You are given an array of intervals, where intervals[i] = [starti, endi] and each starti is unique.
The right interval for an interval i is an interval j such that startj >= endi and startj is minimized. Note that i may equal j.
Return an array of right interval indices for each interval i. If no right interval exists for interval i, then put -1 at index i.
Example 1:
Input: intervals = [[1,2]] Output: [-1] Explanation: There is only one interval in the collection, so it outputs -1.
Example 2:
Input: intervals = [[3,4],[2,3],[1,2]] Output: [-1,0,1] Explanation: There is no right interval for [3,4]. The right interval for [2,3] is [3,4] since start0 = 3 is the smallest start that is >= end1 = 3. The right interval for [1,2] is [2,3] since start1 = 2 is the smallest start that is >= end2 = 2.
Example 3:
Input: intervals = [[1,4],[2,3],[3,4]] Output: [-1,2,-1] Explanation: There is no right interval for [1,4] and [3,4]. The right interval for [2,3] is [3,4] since start2 = 3 is the smallest start that is >= end1 = 3.
Constraints:
1 <= intervals.length <= 2 * 104intervals[i].length == 2-106 <= starti <= endi <= 106In #436 Find Right Interval, each interval requires finding another interval whose start value is greater than or equal to the current interval’s end. The goal is to return the index of the smallest such start value, or -1 if no suitable interval exists.
A common strategy is to separate and sort interval start points while keeping track of their original indices. After sorting, you can efficiently search for the smallest start that is greater than or equal to a given end using binary search. For every interval, perform a binary search over the sorted starts to locate the closest valid right interval.
This approach avoids checking all pairs of intervals and reduces the search time significantly. Sorting enables fast lookups, while binary search ensures efficient querying for each interval.
The overall time complexity is O(n log n) due to sorting and repeated binary searches, with O(n) additional space used for storing start points and indices.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Sorting + Binary Search | O(n log n) | O(n) |
Knowledge Center
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, interval-based problems like Find Right Interval are common in technical interviews at FAANG and other top tech companies. They test understanding of sorting, binary search, and efficient searching techniques on structured data.
Binary search is used to efficiently locate the smallest start value that is greater than or equal to a given end value. Since the start points are sorted, binary search reduces lookup time from linear to logarithmic, improving overall performance.
The optimal approach uses sorting and binary search. By sorting all interval start points and keeping their original indices, you can quickly locate the smallest start that is greater than or equal to a given interval's end. Binary search helps perform this lookup efficiently for each interval.
A sorted array or list of interval start points paired with their indices works well for this problem. This structure allows binary search to efficiently find the next valid start value. Some implementations may also use a TreeMap or balanced BST for similar behavior.