Minimum Interval to Include Each Query
Understanding the Problem
We have a set of intervals on the number line, and for each query point, we need to find the smallest interval that contains that point. "Contains" means the point falls between the interval's left and right endpoints (inclusive), and "smallest" means the interval with the minimum size (right - left + 1).
The challenge is efficiency. With up to 100,000 intervals and 100,000 queries, checking every interval for every query is too slow. Sorting both the intervals and the queries lets us process everything in a single left-to-right sweep instead of solving each query independently.
Key Constraints:
1 <= intervals.length <= 10^5→ With n up to 100,000 intervals, O(n^2) is 10^10 operations, far too slow. We need O(n log n) or better per dimension.1 <= queries.length <= 10^5→ Same scale as intervals. The combined work must stay near O((n + q) log(n + q)).1 <= left_i <= right_i <= 10^7→ Large value range rules out direct indexing over the number line. We must work with event points, not with every possible integer.
Approach 1: Brute Force
Intuition
For each query, scan every interval and check if it contains the query point. Among all intervals that do, pick the one with the smallest size. This gives a correct baseline to optimize from.
Algorithm
- Create a result array of size
queries.length. - For each query
qat indexj: - Initialize
minSize = infinity. - For each interval
[left, right]: ifleft <= q <= right, computesize = right - left + 1and updateminSize. - If
minSizeis still infinity, setresult[j] = -1. Otherwise, setresult[j] = minSize. - Return
result.
Example Walkthrough
Let's trace through intervals = [[1,4],[2,4],[3,6],[4,4]], queries = [2,3,4,5]:
Code
- Time Complexity: O(n * q). For each of the q queries, we scan all n intervals. With n and q both up to 10^5, this is 10^10 operations, which is far too slow.
- Space Complexity: O(q). We only store the result array of size q.
For every query, we scan all n intervals from scratch, repeating work across queries. The next approach sorts both the intervals and the queries so that processing queries in increasing order lets us maintain a running set of active intervals instead of rescanning.
Approach 2: Sorting + Min-Heap (Line Sweep)
Intuition
Sort the intervals by left endpoint and the queries by value, then sweep from left to right across the number line. For each query, add every interval whose left endpoint is at or before the query. These intervals start early enough to possibly contain the query. Some of them end before the query point, so those must be discarded.
We need the smallest valid interval at each step. A min-heap keyed by interval size provides it. We push candidate intervals onto the heap, pop any whose right endpoint is less than the current query, and the heap's top is the answer.
Expired intervals are not removed eagerly. Before answering a query, we check the heap top: if its right endpoint is before the current query, it can never cover this query or any later one (queries only increase), so we pop it and check the next top. Popping the minimum-size interval is safe because a smaller interval that already expired would never have been a valid answer for a later query anyway. Each interval is pushed once and popped at most once, so the total heap work across the whole sweep is O(n log n).
Algorithm
- Sort
intervalsby left endpoint. - Create a list of
(query_value, original_index)pairs and sort byquery_value. - Initialize a min-heap keyed by interval size and a pointer
i = 0into the sorted intervals. - For each query
(q, idx)in sorted order: - Push all intervals where
left <= qonto the heap as(size, right). - Pop all entries from the heap where
right < q. - If the heap is non-empty,
result[idx] = heap.top().size. Otherwise,result[idx] = -1. - Return
result.
Example Walkthrough
Code
- Time Complexity: O((n + q) log n). Sorting intervals takes O(n log n). Sorting queries takes O(q log q). Each interval is pushed and popped from the heap at most once, and each heap operation is O(log n).
- Space Complexity: O(n + q). The heap holds at most n intervals. The sorted queries array and result array each use O(q) space.
When queries contain many duplicates, this version repeats the heap peek-and-pop work for every copy of the same query value. The next approach computes the answer once per unique query value and reuses it.
Approach 3: Sorting + Hash Map (Optimal)
Intuition
This approach uses the same sweep but processes each distinct query value only once. Instead of pairing every query with its original index and sorting those pairs, we extract the unique query values, compute the answer for each, and store it in a hash map keyed by query value. At the end, we look up each original query's answer.
The sweep logic is unchanged: sort intervals by left endpoint, process unique queries in sorted order, and use a min-heap to track the smallest active interval. The benefit appears when queries repeat: a query value that occurs many times drives only one round of heap operations rather than one per occurrence.
Algorithm
- Sort
intervalsby left endpoint. - Extract sorted unique query values.
- Initialize a min-heap keyed by interval size and an interval pointer
i = 0. - For each unique query value
qin sorted order: - Push all intervals where
left <= qonto the heap as(size, right). - Pop all entries where
right < q. - Store
queryMap[q] = heap.top().size(or -1 if empty). - Build the result array by looking up each original query in
queryMap.
Example Walkthrough
Code
- Time Complexity: O((n + q) log n). Same as Approach 2. Sorting is O(n log n + q log q). The sweep processes at most n intervals (push/pop) and at most q unique query values. Hash map lookups at the end are O(q).
- Space Complexity: O(n + q). Heap holds at most n entries. Hash map holds at most q entries. Result array is O(q).