Minimum Interval to Include Each Query solution and explanation
Google
9 more videos on this problem
Minimum Interval to Include Each Query - Leetcode 1851 - PythonNeetCode · 26:23 · 68K views
Minimum Interval Query | LeetCode 1851 (Hard) HeapDestination FAANG · 18:14 · 1K views
LeetCode 1851. Minimum Interval to Include Each QueryHappy Coding · 20:16 · 1K views
Google Coding Interview Question | Leetcode 1851 | Minimum Interval to Include Each QueryWorkWithGoogler · 21:45 · 1K views
Leetcode Contest 239: Minimum Interval to Include Each QueryCoding Ninjas Webinars and Contest Editorials · 18:26 · 890 views
【每日一题】1851. Minimum Interval to Include Each Query, 6/20/2021Huifeng Guan · 21:40 · 744 views
1851. Minimum Interval to Include Each Query (Leetcode Hard)Programming Live with Larry · 18:35 · 682 views
LeetCode 1851. Minimum Interval to Include Each Query | Hard | Line SweepThe Compass · 24:37 · 429 views
Minimum Interval to Include Each Query Neetcode150 Series: (150 of 150) LeetcodeRaymond Chen · 12:02 · 254 views
LeetCode 1851. Minimum Interval to Include Each Query 中文 | Weekly Contest 239宰相小甘罗 · 3:25 · 235 views
The problem
You are given a 2D integer array intervals, where intervals[i] = [lefti, righti] describes the ith interval starting at lefti and ending at righti (inclusive). The size of an interval is defined as the number of integers it contains, or more formally righti - lefti + 1.
You are also given an integer array queries. The answer to the jth query is the size of the smallest interval i such that lefti <= queries[j] <= righti. If no such interval exists, the answer is -1.
Return an array containing the answers to the queries.
Example 1:
Input: intervals = [[1,4],[2,4],[3,6],[4,4]], queries = [2,3,4,5] Output: [3,3,1,4] Explanation: The queries are processed as follows: - Query = 2: The interval [2,4] is the smallest interval containing 2. The answer is 4 - 2 + 1 = 3. - Query = 3: The interval [2,4] is the smallest interval containing 3. The answer is 4 - 2 + 1 = 3. - Query = 4: The interval [4,4] is the smallest interval containing 4. The answer is 4 - 4 + 1 = 1. - Query = 5: The interval [3,6] is the smallest interval containing 5. The answer is 6 - 3 + 1 = 4.
Example 2:
Input: intervals = [[2,3],[2,5],[1,8],[20,25]], queries = [2,19,5,22] Output: [2,-1,4,6] Explanation: The queries are processed as follows: - Query = 2: The interval [2,3] is the smallest interval containing 2. The answer is 3 - 2 + 1 = 2. - Query = 19: None of the intervals contain 19. The answer is -1. - Query = 5: The interval [2,5] is the smallest interval containing 5. The answer is 5 - 2 + 1 = 4. - Query = 22: The interval [20,25] is the smallest interval containing 22. The answer is 25 - 20 + 1 = 6.
Constraints:
1 <= intervals.length <= 1051 <= queries.length <= 105intervals[i].length == 21 <= lefti <= righti <= 1071 <= queries[j] <= 107
Approach overview
Problem Overview: You get a list of intervals [start, end] and a list of query values. For each query, return the length of the smallest interval that contains that value. If no interval covers the query, return -1. The challenge is answering many queries efficiently without scanning every interval each time.
Approach 1: Sorting with Two Pointers Approach (O((n + q) log n) time, O(n) space)
Sort intervals by start time and sort queries while keeping their original indices. Use two pointers to iterate through intervals as queries increase. When the interval start becomes <= current query, add that interval to a structure tracking candidate intervals. Remove intervals whose end is smaller than the query. The smallest valid interval length is tracked dynamically. This approach relies heavily on sorting and pointer movement across both arrays.
Approach 2: Binary Search with Interval Indexing (O((n + q) log n) time, O(n) space)
Sort intervals by start value and build indexed structures for fast lookups. For each query, use binary search to locate the first interval whose start could contain the query. From that position, evaluate candidate intervals that still satisfy start ≤ query ≤ end. Track the minimum interval length while scanning valid ranges. Binary search reduces the search window for each query instead of checking all intervals.
Approach 3: Priority Queue with Sorting (O((n + q) log n) time, O(n) space)
Sort intervals by start and queries by value. As you process each query from smallest to largest, push intervals whose start ≤ query into a min heap keyed by interval length. Remove heap entries where end < query because they no longer cover the query. The top of the heap always gives the smallest interval that currently contains the query. This combination of priority queue, sorting, and a sweep over queries behaves like a classic line sweep technique.
Approach 4: Sorting and Binary Search (O((n + q) log n) time, O(n) space)
Sort intervals and preprocess useful metadata such as interval lengths and endpoints. For each query, use binary search to locate candidate intervals and evaluate which ones cover the query. Maintain the smallest length among valid matches. This method is straightforward to implement when binary search utilities are readily available and avoids maintaining a dynamic heap.
Recommended for interviews: The priority queue with sorting approach is the one most interviewers expect. It demonstrates control of offline query processing, heap operations, and efficient interval filtering. Showing the brute-force idea first (checking every interval per query) proves you understand the problem, but moving to the heap-based sweep with O((n + q) log n) complexity shows strong algorithmic thinking.
Approach 1: Sorting with Two Pointers Approach
Sort both intervals by size and queries by their values. Use a two-pointer technique to iterate over intervals and queries simultaneously, maintaining a data structure (min-heap) to efficiently access the interval with the smallest size that contains the current query. This allows you to efficiently process each query in O(log n) time on average, leading to a total time complexity of O((m + n) log n), where m is the number of queries and n is the number of intervals.
import heapq
def min_interval(intervals, queries):
intervals.sort(key=lambda x: (x[1] - x[0] + 1, x[0]))
sorted_queries = sorted((q, i) for i, q in enumerate(queries))
min_heap, result = [], [-1] * len(queries)
interval_idx = 0
for q, i in sorted_queries:
while interval_idx < len(intervals) and intervals[interval_idx][0] <= q:
heapq.heappush(min_heap, (intervals[interval_idx][1] - intervals[interval_idx][0] + 1, intervals[interval_idx][1], intervals[interval_idx][0]))
interval_idx += 1
while min_heap and min_heap[0][1] < q:
heapq.heappop(min_heap)
if min_heap:
result[i] = min_heap[0][0]
return result
# Example usage
intervals = [[1,4],[2,4],[3,6],[4,4]]
queries = [2,3,4,5]
print(min_interval(intervals, queries)) # [3, 3, 1, 4]In this Python implementation, intervals are first sorted by their size, then by their start point. Queries are sorted to process from left to right. A min-heap is used to keep the smallest interval available that includes the query. We iteratively check each query against available intervals and update the heap if an interval does not satisfy the query condition anymore.
Time Complexity: O((n + m) log n), where n is the number of intervals and m is the number of queries. Space Complexity: O(n), used by the heap.
Approach 2: Binary Search with Interval Indexing
Sort intervals and queries. For each query, use binary search to find the smallest interval containing it. You maintain an active set of intervals and perform binary search over this set for each query. This approach efficiently handles comparisons and updates to determine the smallest intervals.
function minInterval(intervals, queries) {
intervals.sort((a, b) => (a[1] - a[0] + 1) - (b[1] - b[0] + 1));
let sortedQueries = queries.map((q, idx) => [q, idx]).sort((a, b) => a[0] - b[0]);
let minHeap = [];
let results = new Array(queries.length).fill(-1);
let intervalIdx = 0;
for (let [q, i] of sortedQueries) {
while (intervalIdx < intervals.length && intervals[intervalIdx][0] <= q) {
minHeap.push([intervals[intervalIdx][1] - intervals[intervalIdx][0] + 1, intervals[intervalIdx][1], intervals[intervalIdx][0]]);
minHeap.sort((a, b) => a[0] - b[0]); // This keeps the smallest size at the front
intervalIdx++;
}
while (minHeap.length > 0 && minHeap[0][1] < q) {
minHeap.shift();
}
if (minHeap.length > 0) {
results[i] = minHeap[0][0];
}
}
return results;
}
// Example usage
let intervals = [[1,4],[2,4],[3,6],[4,4]];
let queries = [2,3,4,5];
console.log(minInterval(intervals, queries)); // [3, 3, 1, 4]This Javascript solution sorts intervals by size as primary criteria. For each query, intervals are maintained in a min-heap that helps track the smallest interval containing the current query. Intervals are added or removed from this heap through a loop, ensuring complexity remains reasonable.
Time Complexity: O((n + m) log n), due to both sorting intervals and reorganizing the heap. Space Complexity: O(n), for the data structures used.
Approach 3: Priority Queue with Sorting
Approach Description: We first sort the intervals based on their start points and prepare a priority queue (or heap) to process them by size. For each query, process the intervals that start before or when the query appears and use the priority queue to find the smallest valid interval.
import heapq
def minInterval(intervals, queries):
intervals.sort()
results = {}
min_heap = []
i = 0
for q in sorted(queries):
while i < len(intervals) and intervals[i][0] <= q:
left, right = intervals[i]
heapq.heappush(min_heap, (right - left + 1, right))
i += 1
while min_heap and min_heap[0][1] < q:
heapq.heappop(min_heap)
results[q] = min_heap[0][0] if min_heap else -1
return [results[q] for q in queries]
# Example usage
intervals = [[1,4],[2,4],[3,6],[4,4]]
queries = [2,3,4,5]
print(minInterval(intervals, queries))import java.util.*;
public class Solution {
public int[] minInterval(int[][] intervals, int[] queries) {
Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
int[] result = new int[queries.length];
Map<Integer, Integer> resultsMap = new HashMap<>();
PriorityQueue<int[]> minHeap = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
List<Integer> sortedQueries = new ArrayList<>();
for (int q : queries) sortedQueries.add(q);
sortedQueries.sort(Integer::compare);
int i = 0;
for (int q : sortedQueries) {
while (i < intervals.length && intervals[i][0] <= q) {
minHeap.add(new int[]{intervals[i][1] - intervals[i][0] + 1, intervals[i][1]});
i++;
}
while (!minHeap.isEmpty() && minHeap.peek()[1] < q) {
minHeap.poll();
}
resultsMap.put(q, minHeap.isEmpty() ? -1 : minHeap.peek()[0]);
}
for (int j = 0; j < queries.length; j++) {
result[j] = resultsMap.get(queries[j]);
}
return result;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[][] intervals = {{1, 4}, {2, 4}, {3, 6}, {4, 4}};
int[] queries = {2, 3, 4, 5};
System.out.println(Arrays.toString(sol.minInterval(intervals, queries)));
}
}This Python code utilizes a priority queue (min-heap) to find the smallest interval for every query. We sort the intervals and process each query in sorted order, adding all potential intervals into the heap and discarding irrelevant ones. The heap ensures that we can quickly retrieve the smallest interval size that contains the query.
Time Complexity: O((n + m) log n), where n is the number of intervals and m is the number of queries. We sort intervals and queries, and maintain a heap for processing.
Space Complexity: O(n) for the heap that stores intervals.
Approach 4: Sorting and Binary Search
Approach Description: Sort the intervals by their starting and ending points. For each query, use binary search to find the smallest interval that contains the query point in this sorted list. Keeping track of active intervals helps efficiently locate the correct interval size.
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
vector<int> minInterval(vector<vector<int>>& intervals, vector<int>& queries) {
map<int, vector<int>> active;
vector<int> sortedQueries = queries;
sort(sortedQueries.begin(), sortedQueries.end());
sort(intervals.begin(), intervals.end());
vector<int> result(queries.size(), -1);
int i = 0;
for (int q : sortedQueries) {
while (i < intervals.size() && intervals[i][0] <= q) {
active[intervals[i][1] - intervals[i][0] + 1].push_back(intervals[i][1]);
i++;
}
while (!active.empty() && active.begin()->second.front() < q) {
active.begin()->second.erase(active.begin()->second.begin());
if (active.begin()->second.empty()) { active.erase(active.begin()); }
}
if (!active.empty()) { result[find(queries.begin(), queries.end(), q) - queries.begin()] = active.begin()->first; }
}
return result;
}
int main() {
vector<vector<int>> intervals = {{1, 4}, {2, 4}, {3, 6}, {4, 4}};
vector<int> queries = {2, 3, 4, 5};
vector<int> output = minInterval(intervals, queries);
for (int res : output) { cout << res << " "; }
return 0;
}function minInterval(intervals, queries) {
intervals.sort((a, b) => a[0] - b[0]);
let sortedQueries = [...queries].sort((a, b) => a - b);
let mapResults = new Map();
let results = Array(queries.length);
let i = 0;
let minHeap = [];
for (let q of sortedQueries) {
while (i < intervals.length && intervals[i][0] <= q) {
const [l, r] = intervals[i];
minHeap.push([r - l + 1, r]);
i++;
}
minHeap = minHeap.filter(([size, end]) => end >= q);
minHeap.sort((a, b) => a[0] - b[0]);
mapResults.set(q, minHeap.length > 0 ? minHeap[0][0] : -1);
}
return queries.map(q => mapResults.get(q));
}
// Example usage
let intervals = [[1, 4], [2, 4], [3, 6], [4, 4]];
let queries = [2, 3, 4, 5];
console.log(minInterval(intervals, queries));This C++ code makes use of sorting and a map to emulate a priority queue for managing interval ranges. Intervals are sorted, and for each query, relevant intervals are checked using a combination of sorting and direct access through map operations.
Time Complexity: O(n log n + m log n) due to sorting and potential binary search operations.
Space Complexity: O(n) for the map to keep track of interval sizes.
Approach 5: Sorting + Offline Query + Priority Queue (Min Heap)
We notice that the order of queries does not affect the answer, and the intervals involved do not change. Therefore, we consider sorting all queries in ascending order, and sorting all intervals in ascending order of the left endpoint.
We use a priority queue (min heap) pq to maintain all current intervals. Each element in the queue is a pair (v, r), representing an interval with length v and right endpoint r. Initially, the priority queue is empty. In addition, we define a pointer i that points to the current interval being traversed, and initially i=0.
We traverse each query (x, j) in ascending order and perform the following operations:
- If the pointer
ihas not traversed all intervals, and the left endpoint of the current interval[a, b]is less than or equal tox, then we add this interval to the priority queue and move the pointerione step forward. Repeat this process. - If the priority queue is not empty, and the right endpoint of the heap top element is less than
x, then we pop the heap top element. Repeat this process. - At this point, if the priority queue is not empty, then the heap top element is the smallest interval containing
x. We add its lengthvto the answer arrayans.
After the above process is over, we return the answer array ans.
The time complexity is O(n times log n + m times log m), and the space complexity is O(n + m). Where n and m are the lengths of the arrays intervals and queries respectively.
func minInterval(intervals [][]int, queries []int) []int {
n, m := len(intervals), len(queries)
sort.Slice(intervals, func(i, j int) bool { return intervals[i][0] < intervals[j][0] })
qs := make([][2]int, m)
ans := make([]int, m)
for i := range qs {
qs[i] = [2]int{queries[i], i}
ans[i] = -1
}
sort.Slice(qs, func(i, j int) bool { return qs[i][0] < qs[j][0] })
pq := hp{}
i := 0
for _, q := range qs {
x, j := q[0], q[1]
for i < n && intervals[i][0] <= x {
a, b := intervals[i][0], intervals[i][1]
heap.Push(&pq, pair{b - a + 1, b})
i++
}
for len(pq) > 0 && pq[0].r < x {
heap.Pop(&pq)
}
if len(pq) > 0 {
ans[j] = pq[0].v
}
}
return ans
}
type pair struct{ v, r int }
type hp []pair
func (h hp) Len() int { return len(h) }
func (h hp) Less(i, j int) bool { return h[i].v < h[j].v }
func (h hp) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(v any) { *h = append(*h, v.(pair)) }
func (h *hp) Pop() any { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }Complexity comparison
| Approach | Complexity |
|---|---|
| Sorting with Two Pointers Approach | Time Complexity: O((n + m) log n), where n is the number of intervals and m is the number of queries. Space Complexity: O(n), used by the heap. |
| Binary Search with Interval Indexing | Time Complexity: O((n + m) log n), due to both sorting intervals and reorganizing the heap. Space Complexity: O(n), for the data structures used. |
| Priority Queue with Sorting | Time Complexity: Space Complexity: |
| Sorting and Binary Search | Time Complexity: Space Complexity: |
| Sorting + Offline Query + Priority Queue (Min Heap) | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting with Two Pointers | O((n + q) log n) | O(n) | When processing queries offline with sorted intervals |
| Binary Search with Interval Indexing | O((n + q) log n) | O(n) | When you want direct lookup of candidate intervals using binary search |
| Priority Queue with Sorting | O((n + q) log n) | O(n) | Best general solution; dynamically tracks smallest valid interval |
| Sorting and Binary Search | O((n + q) log n) | O(n) | When intervals are preprocessed and heap usage is unnecessary |
Frequently asked questions
Is Minimum Interval to Include Each Query easy or hard?
Minimum Interval to Include Each Query is classified as a Hard problem. The difficulty comes from combining sorting, offline query processing, and heap maintenance while ensuring each interval is processed only once to achieve O((n + q) log n) performance.
Minimum Interval to Include Each Query Python or Java solution?
Python implementations typically use the heapq module to maintain the min heap of candidate intervals, while Java solutions use PriorityQueue. Both follow the same pattern: sort intervals, sort queries with indices, push valid intervals into the heap, remove expired intervals, and record the smallest interval length.
What is the best approach for Minimum Interval to Include Each Query?
The most effective solution sorts intervals and queries, then uses a min heap to track candidate intervals. As queries increase, intervals whose start is ≤ query are pushed into the heap, and intervals that end before the query are removed. The smallest interval length in the heap is the answer for that query. This priority queue approach runs in O((n + q) log n) time.
How to solve Minimum Interval to Include Each Query in O((n+q) log n)?
Sort intervals by start and queries by value. Iterate through queries in increasing order while inserting intervals whose start ≤ query into a min heap keyed by interval length. Remove intervals whose end < query because they no longer cover the query. The heap top gives the smallest valid interval length for that query.
Is Minimum Interval to Include Each Query asked at Google/Amazon/Meta?
Interval processing and heap-based query problems frequently appear in interviews at companies like Google, Amazon, and Meta. The problem tests understanding of sorting, line sweep techniques, and priority queue optimization, which are common patterns in real interview questions.
What data structure is used in Minimum Interval to Include Each Query?
The core data structure is a min heap (priority queue) that stores intervals currently capable of covering the query. Each heap element is typically ordered by interval length so the smallest covering interval can be retrieved in O(log n) time. Sorting and binary search are also used for efficient traversal.
What is the time complexity of Minimum Interval to Include Each Query?
The optimal algorithm runs in O((n + q) log n) time where n is the number of intervals and q is the number of queries. Sorting intervals and queries takes O(n log n + q log q), and each interval is pushed and popped from the heap at most once. Space complexity is O(n) for the heap and query indexing.