436. Find Right Interval
Problem Description
The goal of this problem is to find the "right interval" for a given set of intervals. Given an array intervals
, where each element intervals[i]
represents an interval with a start_i
and an end_i
, we need to identify for each interval i
another interval j
where the interval j
starts at or after the end of interval i
, and among all such possible j
, it starts the earliest. This means that the start of interval j
(start_j
) must be greater than or equal to the end of interval i
(end_i
), and we want the smallest such start_j
. If there is no such interval j
that meets these criteria, the corresponding index should be -1
.
The challenge is to write a function that returns an array of indices of the right intervals for each interval. If an interval has no right interval, as mentioned -1
will be the placeholder for that interval.
Intuition
To approach this problem, we utilize a binary search strategy to efficiently find the right interval for each entry. Here's how we arrive at the solution:
- To make it possible to return indices, we augment each interval with its original index in the
intervals
array. - We then sort the augmented intervals according to the starting points. The sort operation allows us to apply binary search later since binary search requires a sorted sequence.
- Prepare an answer array filled with
-1
to assume initially that there is no right interval for each interval. - For each interval, use binary search (
bisect_left
) to efficiently find the least starting intervalj
that is greater than or equal to the end of the current intervali
. - If the binary search finds such an interval, update the answer array at index
i
with the index of the found intervalj
. - After completing the search for all intervals, the answer array is returned.
Implementing binary search reduces the complexity of finding the right interval from a brute-force search which would be O(n^2) to O(n log n) since each binary search operation takes O(log n) and we perform it for each of the n intervals.
Learn more about Binary Search and Sorting patterns.
Solution Approach
The solution to this problem involves the following steps, which implement a binary search algorithm:
-
Augment Intervals with Indices: First, we update each interval to include its original index. This is achieved by iterating through the
intervals
array and appending the index to each interval.for i, v in enumerate(intervals): v.append(i)
-
Sort Intervals by Start Times: We then sort the augmented intervals based on their start times. This allows us to leverage binary search later on since it requires the list to be sorted.
intervals.sort()
-
Initialize Answer Array: We prepare an answer array,
ans
, with the same length as theintervals
array and initialize all its values to-1
, which indicates that initially, we assume there is no right interval for any interval.ans = [-1] * n
-
Binary Search for Right Intervals: For each interval in
intervals
, we perform a binary search to find the minimumstart_j
value that is greater than or equal toend_i
. To do this, we use thebisect_left
method from thebisect
module. It returns the index at which theend_i
value could be inserted to maintain the sorted order.for _, e, i in intervals: j = bisect_left(intervals, [e])
-
Updating the Answer: If the binary search returns an index less than the number of intervals (
n
), it means we have found a right interval. We then update theans[i]
with the original index of the identified right interval, which is stored atintervals[j][2]
.if j < n: ans[i] = intervals[j][2]
-
Return the Final Array: After the loop, the
ans
array is populated with the indices of right intervals for each interval in the given array. This array is then returned as the final answer.return ans
This approach efficiently uses binary search to minimize the time complexity. The key to binary search is the sorted nature of the intervals
after they are augmented with their original indices. By maintaining a sorted list of start times and employing binary search, we're able to significantly reduce the number of comparisons needed to find the right interval from linear (checking each possibility one by one) to logarithmic, thus enhancing the performance of the solution.
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 walk through this approach with a small example. Consider the list of intervals intervals = [[1,2], [3,4], [2,3], [4,5]]
.
-
First, we augment each interval with its index.
augmented_intervals = [[1, 2, 0], [3, 4, 1], [2, 3, 2], [4, 5, 3]]
-
Next, we sort the augmented intervals by their start times.
sorted_intervals = [[1, 2, 0], [2, 3, 2], [3, 4, 1], [4, 5, 3]]
-
We initialize the answer array with all elements set to
-1
.ans = [-1, -1, -1, -1]
-
Now, using a binary search, we look for the right interval for each interval in
sorted_intervals
.For interval
[1, 2, 0]
:- The end time is
2
. - The binary search tries to find the minimum index where
2
could be inserted to maintain the sorted order, which is index1
(interval[2, 3, 2]
). - Thus, the right interval index is
2
.
For interval
[2, 3, 2]
:- The end time is
3
. - The binary search finds index
2
(interval[3, 4, 1]
). - The right interval index is
1
.
For interval
[3, 4, 1]
:- The end time is
4
. - The binary search finds index
3
(interval[4, 5, 3]
). - The right interval index is
3
.
For interval
[4, 5, 3]
:- The end time is
5
, and there's no interval starting after5
. - The binary search returns an index of
4
, which is outside the array bounds. - There's no right interval, so the value remains
-1
.
- The end time is
-
After performing the binary search for all intervals, we update the answer array with the right intervals' indices.
ans = [2, 1, 3, -1]
-
The
ans
array, which keeps track of the right interval for each interval, is returned as the final answer. In our example, this is[2, 1, 3, -1]
, indicating that the interval[1,2]
is followed by[2,3]
,[3,4]
follows[2,3]
, and[4,5]
follows[3,4]
. The last interval,[4,5]
, has no following interval that satisfies the conditions.
This approach efficiently finds the right intervals for each given interval with reduced time complexity.
Solution Implementation
1from bisect import bisect_left
2from typing import List
3
4class Solution:
5 def findRightInterval(self, intervals: List[List[int]]) -> List[int]:
6 # Append the original index to each interval
7 for index, interval in enumerate(intervals):
8 interval.append(index)
9
10 # Sort intervals based on their start times
11 intervals.sort()
12 n = len(intervals)
13 answer = [-1] * n # Initialize the answer list with -1
14
15 # Iterate through the sorted intervals
16 for _, end, original_index in intervals:
17 # Find the leftmost interval starting after the current interval's end
18 right_index = bisect_left(intervals, [end])
19 # If such an interval exists, update the corresponding position in answer
20 if right_index < n:
21 answer[original_index] = intervals[right_index][2]
22
23 return answer
24
1class Solution {
2 public int[] findRightInterval(int[][] intervals) {
3 int numIntervals = intervals.length;
4 // This list will hold the start points and their corresponding indices
5 List<int[]> startIndexPairs = new ArrayList<>();
6
7 // Populate the list with the start points and their indices
8 for (int i = 0; i < numIntervals; ++i) {
9 startIndexPairs.add(new int[] {intervals[i][0], i});
10 }
11
12 // Sort the startIndexPairs based on the start points in ascending order
13 startIndexPairs.sort(Comparator.comparingInt(a -> a[0]));
14
15 // Prepare an array to store the result
16 int[] result = new int[numIntervals];
17
18 // Initialize an index for placing interval results
19 int resultIndex = 0;
20
21 // Loop through each interval to find the right interval
22 for (int[] interval : intervals) {
23 int left = 0, right = numIntervals - 1;
24 int intervalEnd = interval[1];
25
26 // Binary search to find the minimum start point >= interval's end point
27 while (left < right) {
28 int mid = (left + right) / 2;
29 if (startIndexPairs.get(mid)[0] >= intervalEnd) {
30 right = mid;
31 } else {
32 left = mid + 1;
33 }
34 }
35
36 // Check if the found start point is valid and set the result accordingly
37 result[resultIndex++] = startIndexPairs.get(left)[0] < intervalEnd ? -1 : startIndexPairs.get(left)[1];
38 }
39
40 // Return the populated result array
41 return result;
42 }
43}
44
1class Solution {
2public:
3 vector<int> findRightInterval(vector<vector<int>>& intervals) {
4 int n = intervals.size(); // The total number of intervals
5
6 // Vector of pairs to hold the start of each interval and its index
7 vector<pair<int, int>> startWithIndexPairs;
8 for (int i = 0; i < n; ++i) {
9 // Emplace back will construct the pair in-place
10 startWithIndexPairs.emplace_back(intervals[i][0], i);
11 }
12 // Sort the startWithIndexPairs array based on the interval starts
13 sort(startWithIndexPairs.begin(), startWithIndexPairs.end());
14
15 // This will hold the result; for each interval the index of the right interval
16 vector<int> result;
17
18 // Iterate over each interval to find the right interval
19 for (const auto& interval : intervals) {
20 int left = 0, right = n - 1; // Binary search bounds
21 int end = interval[1]; // The end of the current interval
22
23 // Perform a binary search to find the least start >= end
24 while (left < right) {
25 int mid = (left + right) / 2; // This avoids the overflow that (l+r)>>1 might cause
26 if (startWithIndexPairs[mid].first >= end)
27 right = mid; // We have found a candidate, try to find an earlier one
28 else
29 left = mid + 1; // Not a valid candidate, look further to the right
30 }
31
32 // Check if the found interval starts at or after the end of the current interval
33 // If not, append -1 to indicate there is no right interval
34 int index = (startWithIndexPairs[left].first >= end) ? startWithIndexPairs[left].second : -1;
35 result.push_back(index);
36 }
37
38 return result; // Return the populated result vector
39 }
40};
41
1function findRightInterval(intervals: number[][]): number[] {
2 // Get the total number of intervals
3 const intervalCount = intervals.length;
4
5 // Create an array to store the start points and their original indices
6 const startPoints = Array.from({ length: intervalCount }, () => new Array<number>(2));
7
8 // Fill the startPoints array with start points and their original indices
9 for (let i = 0; i < intervalCount; i++) {
10 startPoints[i][0] = intervals[i][0]; // Start point of interval
11 startPoints[i][1] = i; // Original index
12 }
13
14 // Sort the array of start points in ascending order
15 startPoints.sort((a, b) => a[0] - b[0]);
16
17 // Map each interval to the index of the interval with the closest start point that is greater than or equal to the end point of the current interval
18 return intervals.map(([_, end]) => {
19 let left = 0;
20 let right = intervalCount;
21
22 // Binary search to find the right interval
23 while (left < right) {
24 const mid = (left + right) >>> 1; // Equivalent to Math.floor((left + right) / 2)
25 if (startPoints[mid][0] < end) {
26 left = mid + 1;
27 } else {
28 right = mid;
29 }
30 }
31
32 // If left is out of bounds, return -1 to indicate no such interval was found
33 if (left >= intervalCount) {
34 return -1;
35 }
36
37 // Return the original index of the found interval
38 return startPoints[left][1];
39 });
40}
41
Time and Space Complexity
The time complexity of the provided code consists of two major operations: sorting the intervals
list and performing binary search using bisect_left
for each interval.
- Sorting the
intervals
list using thesort
method has a time complexity ofO(n log n)
, wheren
is the number of intervals. - Iterating over each interval and performing a binary search using
bisect_left
has a time complexity ofO(n log n)
since the binary search operation isO(log n)
and it is executedn
times, once for each interval.
Thus, the combined time complexity of these operations would be O(n log n + n log n)
. However, since both terms have the same order of growth, the time complexity simplifies to O(n log n)
.
The space complexity of the code is O(n)
for the following reasons:
- The
intervals
list is expanded to include the original index position of each interval, but the overall space required is still linearly proportional to the number of intervalsn
. - The
ans
list is created to store the result for each interval, which requiresO(n)
space. - Apart from the two lists mentioned above, no additional space that scales with the size of the input is used.
Therefore, the total space complexity is O(n)
.
Learn more about how to find time and space complexity quickly using problem constraints.
Which type of traversal does breadth first search do?
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
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Want a Structured Path to Master System Design Too? Donāt Miss This!