436. Find Right Interval - Solution

The problem

You are given an array of intervals, where intervals[i] = [start_i, end_i] and each start_i is unique.

The right interval for an interval i is an interval j such that start_j >= end_i and start_j 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 start₀ = 3 is the smallest start that is >= end₁ = 3.
The right interval for [1,2] is [2,3] since start₁ = 2 is the smallest start that is >= end₂ = 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 start₂ = 3 is the smallest start that is >= end₁ = 3.

Constraints:

1 <= intervals.length <= 2 * 10⁴
intervals[i].length == 2
-10⁶ <= start_i <= end_i <= 10⁶
The start point of each interval is unique.

Approach overview

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

Approach 1: Approach 1: Sort and Binary Search

This approach involves sorting the intervals by their starting times, then using binary search to quickly find the right interval for each end time.

Python

from sortedcontainers import SortedDict

def findRightInterval(intervals):
    n = len(intervals)
    result = [-1] * n
    sorted_map = SortedDict({intervals[i][0]: i for i in range(n)})
    
    for i in range(n):
        idx = sorted_map.bisect_left(intervals[i][1])
        if idx < len(sorted_map):
            result[i] = sorted_map.peekitem(idx)[1]
    
    return result

Java

import java.util.*;

class Solution {
    public int[] findRightInterval(int[][] intervals) {
        TreeMap<Integer, Integer> map = new TreeMap<>();
        int n = intervals.length;
        for (int i = 0; i < n; i++) {
            map.put(intervals[i][0], i);
        }
        int[] result = new int[n];
        for (int i = 0; i < n; i++) {
            Integer key = map.ceilingKey(intervals[i][1]);
            result[i] = key != null ? map.get(key) : -1;
        }
        return result;
    }
}

JavaScript

var findRightInterval = function(intervals) {
    const map = new Map();
    intervals.forEach(([start], idx) => map.set(start, idx));
    const starts = Array.from(map.keys()).sort((a, b) => a - b);
    const result = new Array(intervals.length).fill(-1);
    intervals.forEach(([, end], idx) => {
        let left = 0, right = starts.length - 1;
        while (left <= right) {
            const mid = Math.floor((left + right) / 2);
            if (starts[mid] >= end) right = mid - 1;
            else left = mid + 1;
        }
        if (left < starts.length) result[idx] = map.get(starts[left]);
    });
    return result;
};

#include <stdio.h>
#include <stdlib.h>

struct Interval {
    int start;
    int end;
    int index;
};

int compare(const void* a, const void* b) {
    return ((struct Interval*)a)->start - ((struct Interval*)b)->start;
}

