Find Right Interval: Binary Search on Sorted Starts

LeetCode 436, Find Right Interval, gives you an array of intervals and asks you to find, for each interval, the interval whose start point is the smallest value that is still greater than or equal to that interval's end. If no such interval exists, you return -1 for that position.

Why this problem matters

At first glance, this looks like it might need nested loops: for each interval, scan all others to find the best match. That would be O(n^2), and it misses the key insight. The "right interval" depends only on start values, and start values can be sorted. Once sorted, you can binary search instead of scanning.

This problem sits at the intersection of two patterns that show up constantly in interviews: interval processing and binary search on a sorted structure. If you have practiced merge intervals and basic binary search separately, this problem is where those skills combine.

The trick is recognizing that you do not need to keep intervals together as pairs while searching. You can extract the start values, sort them, and binary search over just the starts. The original indices ride along so you can map back to the answer.

The approach

The strategy breaks into two phases:

1. Sort start values with their original indices. Create pairs of (start, index) and sort by start value. This gives you a sorted array you can binary search over.
2. For each interval, binary search for the smallest start that is >= its end. If found, record the original index. If not found, record -1.

The binary search is a classic "find the leftmost value satisfying a condition" pattern. You are looking for the smallest start value that is at least as large as the current interval's end.

import bisect

def findRightInterval(intervals):
    starts = sorted((iv[0], i) for i, iv in enumerate(intervals))
    keys = [s[0] for s in starts]
    result = []

    for _, end in intervals:
        pos = bisect.bisect_left(keys, end)
        if pos < len(starts):
            result.append(starts[pos][1])
        else:
            result.append(-1)

    return result

Step-by-step walkthrough

Let's trace through intervals = [[1,2],[2,3],[0,1],[3,4]]. First, we sort the start values: [0, 1, 2, 3] with original indices [2, 0, 1, 3]. Then for each interval, we binary search this sorted array for the smallest start that is >= the interval's end.

Each binary search takes O(log n) time. We run it once per interval, so the total search work is O(n log n). Combined with the O(n log n) sort, the overall time complexity stays at O(n log n).

Complexity analysis

The brute force approach compares every interval's end against every other interval's start. Sorting the starts and using binary search drops the per-query cost from O(n) to O(log n).

Space is O(n) for the sorted starts array and the result array.

Edge cases to watch for

• Single interval. If there is only one interval, the right interval for it is itself only if its start is >= its end. For an interval like [1,1], the answer is 0. For [1,2], the answer is -1 since 1 is not >= 2.
• All intervals are the same. If every interval is [1,2], then every interval's right interval is itself (start 1 is not >= end 2, so actually every answer would be -1). Think carefully about the condition.
• Intervals with start equal to end. An interval [3,3] has a right interval if any start is >= 3. It can even be its own right interval.
• No right interval exists for any entry. This happens when the maximum start value is less than the minimum end value.
• Already sorted input. The algorithm sorts starts regardless, so pre-sorted input does not change the approach.

The building blocks

Binary search for lower bound

The core operation here is bisect_left: find the leftmost position where a value could be inserted to maintain sorted order. This is the same as finding the smallest element >= a target. This building block appears in Binary Search, Find First and Last Position, and Search Insert Position. If you can write this from scratch, you can solve any "find the first element satisfying a condition" problem.

Sort with index tracking

Sorting data while preserving original positions is a common preprocessing step. You create tuples of (value, original_index), sort by value, and use the original index to map answers back. This same idea appears in problems like meeting room scheduling and event-based sweeps. It decouples the search structure from the original ordering.

From understanding to recall

You have seen how sorting starts and binary searching turns an O(n^2) problem into O(n log n). The logic is clean: sort starts, then for each end, find the leftmost start that is large enough. But in an interview, the details trip people up. Do you sort by start or by end? Do you use bisect_left or bisect_right? Do you search for the end value or something else?

These are exactly the kinds of small decisions that feel obvious when reading a solution but become confusing under time pressure. The way to lock this pattern in is to practice writing the solution from memory, not just reading it.

Related posts

• Merge Intervals - The foundational interval processing pattern that teaches sort-first thinking
• Insert Interval - Another interval problem where sorted order eliminates complexity
• Find First and Last Position of Element in Sorted Array - The binary search lower/upper bound pattern used in this solution