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.
This approach involves sorting the intervals by their starting times, then using binary search to quickly find the right interval for each end time.
The solution first defines a struct to store each interval with its start, end, and original index. The intervals are sorted based on start times. For each interval, binary search is used to find the smallest start that is greater than or equal to the end of the current interval. If no such interval exists, -1 is used.
C
Java
Python
C#
JavaScript
Time Complexity: O(n log n), due to sorting and binary search operations.
Space Complexity: O(n), for storing the intervals and the result.
This approach suggests sorting intervals based on their start times and then linearly scanning to determine possible matches for each interval's end.
This C solution uses simple sorting followed by a linear scan to determine the smallest index j where the start of interval j is greater than or equal to the end of interval i.
C
Java
Python
C#
JavaScript
Time Complexity: O(n^2) due to nested loops after sorting.
Space Complexity: O(n) for storing additional interval information.
We can store the start point and index of each interval into an array arr, and sort it by the start point. Then we iterate through the interval array, for each interval [_, ed], we can use binary search to find the first interval whose start point is greater than or equal to ed, which is its right-side interval. If found, we store its index into the answer array, otherwise, we store -1.
The time complexity is O(n times log n), and the space complexity is O(n). Where n is the length of the intervals.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Approach 1: Sort and Binary Search | Time Complexity: O(n log n), due to sorting and binary search operations. |
| Approach 2: Interval Sorting with Linear Scan | Time Complexity: O(n^2) due to nested loops after sorting. |
| Sorting + Binary Search | — |
| 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. |
Find Right Interval | LeetCode 436 | C++, Java, Python • Knowledge Center • 9,291 views views
Watch 9 more video solutions →Practice Find Right Interval with our built-in code editor and test cases.
Practice on FleetCode