You are given a 2D integer array intervals, where intervals[i] = [left_i, right_i] describes the i-th interval starting at left_i and ending at right_i (inclusive). The size of an interval is right_i - left_i + 1. You are also given an integer array queries. The answer to the j-th query is the size of the smallest interval i such that left_i <= queries[j] <= right_i. If no such interval exists, the answer is -1.
Constraints: 1 ≤ intervals.length ≤ 10⁵ · 1 ≤ queries.length ≤ 10⁵ · 1 ≤ leftᵢ ≤ rightᵢ ≤ 10⁷
Given intervals = [[1,4],[2,4],[3,6],[4,4]] and queries = [2,3,4,5], find the smallest interval containing each query. The brute-force approach is simple: for each query, scan ALL intervals, check which ones contain the query, and pick the smallest. Simple means slow.
Below is a number line with each interval drawn as a horizontal bar. Drag the query pointer left and right to see which intervals contain the current position. Watch how the “smallest containing” badge changes as you move — and notice that you are checking every single interval at every position.
This is exactly what brute force does: for each query, it tests start <= q <= end on EVERY interval, then picks the minimum size. Four intervals and four queries means 16 checks. At the constraint limit (`n = q = 10^5`), that becomes 10 billion.
Why is this so wasteful? Consider queries 2345. When you check q=2, you discover that 14 and 24 both contain it. Then for q=3, you scan ALL four intervals again — even though 14 and 24 obviously still contain 3 (they contained 2, and 3 is between 2 and 4). The brute-force approach has no memory: each query starts from zero, discarding everything learned from the previous one. That redundancy is the root of the O(n * q) blowup.
Drag the pointer across the full number line to see how the containing intervals change.