1851. Minimum Interval to Include Each Query
Problem Description
In this problem, we are given two primary inputs:
-
A 2D integer array named
intervals
. Each subarray contains two integer values[left_i, right_i]
which represent an interval that starts atleft_i
and ends atright_i
(inclusive). The size of an interval is the number of integers within that range, which is calculated using the formularight_i - left_i + 1
. -
An integer array called
queries
. Each valuequeries[j]
within this array denotes a question asking for the size of the smallest intervali
such thatleft_i <= queries[j] <= right_i
. If no interval satisfies this condition for a given query, the answer is-1
.
The task is to go through each query and determine the answer by finding the appropriate interval that contains the query value and has the smallest size. The result should be returned as an array of answers corresponding to the original order of the queries.
Intuition
The intuition behind the solution approach is to efficiently match queries to their smallest enclosing intervals (if they exist). We need a way to handle these possible overlaps and find the smallest intervals quickly as the number of queries can be quite large. The approach can be broken down into a few key ideas:
-
Sort the
intervals
by their starting point to iterate over them in order. -
Sort the
queries
by their value but keep track of their original indices so we can store the answer in the right place later. -
Use a priority queue (
pq
) to maintain a set of active intervals at any given query value. This priority queue will store pairs of (interval size, right endpoint) sorted by size. -
For each query value
x
, add all the intervals that start at or beforex
to the priority queue. This ensures that at any iteration, the priority queue contains all intervals that could possibly containx
. -
Remove from the priority queue any intervals that end before
x
, as these intervals can no longer contain the query value. -
Look at the smallest interval remaining in the priority queue (which is at the front of the queue due to the sorting by size) to answer the current query. If the priority queue is empty, this means there are no valid intervals for the query, and we should record
-1
. -
Repeat the process for all queries. Since the queries and intervals are sorted, we can do this in a single pass using two pointers, where one iterates over the sorted intervals and the other iterates over the sorted queries.
By using a sorted structure and a priority queue, we can efficiently manage the set of potential intervals for each query, enabling us to quickly find the smallest interval when it exists.
Learn more about Binary Search, Sorting, Line Sweep and Heap (Priority Queue) patterns.
Solution Approach
The solution to the problem leverages both sorting and a heap (priority queue) to efficiently determine the smallest interval containing each query. The implementation proceeds as follows:
-
Sort Intervals and Queries: The first step is to sort the
intervals
based on their starting points, so they can be processed in ascending order. Simultaneously, thequeries
are sorted based on their value, but each query is transformed into a tuple containing its value and original index. This transformation allows us to return the results according to the original order of queries. -
Initialize Data Structures: A priority queue in Python is implemented using a heap, specifically through the built-in
heapq
module. Thepq
list will serve as our priority queue for the intervals. A listans
of sizem
(number of queries) is also initialized to-1
and will be used to store the final answer to each query. -
Iterate Over Queries: We iterate over each sorted query value
x
along with the corresponding original indexj
. The goal during this iteration is to add any new intervals that could potentially containx
and to remove intervals that no longer apply. -
Add Matching Intervals to Priority Queue:
- Using a pointer
i
to traverse the sortedintervals
, we check whether the current interval starts at or before the query valuex
. - If it does, we calculate the size of the interval by
b - a + 1
(wherea
andb
are the starting and ending points of the interval) and push a tuple(size, b)
onto the priority queue (heap). - This ensures that the smallest intervals (by size) will be at the top of the heap.
- Increment
i
to move to the next interval for future queries.
- Using a pointer
-
Remove Invalid Intervals from Priority Queue:
- Before checking the smallest interval, we first clear out any intervals from the priority queue whose end point is before the query value
x
because such intervals cannot possibly containx
. - This is done by popping elements off the heap as long as the smallest interval's end point is less than
x
.
- Before checking the smallest interval, we first clear out any intervals from the priority queue whose end point is before the query value
-
Retrieve the Smallest Valid Interval:
- After potentially removing intervals, if the priority queue is not empty, the interval at the top of the heap is the smallest interval that contains
x
. - We set
ans[j]
(wherej
is the original index of the query) to the size of this interval.
- After potentially removing intervals, if the priority queue is not empty, the interval at the top of the heap is the smallest interval that contains
-
Return Results: Finally, after all queries have been processed, we return the array
ans
, which contains the size of the smallest interval corresponding to each query in the order they were originally presented.
By sorting the intervals and queries and using a min-heap to keep track of active intervals, this approach efficiently manages the various size intervals that could satisfy the range condition for each query, allowing us to determine the minimum interval size required in an optimized manner.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach using a small example.
Suppose our input intervals
array is [[1,4], [2,5], [6,8]]
, and the queries
array is [3, 5, 7]
.
-
Sort Intervals and Queries:
- Firstly, we sort the intervals by their start point, which doesnāt change the order in this case:
[[1,4], [2,5], [6,8]]
. - Then, sort the queries
[3, 5, 7]
. They are already sorted, so we transform them into pairs of values and original indices:[(3, 0), (5, 1), (7, 2)]
.
- Firstly, we sort the intervals by their start point, which doesnāt change the order in this case:
-
Initialize Data Structures:
- We create a priority queue
pq
, which starts as an empty list[]
. - An
ans
list is initialized to store the results:[-1, -1, -1]
(since there are 3 queries).
- We create a priority queue
-
Iterate Over Queries:
- Begin by processing the query value
3
and its corresponding index0
.
- Begin by processing the query value
-
Add Matching Intervals to Priority Queue:
- We check intervals starting with
[1,4]
. Since1 <= 3
, we calculate its size4 - 1 + 1 = 4
and add(4, 4)
to the priority queue. - Next, the interval
[2,5]
. Since2 <= 3
, its size is5 - 2 + 1 = 4
, and we add(4, 5)
to the priority queue. - The queue now has
[(4, 4), (4, 5)]
.
- We check intervals starting with
-
Remove Invalid Intervals from Priority Queue:
- No intervals end before
3
, so nothing is removed.
- No intervals end before
-
Retrieve the Smallest Valid Interval:
- The top of the heap is
(4, 4)
, soans
at the original index0
is updated to4
.
- The top of the heap is
Next, we process the remaining queries. For 5
, both [1,4]
and [2,5]
are considered, but [1,4]
is removed since it doesn't contain 5
. The heap has [(4, 5)]
, and the answer to query 5
is 4
.
For 7
, [6,8]
is considered and (3, 8)
is added to the heap. After removing intervals that end before 7
, we get the smallest interval size 3
for query 7
.
- Return Results:
- The final results array is
[4, 4, 3]
: the smallest intervals containing each query value respectively.
- The final results array is
By following these steps, we effectively matched each query to its smallest enclosing interval, if such one existed, and obtained the solution to our problem.
Solution Implementation
1from heapq import heappush, heappop
2from typing import List
3
4class Solution:
5 def min_interval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:
6 # Sort intervals by starting points
7 intervals.sort()
8 # Pair each query with its original index and sort by the query value
9 sorted_queries = sorted((query, index) for index, query in enumerate(queries))
10
11 # Initialize the result list with -1, assuming interval is not found
12 result = [-1] * len(queries)
13 # A priority queue to store intervals as we process the queries
14 priority_queue = []
15
16 # 'interval_index' tracks the index of the current interval being processed
17 interval_index = 0
18
19 # Loop through each query in sorted_queries
20 for query_value, query_index in sorted_queries:
21 # Add to the priority_queue all intervals that start before or at the query value
22 while interval_index < len(intervals) and intervals[interval_index][0] <= query_value:
23 start, end = intervals[interval_index]
24 interval_size = end - start + 1
25 # Add the interval size and the end value to the priority_queue
26 heappush(priority_queue, (interval_size, end))
27 interval_index += 1
28
29 # Remove intervals from the priority_queue that end before the query value
30 while priority_queue and priority_queue[0][1] < query_value:
31 heappop(priority_queue)
32
33 # If there is an interval that includes the query value, record its size
34 if priority_queue:
35 result[query_index] = priority_queue[0][0]
36
37 return result
38
39# Example usage:
40# sol = Solution()
41# print(sol.min_interval([[1,4],[2,4],[3,6]], [2,3,4,5])) # Output: [3,3,3,4]
42
1class Solution {
2 public int[] minInterval(int[][] intervals, int[] queries) {
3 int numIntervals = intervals.length, numQueries = queries.length;
4
5 // Sort the intervals based on their starting points
6 Arrays.sort(intervals, (interval1, interval2) -> interval1[0] - interval2[0]);
7
8 // Pair each query with its original index and sort by query value
9 int[][] queriesWithIndices = new int[numQueries][];
10 for (int i = 0; i < numQueries; ++i) {
11 queriesWithIndices[i] = new int[] { queries[i], i };
12 }
13 Arrays.sort(queriesWithIndices, (query1, query2) -> query1[0] - query2[0]);
14
15 // Initialize the answer array with -1 (indicating no interval found)
16 int[] answer = new int[numQueries];
17 Arrays.fill(answer, -1);
18
19 // Use a priority queue to store intervals with smallest size (end - start + 1) on top
20 PriorityQueue<int[]> minHeap = new PriorityQueue<>((interval1, interval2) -> interval1[0] - interval2[0]);
21 int index = 0;
22
23 // Process each query
24 for (int[] queryWithIndex : queriesWithIndices) {
25 int queryValue = queryWithIndex[0];
26
27 // Add intervals to the priority queue where the start is less than or equal to the query value
28 while (index < numIntervals && intervals[index][0] <= queryValue) {
29 int start = intervals[index][0], end = intervals[index][1];
30 minHeap.offer(new int[] { end - start + 1, end });
31 ++index;
32 }
33
34 // Remove intervals from the queue which end before the query value
35 while (!minHeap.isEmpty() && minHeap.peek()[1] < queryValue) {
36 minHeap.poll();
37 }
38
39 // If the queue is not empty, there is an interval covering the query value
40 if (!minHeap.isEmpty()) {
41 // The size of the smallest interval covering the query is stored in the answer array
42 answer[queryWithIndex[1]] = minHeap.peek()[0];
43 }
44 }
45
46 return answer; // Return the array containing the size of smallest interval covering each query
47 }
48}
49
1class Solution {
2public:
3 vector<int> minInterval(vector<vector<int>>& intervals, vector<int>& queries) {
4 // n is the number of intervals, m is the number of queries
5 int n = intervals.size(), m = queries.size();
6
7 // Sort the intervals based on start times
8 sort(intervals.begin(), intervals.end());
9
10 using Pair = pair<int, int>; // Defining Pair as a shorthand
11
12 // Create a vector to store queries and their original indices
13 vector<Pair> sortedQueries;
14 for (int i = 0; i < m; ++i) {
15 sortedQueries.emplace_back(queries[i], i);
16 }
17
18 // Sort the queries based on their values
19 sort(sortedQueries.begin(), sortedQueries.end());
20
21 // Answer array with default values -1 (no interval found case)
22 vector<int> ans(m, -1);
23
24 // Min-heap to store the smallest interval covering x and its end time
25 priority_queue<Pair, vector<Pair>, greater<Pair>> minHeap;
26
27 // Index to track the next interval to examine
28 int index = 0;
29
30 // Iterate over sorted queries
31 for (auto& [queryValue, originalIndex] : sortedQueries) {
32 // Add all intervals that start before or at the current query value
33 while (index < n && intervals[index][0] <= queryValue) {
34 int start = intervals[index][0], end = intervals[index][1];
35 // Push the interval size and end value into the heap
36 minHeap.emplace(end - start + 1, end);
37 ++index;
38 }
39
40 // Remove intervals from heap that don't cover the current query value
41 while (!minHeap.empty() && minHeap.top().second < queryValue) {
42 minHeap.pop();
43 }
44
45 // If the heap is not empty, the top element is the smallest interval covering x
46 if (!minHeap.empty()) {
47 ans[originalIndex] = minHeap.top().first;
48 }
49 }
50
51 // Return the filled answer array
52 return ans;
53 }
54};
55
1type Interval = [number, number];
2type Query = number;
3type QueryWithIndex = [number, number];
4type HeapElement = [number, number];
5
6// Function that sorts an array of intervals
7function sortIntervals(intervals: Interval[]): Interval[] {
8 return intervals.sort((a, b) => a[0] - b[0]);
9}
10
11// Function that sorts queries and maintains original indices
12function sortQueries(queries: Query[]): QueryWithIndex[] {
13 return queries.map((query, index) => [query, index])
14 .sort((a, b) => a[0] - b[0]);
15}
16
17// Function to execute the main logic of finding minimum intervals for queries
18function minInterval(intervals: Interval[], queries: Query[]): number[] {
19 const n: number = intervals.length;
20 const m: number = queries.length;
21 let sortedIntervals: Interval[] = sortIntervals(intervals);
22 let sortedQueries: QueryWithIndex[] = sortQueries(queries);
23 let answerArray: number[] = new Array(m).fill(-1); // Initialize answer array with -1 (no interval case)
24
25 // Min-heap to store the smallest interval covering x and its end time
26 let minHeap: HeapElement[] = [];
27
28 // Helper function to push elements to the heap
29 const pushHeap = (size: number, endValue: number) => {
30 minHeap.push([size, endValue]);
31 minHeap.sort((a, b) => a[0] - b[0]);
32 };
33
34 // Helper function to pop the top element from the heap
35 const popHeap = () => {
36 minHeap.shift();
37 };
38
39 // Index to track the next interval to examine
40 let index = 0;
41
42 // Iterate over sorted queries
43 for (const [queryValue, originalIndex] of sortedQueries) {
44 // Add all intervals starting at or before the current query value
45 while (index < n && sortedIntervals[index][0] <= queryValue) {
46 const start = sortedIntervals[index][0];
47 const end = sortedIntervals[index][1];
48 // Push the interval size and end value into the heap
49 pushHeap(end - start + 1, end);
50 index++;
51 }
52
53 // Remove intervals that don't cover the current query
54 while (minHeap.length > 0 && minHeap[0][1] < queryValue) {
55 popHeap();
56 }
57
58 // If the heap is not empty, set the answer as the size of the smallest covering interval
59 if (minHeap.length > 0) {
60 answerArray[originalIndex] = minHeap[0][0];
61 }
62 }
63
64 // Return the filled answer array
65 return answerArray;
66}
67
Time and Space Complexity
Time Complexity:
The time complexity of the code can be broken down into the following parts:
-
Sorting the intervals:
n
is the number of intervals, and this step takesO(n log n)
time using the Timsort algorithm (Python's built-in sorting algorithm). -
Sorting the queries along with their original indices:
m
is the number of queries, and this step also takesO(m log m)
time. -
Traversing the sorted queries and intervals: Each interval and query is checked at most once, which is
O(m + n)
. -
Heap operations: In the worst case, every interval can be pushed and popped once. Given that the priority queue (min-heap) can contain at most
n
elements, each push and pop operation takesO(log n)
. Therefore, if alln
intervals are pushed and popped, it would takeO(n log n)
.
Summing up the complexities, we have O(n log n) + O(m log m)
for the sorting operations and O(m + n)
for the linear traversal, and O(n log n)
for heap operations. The most significant terms are the ones that involve sorting and heap operations, thus overall time complexity is O(n log n + m log m)
.
Space Complexity:
For space complexity:
-
The intervals and the extra space for storing the sorted queries and their original indices require
O(n)
andO(m)
space respectively. -
The priority queue (min-heap) can contain up to
n
elements at any time, and therefore, requiresO(n)
space.
Therefore, the space complexity is O(n + m)
when considering the intervals, queries, and the min-heap storage.
Learn more about how to find time and space complexity quickly using problem constraints.
Which algorithm should you use to find a node that is close to the root of the tree?
Recommended Readings
Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
Line Sweep Introduction The primary motivation for this algorithm is for geometry related problems that we encounter in computer science Deeply rooted in geometric problem solving it has become an essential tool for tackling questions related to shapes lines or points on a Cartesian plane At its heart the line
Want a Structured Path to Master System Design Too? Donāt Miss This!