Watch 10 video solutions for Find Right Interval, a medium level problem involving Array, Binary Search, Sorting. This walkthrough by Knowledge Center has 9,291 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 106Problem Overview: Each interval has a start and end. For every interval i, you need the index of another interval whose start >= end[i] and whose start is the smallest possible among such intervals. If no such interval exists, return -1 for that position.
Approach 1: Sort and Binary Search (Time: O(n log n), Space: O(n))
The key observation: you only care about interval start values when searching for the "right" interval. Extract all starts along with their original indices and sort them. For each interval, perform a binary search to find the smallest start value that is >= current end. The sorted array makes this search efficient. After locating the candidate position, return the stored original index; if the search goes past the array, the answer is -1. Sorting takes O(n log n), and you run n binary searches each in O(log n), keeping total time at O(n log n). This method heavily relies on sorting and binary search over interval start points.
Approach 2: Interval Sorting with Linear Scan (Time: O(n log n), Space: O(n))
Another approach sorts intervals twice: once by start and once by end. Maintain two pointers while scanning both sorted lists. Move through the intervals sorted by end, and advance the pointer in the start-sorted list until you find the first start that satisfies start >= end. Because both lists are sorted, the pointer never moves backward, giving a single linear sweep after sorting. This approach avoids repeated binary searches and instead performs a controlled two-pointer scan. The total runtime is dominated by the sorting step O(n log n), followed by a linear pass O(n). It is a good demonstration of how sorted data can turn repeated lookups into a single scan using techniques common in array processing.
Recommended for interviews: The sort + binary search solution is what most interviewers expect. It directly models the problem as "find the smallest start >= end" and shows you know how to combine sorting with binary search efficiently. The two-pointer scan is also solid and can be slightly cleaner once both lists are sorted, but binary search is usually the first approach candidates reach for.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sort Starts + Binary Search | O(n log n) | O(n) | Standard solution. Best when you want fast lookups for each interval independently. |
| Sort Intervals + Linear Scan (Two Pointers) | O(n log n) | O(n) | Good when processing intervals sequentially after sorting and avoiding repeated binary searches. |