int binarySearch(struct Interval* intervals, int size, int target) {
    int left = 0, right = size - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (intervals[mid].start >= target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return left < size ? intervals[left].index : -1;
}

int* findRightInterval(int** intervalsArr, int intervalsSize, int* outArrSize){
    struct Interval* intervals = malloc(sizeof(struct Interval) * intervalsSize);
    for (int i = 0; i < intervalsSize; i++) {
        intervals[i].start = intervalsArr[i][0];
        intervals[i].end = intervalsArr[i][1];
        intervals[i].index = i;
    }
    qsort(intervals, intervalsSize, sizeof(struct Interval), compare);
    int* result = malloc(sizeof(int) * intervalsSize);
    for (int i = 0; i < intervalsSize; i++) {
        result[i] = binarySearch(intervals, intervalsSize, intervalsArr[i][1]);
    }
    *outArrSize = intervalsSize;
    free(intervals);
    return result;
}

// Add main function for testing if needed

using System;
using System.Collections.Generic;

public class Solution {
    public int[] FindRightInterval(int[][] intervals) {
        int n = intervals.Length;
        var map = new SortedDictionary<int, int>();
        for (int i = 0; i < n; i++) {
            map[intervals[i][0]] = i;
        }
        int[] result = new int[n];
        for (int i = 0; i < n; i++) {
            var ceiling = map.Keys.FirstOrDefault(key => key >= intervals[i][1]);
            result[i] = ceiling != default(int) ? map[ceiling] : -1;
        }
        return result;
    }
}

In this Python solution, SortedDict is used to sort and store interval start times and their indices. For each interval, bisect_left is used to find the appropriate right interval efficiently.

Complexity

Time Complexity: O(n log n). Sorting and bisect operations contribute to this complexity.
Space Complexity: O(n) for the SortedDict.

Try this approach in the editor

Approach 2: Approach 2: Interval Sorting with Linear Scan

This approach suggests sorting intervals based on their start times and then linearly scanning to determine possible matches for each interval's end.

Python

def findRightInterval(intervals):
    indexed_intervals = sorted((e[0], i) for i, e in enumerate(intervals))
    result = []
    for i, (start, end) in enumerate(intervals):
        possible_intervals = [idx for s, idx in indexed_intervals if s >= end]
        if possible_intervals:
            result.append(possible_intervals[0])
        else:
            result.append(-1)
    return result

Java

import java.util.*;

class Solution {
    public int[] findRightInterval(int[][] intervals) {
        int n = intervals.length;
        Integer[] idx = new Integer[n];
        for(int i = 0; i < n; i++) idx[i] = i;
        Arrays.sort(idx, (a, b) -> Integer.compare(intervals[a][0], intervals[b][0]));
        int[] res = new int[n];
        for (int i = 0; i < n; i++) {
            res[i] = -1;
            for(int j = i + 1; j < n; j++) {
                if (intervals[idx[j]][0] >= intervals[i][1]) {
                    res[i] = idx[j];
                    break;
                }
            }
        }
        return res;
    }
}

JavaScript

var findRightInterval = function(intervals) {
    const indexedIntervals = intervals.map((interval, index) => ({...interval, index}));
    indexedIntervals.sort((a, b) => a.start - b.start);
    const result = [];
    for (const {end} of intervals) {
        let foundIndex = -1;
        for (const {start, index} of indexedIntervals) {
            if (start >= end) {
                foundIndex = index;
                break;
            }
        }
        result.push(foundIndex);
    }
    return result;
};

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int start;
    int end;
    int index;
} Interval;

int compare(const void* a, const void* b) {
    return ((Interval*)a)->start - ((Interval*)b)->start;
}

int* findRightInterval(int** intervals, int intervalsSize, int* outArrSize) {
    Interval *arr = (Interval *)malloc(sizeof(Interval) * intervalsSize);
    for (int i = 0; i < intervalsSize; i++) {
        arr[i].start = intervals[i][0];
        arr[i].end = intervals[i][1];
        arr[i].index = i;
    }

    qsort(arr, intervalsSize, sizeof(Interval), compare);

    int* result = (int *)malloc(sizeof(int) * intervalsSize);
    for (int i = 0; i < intervalsSize; i++) {
        result[arr[i].index] = -1;
        for (int j = i + 1; j < intervalsSize; j++) {
            if (arr[j].start >= arr[i].end) {
                result[arr[i].index] = arr[j].index;
                break;
            }
        }
    }

    free(arr);
    *outArrSize = intervalsSize;
    return result;
}

using System;

public class Solution {
    public int[] FindRightInterval(int[][] intervals) {
        int n = intervals.Length;
        int[] result = new int[n];
        int[,] sortedIntervals = new int[n, 2];
        for (int i = 0; i < n; i++) {
            sortedIntervals[i, 0] = intervals[i][0];
            sortedIntervals[i, 1] = i;
        }
        Array.Sort(sortedIntervals, (a, b) => a[0].CompareTo(b[0]));
        for (int i = 0; i < n; i++) {
            result[i] = -1;
            for (int j = 0; j < n; j++) {
                if (sortedIntervals[j, 0] >= intervals[i][1]) {
                    result[i] = sortedIntervals[j, 1];
                    break;
                }
            }
        }
        return result;
    }
}

This Python implementation sorts the intervals by start and then checks each end against the sorted list of starts to find minimal valid index, using a list comprehension method.

Complexity

Time Complexity: O(n^2), although Python's sort is O(n log n), the list comprehension can make it O(n^2) for the worst case.
Space Complexity: O(n).

