Find Right Interval — Medium Problem & Solution

intervals[i] = [starti, endi] and all starts are distinct. The right interval of i is the interval j whose start is the smallest value at least endi…

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 <= 20000
intervals[i].length == 2
-1000000 <= start_i <= end_i <= 1000000
All starts are distinct.

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 least intervals[i][1].
Write that pair's original index, or -1 when 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 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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue