Find Right Interval
MediumUpdated: Aug 2, 2025
Practice on:
Problem
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.
Examples
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.
Solution
Method 1 - Binary Search on Sorted Start Times
Intuition
For each interval, we want to find the interval with the smallest start time that is greater than or equal to its end time. By sorting the intervals by start time and using binary search, we can efficiently find the right interval for each query.
Approach
- Store the start times and their original indices.
- Sort the start times.
- For each interval, use binary search to find the smallest start time that is >= the end time.
- If found, record the index; otherwise, record -1.
Code
C++
class Solution {
public:
vector<int> findRightInterval(vector<vector<int>>& intervals) {
int n = intervals.size();
vector<pair<int, int>> starts;
for (int i = 0; i < n; ++i) {
starts.emplace_back(make_pair(intervals[i][0], i));
}
sort(starts.begin(), starts.end());
vector<int> res;
for (auto interval : intervals) {
int left = 0, right = n - 1;
int end = interval[1];
while (left < right) {
int mid = left + right >> 1;
if (starts[mid].first >= end)
right = mid;
else
left = mid + 1;
}
res.push_back(starts[left].first < end ? -1 : starts[left].second);
}
return res;
}
};
Go
func findRightInterval(intervals [][]int) []int {
n := len(intervals)
starts := make([][]int, n)
for i := 0; i < n; i++ {
starts[i] = make([]int, 2)
starts[i][0] = intervals[i][0]
starts[i][1] = i
}
sort.Slice(starts, func(i, j int) bool {
return starts[i][0] < starts[j][0]
})
var res []int
for _, interval := range intervals {
left, right, end := 0, n-1, interval[1]
for left < right {
mid := (left + right) >> 1
if starts[mid][0] >= end {
right = mid
} else {
left = mid + 1
}
}
val := -1
if starts[left][0] >= end {
val = starts[left][1]
}
res = append(res, val)
}
return res
}
Java
class Solution {
public int[] findRightInterval(int[][] intervals) {
int n = intervals.length;
List<int[]> starts = new ArrayList<>();
for (int i = 0; i < n; ++i) {
starts.add(new int[] {intervals[i][0], i});
}
starts.sort(Comparator.comparingInt(a -> a[0]));
int[] res = new int[n];
int i = 0;
for (int[] interval : intervals) {
int left = 0, right = n - 1;
int end = interval[1];
while (left < right) {
int mid = (left + right) >> 1;
if (starts.get(mid)[0] >= end) {
right = mid;
} else {
left = mid + 1;
}
}
res[i++] = starts.get(left)[0] < end ? -1 : starts.get(left)[1];
}
return res;
}
}
Kotlin
class Solution {
fun findRightInterval(intervals: Array<IntArray>): IntArray {
val n = intervals.size
val starts = Array(n) { intArrayOf(intervals[it][0], it) }
starts.sortBy { it[0] }
val res = IntArray(n)
for ((idx, interval) in intervals.withIndex()) {
var left = 0
var right = n - 1
val end = interval[1]
while (left < right) {
val mid = (left + right) shr 1
if (starts[mid][0] >= end) {
right = mid
} else {
left = mid + 1
}
}
res[idx] = if (starts[left][0] < end) -1 else starts[left][1]
}
return res
}
}
Python
class Solution:
def findRightInterval(self, intervals: List[List[int]]) -> List[int]:
for i, v in enumerate(intervals):
v.append(i)
intervals.sort()
n = len(intervals)
ans = [-1] * n
for _, e, i in intervals:
j = bisect_left(intervals, [e])
if j < n:
ans[i] = intervals[j][2]
return ans
Rust
impl Solution {
pub fn find_right_interval(intervals: Vec<Vec<i32>>) -> Vec<i32> {
let n = intervals.len();
let mut starts: Vec<(i32, usize)> = intervals.iter().enumerate().map(|(i, v)| (v[0], i)).collect();
starts.sort_by_key(|x| x.0);
let mut res = Vec::with_capacity(n);
for interval in &intervals {
let end = interval[1];
let mut left = 0;
let mut right = n - 1;
while left < right {
let mid = (left + right) / 2;
if starts[mid].0 >= end {
right = mid;
} else {
left = mid + 1;
}
}
if starts[left].0 < end {
res.push(-1);
} else {
res.push(starts[left].1 as i32);
}
}
res
}
}
TypeScript
function findRightInterval(intervals: number[][]): number[] {
const n = intervals.length;
const starts = Array.from({ length: n }).map(() => new Array<number>(2));
for (let i = 0; i < n; i++) {
starts[i][0] = intervals[i][0];
starts[i][1] = i;
}
starts.sort((a, b) => a[0] - b[0]);
return intervals.map(([_, target]) => {
let left = 0;
let right = n;
while (left < right) {
const mid = (left + right) >>> 1;
if (starts[mid][0] < target) {
left = mid + 1;
} else {
right = mid;
}
}
if (left >= n) {
return -1;
}
return starts[left][1];
});
}
Complexity
- ⏰ Time complexity:
O(n log n)- Sorting the intervals by start time takes
O(n log n). - For each interval, we perform a binary search in
O(log n), so total isO(n log n).
- Sorting the intervals by start time takes
- 🧺 Space complexity:
O(n)- We store the start times and indices in an auxiliary array of size
n.
- We store the start times and indices in an auxiliary array of size