Minimum Interval to Include Each Query
Last Updated: April 2, 2026
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 would be way too slow. We need a strategy that avoids redundant work, and the key insight is that sorting, both the intervals and the queries, lets us process everything in a single sweep instead of brute-forcing 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
The most direct approach: 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 is what you would naturally write first, and it gives us 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 single query, we scan through all n intervals. Many intervals share similar left endpoints. If we sorted intervals and queries, we could avoid re-scanning intervals we've already ruled out. What if we processed queries in sorted order and kept a running set of active intervals?
Approach 2: Sorting + Min-Heap (Line Sweep)
Intuition
Here's the key insight: if we sort both the intervals (by left endpoint) and the queries (by value), we can sweep from left to right across the number line. For each query, we add all intervals whose left endpoint is at or before the query. These are candidates, intervals that start early enough to possibly contain the query. But some of them end before the query point, so we need to discard those.
We want the smallest valid interval at any moment. A min-heap keyed by interval size gives us exactly that. We push candidate intervals onto the heap, lazily pop any whose right endpoint is less than the current query, and the heap's top is our answer.
We don't remove expired intervals eagerly. Instead, when we peek at the top of the heap to answer a query, we check if it's still valid. If its right endpoint is before the query, we pop it and check the next one. This is efficient because each interval is pushed and popped at most once across the entire sweep.
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.
The heap approach works well, but when queries contain many duplicates, we're doing repeated heap operations for the same query value. What if we computed the answer once per unique query value and reused it?
Approach 3: Sorting + Hash Map (Optimal)
Intuition
This approach takes the same sweep idea but makes it cleaner. Instead of pairing every query with its original index and sorting those pairs, we extract the unique query values, compute the answer for each one, and store results in a hash map. At the end, we just look up each original query's answer.
The sweep logic is identical: sort intervals by left endpoint, process unique queries in sorted order, use a min-heap to track the smallest active interval. But the code is shorter and, when queries have duplicates, we avoid redundant heap operations.
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).