Domain 2MediumCORE

Find Right Interval

We have a list of intervals where each interval is defined as [starti, endi]. A crucial constraint here is that every start value across all intervals is unique.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#FAANG asked: 0

436. Find Right Interval

Model: qwen3.5:9b
Topics:
FAANG asked: 0
Acceptance rate: 48.6%


Problem Breakdown

We have a list of intervals where each interval is defined as [start_i, end_i]. A crucial constraint here is that every start value across all intervals is unique.

For every single interval in the input array (let’s call it index i), we need to find another interval at some index j such that:

  1. The start of interval j (intervals[j][0]) is greater than or equal to the end of interval i (intervals[i][1]).
  2. Among all intervals satisfying condition #1, we want the one with the smallest valid start time (minimized).

If no such interval exists for a given i, we return -1. The output must be an array of indices corresponding to each input position in order.

Key constraints: NN up to 20,000. This suggests that an O(N2)O(N^2) solution will likely time out (roughly 4⋅1084 \cdot 10^8 operations), so we need something closer to O(Nlog⁡N)O(N \log N).

Intuition

If I were solving this without thinking about complexity first, the brute force approach would be: for each interval i, iterate through every other interval j and check if start_j >= end_i. Keep track of the minimum valid start found. This is O(N2)O(N^2) because we do a linear scan for every element. Given the constraints (N=2⋅104N=2 \cdot 10^4), this will almost certainly exceed time limits in Python or C++.

The core operation here is: “Find the smallest value ≥X\ge X.” This pattern immediately signals Binary Search. To use binary search, we need a sorted collection. The input isn’t guaranteed to be sorted by start times. So, our first step must be sorting based on the start values of all intervals while preserving their original indices (since the output requires us to return the original index).

Once we have a list of starts in ascending order, for each interval’s end time, we can binary search this sorted list to find the insertion point. The first element at or after that position is our candidate right interval. If the insertion point goes past the array bounds, no such interval exists.

Approach

  1. Preparation: Create a new list containing tuples of (start_time, original_index) for every interval in intervals.
  2. Sorting: Sort this prepared list based on start_time (the first element of the tuple). Since start times are unique, we don’t need to worry about tie-breaking logic during sorting; Python’s default sort handles tuples lexicographically anyway.
  3. Extraction for Binary Search: To make binary search cleaner and avoid complex key arguments in some languages or environments, I’ll extract just a list of the start_times from our sorted structure into a separate array (or use bisect on the tuple list with careful comparison). For this solution, extracting start times is efficient enough.
  4. Querying: Iterate through each interval in the original input order:
    • Get its end_i.
    • Use binary search (bisect_left) to find the first index where a start_time >= end_i exists in our sorted list of starts.
    • If such an element is found, record its corresponding original_index (which we stored during sorting) into our result array at position i.
    • Otherwise, keep -1.

Complexity Analysis

  • Time:
    • Sorting the intervals by start time takes O(Nlog⁡N)O(N \log N).
    • We perform a binary search for each of the NN intervals. Binary search is O(log⁡N)O(\log N) per query. Total loop cost: O(Nlog⁡N)O(N \log N).
    • Overall Time Complexity: O(Nlog⁡N)O(N \log N). This fits comfortably within limits for N=20,000N=20,000.
  • Space:
    • We store a list of tuples and an auxiliary array for start times. Both scale linearly with input size.
    • Overall Space Complexity: O(N)O(N) (excluding output space).

Solution

import bisect

def findRightInterval(intervals):
    n = len(intervals)
    
    # Result array initialized to -1, as we assume no right interval initially
    result = [-1] * n
    
    # Create a list of (start_time, original_index). 
    # We need the index because bisect will give us position in sorted list, not input order.
    starts_with_idx = []
    for i in range(n):
        start_val = intervals[i][0]
        ends_at_i = intervals[i][1]  # Not needed here but good to note context
        
        # We store (start_time, original_index) so we can sort by time and retrieve index later.
        starts_with_idx.append((intervals[i][0], i))
    
    # Sort based on start times. Since starts are unique, this is deterministic.
    starts_with_idx.sort() 
    
    # Extract just the start values to use with bisect_left cleanly. 
    # This avoids tuple comparison overhead/complexity during search logic.
    sorted_starts = [item[0] for item in starts_with_idx]
    
    # For each interval, find its right neighbor using binary search on sorted_starts
    for i in range(n):
        end_val = intervals[i][1]
        
        # bisect_left finds the first index where start >= end_val. 
        # If multiple existed (not possible here due to unique constraint), it picks leftmost.
        idx_in_sorted = bisect.bisect_left(sorted_starts, end_val)
        
        # Check if we found a valid interval within bounds
        if idx_in_sorted < n:
            result[i] = starts_with_idx[idx_in_sorted][1]
            
    return result

# Example usage (uncomment to test locally):
# print(findRightInterval([[3,4],[2,3],[1,2]])) # Output: [-1, 0, 1]

Edge Cases Handled

  • No Right Interval: If bisect_left returns an index equal to or greater than the length of sorted_starts, it means no interval satisfies start >= end. The code leaves -1 in place (initialized value), which is correct.
  • Exact Match: Since we use bisect_left, if there exists a start time exactly equal to end_val, it will be included as the right interval, satisfying the condition start_j >= end_i. This matches problem requirements.
  • Empty Input: Constraints state N≥1N \ge 1, but logic holds regardless (returns empty list).
  • Negative Coordinates: The values can range from −106-10^6 to 10610^6. Python handles arbitrary integer sizes, so overflow is not an issue here. Binary search works correctly on negative integers as well.