Find Right Interval

Medium
827.

Find Right Interval

Find Right Interval is a medium coding problem on arrays, sorting and binary search, asked in Amazon, Google and Nutanix interviews.

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.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} intervals
 * @return {number[]}
 */
var findRightInterval = function(intervals) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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.

Hints for Find Right Interval

  1. Hint 1

    Collect the starts together with their original indices and sort them.

  2. Hint 2

    For each interval, the answer is a lower-bound query on that sorted list.

  3. 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

  1. Build pairs (start_i, i) and sort them by start.
  2. For each i, binary search the first pair whose start is at least intervals[i][1].
  3. 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

Java

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