Find Right Interval — Binary Search on Sorted Start Points

Problem Statement#

You are given an array of intervals, where intervals[i] = [start_i, end_i] and each start_i is unique. For each interval i, find the index of the right interval for it — the interval with the smallest start that is greater than or equal to end_i. Return -1 if no such right interval exists.

Constraints:

• 1 <= intervals.length <= 2 * 10^4
• intervals[i].length == 2
• -10^6 <= start_i <= end_i <= 10^6
• Each start_i is unique.

Examples:

Example 1:
Input: intervals = [[1,2]]
Output: [-1]
Explanation: There is only one interval, so it has no right interval.
 
Example 2:
Input: intervals = [[3,4],[2,3],[1,2]]
Output: [-1, 0, 1]
Explanation:
  Interval 0 [3,4]: need start >= 4. None → -1.
  Interval 1 [2,3]: need start >= 3. [3,4] has start=3. Index 0.
  Interval 2 [1,2]: need start >= 2. [2,3] has start=2. Index 1.
 
Example 3:
Input: intervals = [[1,4],[2,3],[3,4]]
Output: [-1,2,-1]

Why This Problem Matters#

Find Right Interval is a focused medium problem that tests a critical skill: performing binary search on a sorted projection of data while preserving the original indices. This pattern — sort by attribute A to enable fast lookup, but remember original indices to answer questions about attribute B — appears constantly in interview problems.

Google includes this type of problem because it tests data organization skills. The naive approach (for each interval, scan all others to find the best right interval) is O(n²). The optimal approach reduces it to O(n log n) by sorting start points into a lookup structure, then binary searching for each query.

The problem also introduces candidates to the coordinate compression + binary search pattern, which is a building block for more complex problems like "Count of Smaller Numbers After Self," "Minimum Interval to Include Each Query," and "Skyline Problem."

A particularly valuable skill tested here is implementing the binary search correctly for a "smallest value greater than or equal to target" query — the classic lower bound search. Many candidates struggle to implement this cleanly without bugs.

The Core Insight#

All start points are unique. So you can:

1. Build a sorted list of (start_value, original_index) pairs.
2. For each interval i with end = end_i, binary search in the sorted starts for the smallest start ≥ end_i (lower bound search).
3. If found, return the corresponding original index. Otherwise return -1.

The binary search target: find the leftmost position in the sorted starts array where start >= end_i. This is a standard lower_bound operation.

Why does sorting work? Start points are unique, so there's no ambiguity in the mapping start → original_index. The sorted list gives us O(log n) lookup instead of O(n) scan.

Visual Dry Run#

intervals = [[3,4],[2,3],[1,2]]
 
Step 1: Build sorted starts with original indices.
  (start=3, idx=0), (start=2, idx=1), (start=1, idx=2)
  Sorted: [(1,2), (2,1), (3,0)]
  start_vals = [1, 2, 3]
 
Step 2: For each interval, binary search.
  Interval 0 [3,4], end=4:
    lower_bound(start_vals, 4) = position 3 (past end). → -1.
  
  Interval 1 [2,3], end=3:
    lower_bound(start_vals, 3) = position 2. starts[2] = (3, idx=0). → 0.
  
  Interval 2 [1,2], end=2:
    lower_bound(start_vals, 2) = position 1. starts[1] = (2, idx=1). → 1.
 
Result: [-1, 0, 1]. ✓

Solution (Optimal)#

import bisect
 
def findRightInterval(intervals):
    # Create sorted list of (start, original_index)
    starts = sorted((s, i) for i, (s, _) in enumerate(intervals))
    
    # Extract just the start values for binary search
    start_vals = [s for s, _ in starts]
    
    result = []
    for _, end in intervals:
        # Find leftmost start >= end
        pos = bisect.bisect_left(start_vals, end)
        
        if pos < len(starts):
            result.append(starts[pos][1])  # original index
        else:
            result.append(-1)
    
    return result

function findRightInterval(intervals) {
    const n = intervals.length;
    
    // Build sorted array of [start, originalIndex]
    const starts = intervals
        .map(([s, _], i) => [s, i])
        .sort((a, b) => a[0] - b[0]);
    
    const result = [];
    
    for (const [, end] of intervals) {
        // Binary search: find leftmost start >= end
        let lo = 0, hi = n;
        while (lo < hi) {
            const mid = (lo + hi) >> 1;
            if (starts[mid][0] < end) lo = mid + 1;
            else hi = mid;
        }
        
        result.push(lo < n ? starts[lo][1] : -1);
    }
    
    return result;
}

Complexity Analysis:

• Time: O(n log n) — O(n log n) to sort starts, O(log n) per binary search for n intervals
• Space: O(n) — for the sorted starts array

Common Mistakes#

• Using bisect_right instead of bisect_left. bisect_left finds the leftmost position where the value could be inserted, which gives the first element ≥ target. bisect_right gives the first position where the element would be inserted to the right, which skips exact matches.
• Binary search condition < end vs <= end. For "smallest start ≥ end," the condition should be start < end → go right. Using <= would skip exact matches.
• Not checking bounds after binary search. If pos >= len(starts), no interval has start ≥ end. Return -1.
• Sorting by end instead of start. The lookup structure must be sorted by start, since you're searching for starts ≥ end.
• Forgetting that start_i values are unique. This guarantees no ties in the sorted starts array, making the binary search unambiguous.

Follow-up Questions#

1. What if start points were not unique? How would ties affect the binary search and index lookup?
2. Find the left interval for each interval (largest end ≤ start_i). How does the algorithm change?
3. What if you want to find all intervals whose start is in range [end_i, end_i + k]? How do you extend the binary search?
4. Implement this using a sorted map (TreeMap in Java) instead of a sorted array. What's the complexity?
5. Can you solve this online (answering each query as it arrives) in the same time complexity? (Yes — the sorted starts structure is built upfront.)
6. Generalize: given intervals and queries (l, r), find all intervals whose start is in [l, r]. How?

Key Takeaways#

• Build a sorted list of (start, original_index) pairs then use bisect_left to find the smallest start that is >= each interval's end — a clean lower-bound binary search.
• All start points are unique (guaranteed by constraints), so the mapping start -> original_index is unambiguous.
• Time is O(n log n): O(n log n) to sort, O(log n) per binary search for n intervals.
• Use bisect_left not bisect_right — exact matches should count as valid right intervals.
• Always check pos < len(starts) after binary search; if pos >= len, no right interval exists and you return -1.
• This "sort by attribute A to binary search, return index of original position" pattern recurs in Time Based Key-Value Store and Maximum Profit in Job Scheduling.
• Google tests this to check whether candidates can preserve original indices through a sorted projection — a fundamental data organization skill.