LeetCode 436: Find Right Interval

Problem Restatement

We are given a list of intervals.

Each interval is:

[start, end]

For each interval i, we need to find another interval j such that:

intervals[j][0] >= intervals[i][1]

In words, interval j must start at or after interval i ends.

Among all valid intervals, we need the one with the smallest start point.

Return the original index of that interval.

If no such interval exists, return -1 for that interval.

The problem also says every start point is unique, and i may equal j. (leetcode.com)

Input and Output

Example function shape:

def findRightInterval(intervals: list[list[int]]) -> list[int]:
    ...

Examples

Example 1:

intervals = [[1, 2]]

There is only one interval.

Its end is 2, but no interval starts at or after 2.

Answer:

[-1]

Example 2:

intervals = [[3, 4], [2, 3], [1, 2]]

For [3, 4], we need a start point at least 4.

No interval has that.

So answer at index 0 is -1.

For [2, 3], we need a start point at least 3.

The interval [3, 4] starts at 3, and its original index is 0.

So answer at index 1 is 0.

For [1, 2], we need a start point at least 2.

The interval [2, 3] starts at 2, and its original index is 1.

Answer:

[-1, 0, 1]

Example 3:

intervals = [[1, 4], [2, 3], [3, 4]]

For [1, 4], no interval starts at least 4.

For [2, 3], the interval [3, 4] starts at 3, so its index is 2.

For [3, 4], no interval starts at least 4.

Answer:

[-1, 2, -1]

First Thought: Check Every Interval

For each interval i, we can scan every interval j.

We check whether:

intervals[j][0] >= intervals[i][1]

Among all valid intervals, we keep the one with the smallest start.

This works, but it takes:

O(n^2)

because every interval scans all other intervals.

The constraint can be large, so we need a faster lookup.

Key Insight

For every interval, the only value we search for is:

end_i

We need the smallest start point that is greater than or equal to this value.

This is exactly a lower-bound search.

So we can:

1. Store all interval starts with their original indices.
2. Sort them by start.
3. For each interval end, binary search the first start that is at least that end.

For example:

intervals = [[3, 4], [2, 3], [1, 2]]

Store starts with original indices:

[(3, 0), (2, 1), (1, 2)]

Sort them:

[(1, 2), (2, 1), (3, 0)]

Now each query becomes binary search.

Algorithm

Create an array:

starts = []

For each interval at index i, append:

(start, i)

Sort starts.

Create the answer array:

answer = []

For each interval [start, end]:

1. Binary search in starts for the first pair whose start is at least end.
2. If found, append that pair’s original index.
3. Otherwise, append -1.

Python’s bisect_left can do the lower-bound search.

Correctness

The sorted starts array contains every interval start point paired with its original index.

For an interval i, a valid right interval must have:

start_j >= end_i

Among all such intervals, the required answer is the interval with the smallest possible start_j.

Because starts is sorted by start point, the first position with start at least end_i is exactly the smallest valid start.

Binary search finds exactly this first position.

If such a position exists, the stored original index is the correct answer for interval i.

If no such position exists, then every interval starts before end_i, so no right interval exists and the correct answer is -1.

Applying this independently to every interval gives the correct output array.

Complexity

Here, n is the number of intervals.

Implementation

from bisect import bisect_left

class Solution:
    def findRightInterval(self, intervals: list[list[int]]) -> list[int]:
        starts = []

        for i, (start, end) in enumerate(intervals):
            starts.append((start, i))

        starts.sort()

        answer = []

        for start, end in intervals:
            pos = bisect_left(starts, (end, -1))

            if pos == len(starts):
                answer.append(-1)
            else:
                answer.append(starts[pos][1])

        return answer

Code Explanation

We first collect all starts with their original indices:

starts.append((start, i))

This is necessary because sorting changes the order.

Then we sort:

starts.sort()

Now the starts are in ascending order.

For each interval, we binary search using its end:

pos = bisect_left(starts, (end, -1))

This finds the first pair whose start is at least end.

The -1 is used as the second tuple field. Since original indices are non-negative, (end, -1) comes before any tuple (end, index), so it correctly finds the first start equal to end when one exists.

If pos is outside the array:

if pos == len(starts):

then no interval starts at or after end, so we append -1.

Otherwise, we append the original index stored at that sorted position:

answer.append(starts[pos][1])

Testing

def run_tests():
    s = Solution()

    assert s.findRightInterval([[1, 2]]) == [-1]

    assert s.findRightInterval(
        [[3, 4], [2, 3], [1, 2]]
    ) == [-1, 0, 1]

    assert s.findRightInterval(
        [[1, 4], [2, 3], [3, 4]]
    ) == [-1, 2, -1]

    assert s.findRightInterval(
        [[1, 1], [3, 4], [2, 3]]
    ) == [0, -1, 1]

    assert s.findRightInterval(
        [[-10, -5], [-3, 0], [1, 2]]
    ) == [1, 2, -1]

    print("all tests passed")

run_tests()

Test meaning: