Find Right Interval — Solution in Python, Java & C++
Find Right Interval solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Find Right Interval is a medium coding problem on arrays, sorting and binary search, asked in Amazon, Google and Nutanix interviews.
- Difficulty: Medium
- Topics: Arrays, Sorting, Binary Search
- Asked at: Amazon, Google, Nutanix
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
intervals[i] = [start_i, end_i] and all starts are distinct.
The right interval of i is the interval j whose start is the smallest value at least end_i (possibly i itself). Return an array whose i-th entry is that index, or -1 if no such interval exists.
Example 1
Input: intervals = [[1,2]]
Output: [-1]
Explanation: No interval starts at or after 2.
Example 2
Input: intervals = [[3,4],[2,3],[1,2]]
Output: [-1,0,1]
Explanation: For [2,3] the smallest start at least 3 is 3, at index 0.
Example 3
Input: intervals = [[1,4],[2,3],[3,4]]
Output: [-1,2,-1]
Constraints
1 <= intervals.length <= 20000intervals[i].length == 2-1000000 <= start_i <= end_i <= 1000000All starts are distinct.
Hints for Find Right Interval
Hint 1
Collect the starts together with their original indices and sort them.
Hint 2
For each interval, the answer is a lower-bound query on that sorted list.
Hint 3
The original index has to travel with the start, or the answer refers to the wrong interval.
How to solve Find Right Interval
Sort the starts once, keeping each one paired with the index it came from. Then each query is a lower bound: the first start at least end_i.
Approach
- Build pairs
(start_i, i)and sort them by start. - For each
i, binary search the first pair whose start is at leastintervals[i][1]. - Write that pair's original index, or
-1when the search runs past the end.
Why it works
Starts are distinct, so the sorted list has a unique first element at or above any threshold, and the lower bound finds it. Carrying the original index through the sort is what lets the answer be reported in terms of the input's ordering — the sorted position is not the answer.
Complexity
- Time —
O(n log n) - Space —
O(n)
Pitfalls
- Returning the sorted position instead of the original index.
- Using a strict
>misses the case where an interval's own start equals its end. - An interval can be its own right interval when
start_i == end_i.
Reference solution
Python
from typing import List
def findRightInterval(intervals: List[List[int]]) -> List[int]:
n = len(intervals)
starts = sorted((iv[0], i) for i, iv in enumerate(intervals))
out = [-1] * n
for i, iv in enumerate(intervals):
end = iv[1]
lo, hi = 0, n
while lo < hi:
mid = (lo + hi) // 2
if starts[mid][0] >= end:
hi = mid
else:
lo = mid + 1
out[i] = -1 if lo == n else starts[lo][1]
return outJava
public static int[] findRightInterval(int[][] intervals) {
int n = intervals.length;
int[][] starts = new int[n][2];
for (int i = 0; i < n; i++) {
starts[i][0] = intervals[i][0];
starts[i][1] = i;
}
Arrays.sort(starts, (a, b) -> Integer.compare(a[0], b[0]));
int[] out = new int[n];
for (int i = 0; i < n; i++) {
int end = intervals[i][1];
int lo = 0, hi = n;
while (lo < hi) {
int mid = (lo + hi) >>> 1;
if (starts[mid][0] >= end) hi = mid; else lo = mid + 1;
}
out[i] = lo == n ? -1 : starts[lo][1];
}
return out;
}C++
vector<int> findRightInterval(vector<vector<int>>& intervals) {
int n = (int) intervals.size();
vector<pair<int, int>> starts(n);
for (int i = 0; i < n; i++) starts[i] = make_pair(intervals[i][0], i);
sort(starts.begin(), starts.end());
vector<int> out(n, -1);
for (int i = 0; i < n; i++) {
int end = intervals[i][1];
int lo = 0, hi = n;
while (lo < hi) {
int mid = (lo + hi) / 2;
if (starts[mid].first >= end) hi = mid; else lo = mid + 1;
}
out[i] = lo == n ? -1 : starts[lo].second;
}
return out;
}JavaScript
var findRightInterval = function(intervals) {
var n = intervals.length;
var starts = [];
for (var t = 0; t < n; t++) starts.push([intervals[t][0], t]);
starts.sort(function(a, b) { return a[0] - b[0]; });
var out = [];
for (var i = 0; i < n; i++) {
var end = intervals[i][1];
var lo = 0, hi = n;
while (lo < hi) {
var mid = (lo + hi) >> 1;
if (starts[mid][0] >= end) hi = mid; else lo = mid + 1;
}
out.push(lo === n ? -1 : starts[lo][1]);
}
return out;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sorting Algorithms