Try this approach in the editor

Approach 3: Sorting + Binary Search

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.

C++

class Solution {
public:
    vector<int> findRightInterval(vector<vector<int>>& intervals) {
        int n = intervals.size();
        vector<pair<int, int>> arr;
        for (int i = 0; i < n; ++i) {
            arr.emplace_back(intervals[i][0], i);
        }
        sort(arr.begin(), arr.end());
        vector<int> ans;
        for (auto& e : intervals) {
            int j = lower_bound(arr.begin(), arr.end(), make_pair(e[1], -1)) - arr.begin();
            ans.push_back(j == n ? -1 : arr[j].second);
        }
        return ans;
    }
};

TypeScript

function findRightInterval(intervals: number[][]): number[] {
    const n = intervals.length;
    const arr: number[][] = Array.from({ length: n }, (_, i) => [intervals[i][0], i]);
    arr.sort((a, b) => a[0] - b[0]);
    return intervals.map(([_, ed]) => {
        let [l, r] = [0, n];
        while (l < r) {
            const mid = (l + r) >> 1;
            if (arr[mid][0] >= ed) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l < n ? arr[l][1] : -1;
    });
}

func findRightInterval(intervals [][]int) (ans []int) {
	arr := make([][2]int, len(intervals))
	for i, v := range intervals {
		arr[i] = [2]int{v[0], i}
	}
	sort.Slice(arr, func(i, j int) bool { return arr[i][0] < arr[j][0] })
	for _, e := range intervals {
		j := sort.Search(len(arr), func(i int) bool { return arr[i][0] >= e[1] })
		if j < len(arr) {
			ans = append(ans, arr[j][1])
		} else {
			ans = append(ans, -1)
		}
	}
	return
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Approach 1: Sort and Binary Search	Time Complexity: O(n log n). Sorting and bisect operations contribute to this complexity. Space Complexity: O(n) for the SortedDict.
Approach 2: Interval Sorting with Linear Scan	Time Complexity: O(n^2), although Python's sort is O(n log n), the list comprehension can make it O(n^2) for the worst case. Space Complexity: O(n).
Sorting + Binary Search	–

Complexity analysis

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.

Frequently asked questions

Is Find Right Interval easy or hard?

Find Right Interval is classified as a Medium difficulty problem. The challenge lies in recognizing that sorting interval starts enables efficient binary search instead of scanning all intervals.

Find Right Interval Python/Java solution

In Python or Java, the standard implementation stores interval starts with indices, sorts them, and applies binary search for each interval's end value. This results in O(n log n) time and O(n) extra space.

How to solve Find Right Interval in O(n)?

A strict O(n) solution is not possible because intervals must be ordered by start values to locate the next valid interval efficiently. The closest practical approach is sorting followed by a linear scan using two pointers, which runs in O(n log n) due to the sorting step.

What is the best approach for Find Right Interval?

The most common solution sorts interval start points and uses binary search to find the smallest start >= each interval's end. This runs in O(n log n) time and O(n) space. It is straightforward and commonly expected in coding interviews.

Is Find Right Interval asked at Google/Amazon/Meta?

Interval search and binary search problems appear frequently in interviews at companies like Google, Amazon, and Meta. Variants of this problem test understanding of interval processing, sorting, and efficient lookups.

What data structure is used in Find Right Interval?

The typical solution uses arrays or lists combined with sorting and binary search. Some implementations store pairs of (start, original index) to preserve the original interval positions after sorting.

What is the time complexity of Find Right Interval?

The optimal time complexity is O(n log n). Sorting the interval starts takes O(n log n), and each interval performs a binary search in O(log n). The overall complexity remains O(n log n) with O(n) additional space.

Find Right Interval solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Sort and Binary Search

Approach 2: Approach 2: Interval Sorting with Linear Scan

Approach 3: Sorting + Binary Search

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Find Right Interval solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Sort and Binary Search

Approach 2: Approach 2: Interval Sorting with Linear Scan

Approach 3: Sorting + Binary Search

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems