Min Interval for Query LeetCode 1851

LeetCode 1851 gives you a list of intervals (each a [left, right] pair) and a list of query points. For each query point, find the size of the smallest interval that contains that query point, where the size of an interval [l, r] is r - l + 1. If no interval covers a query, return -1 for that position. Return an answer array aligned with the original order of the queries.

Intervals can overlap freely, and multiple intervals may cover the same query point. Among all qualifying intervals, you want the one with the minimum size — the tightest possible wrapper around the query. This is not about finding which query falls in an interval; it is about finding the minimum-size interval from potentially many candidates.

The constraints are tight: up to 10^5 intervals and 10^5 queries, each value up to 10^7. A brute force O(n*m) solution scanning all intervals for every query will time out, so an efficient sweep-based approach is required.

The naive approach checks every interval for every query: for each of m queries, iterate through all n intervals, test if left <= query <= right, and track the minimum size among those that qualify. This is O(n*m), and with n = m = 10^5 that is 10^10 operations — completely infeasible within the 1–2 second time limit.

A sorted binary search on interval start points helps only partially. You can binary search to find intervals with start <= query in O(log n), but you still need to inspect all such intervals to find the one with the smallest size that also ends at or after the query — you cannot binary search on two constraints simultaneously.

The key insight is to decouple the problem: process all queries in sorted order (offline), and maintain a data structure that efficiently answers "what is the smallest-size active interval" at each step. A min-heap keyed by interval size is exactly that structure.

"Offline" processing means we are allowed to reorder queries before answering them, as long as we map answers back to the original order at the end. This is in contrast to "online" processing where each query must be answered before the next arrives. LeetCode 1851 has no ordering constraint on how we process queries, so we can sort them freely.

The strategy is: sort intervals by their start value; create a list of (query_value, original_index) pairs sorted by query value; use a pointer into the sorted intervals array. For each query in ascending order, advance the pointer to add all intervals with start <= query to the min-heap. Then handle expired intervals and read the answer.

Sorting both arrays takes O(n log n + m log m). Each interval is pushed to the heap once and popped at most once, giving O(n log n) heap operations. Each query costs O(log n) for the heap top check. Total: O((n + m) log n), which comfortably fits within time limits for 10^5 inputs.

The min-heap stores tuples of (interval_size, interval_end). The heap is ordered by interval_size (the first element), so the heap root is always the smallest-size interval currently in the heap. When multiple intervals cover a query, the smallest one surfaces automatically at the top.

For each query, first push all intervals with start <= query onto the heap. Then remove all heap entries where end < query — those intervals have already ended and no longer cover the current query point. After removal, if the heap is non-empty, heap[0][0] is the answer (the size field of the smallest active interval).

The heap naturally maintains only intervals that started at or before the current query. Expired intervals (those whose end < query) are removed lazily from the top. Since queries are processed in ascending order, an interval once expired will never become active again — all subsequent queries are larger, so if end < current_query, it is also less than all future queries.

Instead of removing all expired intervals eagerly (which would require a more complex data structure), we use lazy deletion: check the heap top, and if its end < current query, pop it and check again. Repeat until the heap is empty or the top is a valid (non-expired) interval. This is an inner while loop wrapping the heap pop.

Lazy deletion is correct here because queries are processed in ascending order. Once an interval expires (end < query), all future queries are >= current query, so the interval will never be valid again. We can safely discard it the moment we encounter it at the heap top. We never need to eagerly scan or remove from the middle of the heap.

The amortized cost is O(1) per pop: each interval is pushed exactly once and popped at most once across the entire algorithm. The total number of heap operations is O(n) pushes and O(n) pops, giving O(n log n) total heap cost regardless of how many queries are processed. This is why lazy deletion works so well for offline sweep problems.

Python: sort intervals by start. Build sorted_queries = sorted(enumerate(queries), key=lambda x: x[1]). Initialize heap = [], i = 0, ans = [-1] * len(queries). For orig_idx, q in sorted_queries: push heapq.heappush(heap, (r-l+1, r)) for all intervals[i] with intervals[i][0] <= q, advancing i. Then while heap and heap[0][1] < q: heapq.heappop(heap). If heap: ans[orig_idx] = heap[0][0]. Return ans. Total: O((n+m) log n) time, O(n+m) space.

Java: sort intervals by intervals[i][0]. Create int[][] qs = new int[m][2] storing {queries[j], j}, then sort qs by value. Use PriorityQueue<int[]> pq = new PriorityQueue<>((a,b)->a[0]-b[0]) storing {size, end}. Iterate qs: advance pointer and add intervals; poll expired pq entries; set ans[qs[j][1]] = pq.isEmpty() ? -1 : pq.peek()[0]. Java requires explicit comparator for int[] in the PriorityQueue to sort by size.

The only subtle difference between Python and Java is index tracking: in Python, enumerate(queries) gives (index, value) pairs naturally; in Java, create a 2D array of {value, original_index} before sorting. In both cases, after sorting queries, ans[original_index] is set during the sweep. The heap comparison key (size) is the same in both languages.

The Skyline Problem (LeetCode 218) uses a similar sweep: process building edges as events sorted by x-coordinate, use a max-heap of active building heights, and record transitions in the skyline. Both problems sweep a sorted event list while maintaining a heap of "active" elements and lazily removing expired ones. The skyline problem is harder because removal events are mixed with addition events.

Meeting Rooms II (LeetCode 253) asks for the minimum number of conference rooms needed given a set of meeting intervals. Sort meetings by start time and use a min-heap of end times to track when rooms free up. Again the pattern is: sort intervals, sweep with a pointer, use a heap as the active-set data structure. Mastering LeetCode 1851 makes Meeting Rooms II straightforward.

Merge Intervals (LeetCode 56) and Interval List Intersections (LeetCode 986) round out the interval family. Merge Intervals is purely sort-and-scan; Interval List Intersections uses two pointers. Together with the sweep line + heap pattern of LeetCode 1851, these four problems cover the full spectrum of interval algorithm techniques asked in technical interviews.