LeetCode 436 - Find Right Interval

This problem asks us to find, for each interval in a list, the "right interval" that starts at or after the end of the current interval and is the closest such interval in terms of starting time.

leetcodemediumarraybinary-searchsorting

LeetCode Problem 436

Difficulty: 🟡 Medium
Topics: Array, Binary Search, Sorting

Solution

Problem Understanding

This problem asks us to find, for each interval in a list, the "right interval" that starts at or after the end of the current interval and is the closest such interval in terms of starting time. Formally, given an array of intervals intervals[i] = [starti, endi] where each starti is unique, the right interval for an interval i is an interval j such that startj >= endi and startj is minimized. If no such interval exists, we return -1 for that interval.

The input is a list of intervals where each interval consists of two integers [start, end]. The expected output is an array of indices corresponding to the original positions of the right intervals. For example, if the right interval for the interval at index i is at index j in the original array, the output array at position i should contain j.

Constraints give important hints about the scale and nature of the input. The number of intervals can go up to 20,000, and start points are unique, which is important because it allows us to use them as keys for mapping or sorting. The large input size indicates that a naive approach that checks every pair of intervals would be too slow.

Edge cases that could trip up a naive implementation include intervals with no right interval (should return -1), intervals that are already sorted by start, reverse-sorted intervals, and intervals that have the same end but different start times.

Approaches

A brute-force approach is straightforward. For each interval, we could iterate through all other intervals and look for the interval with the smallest start value that is greater than or equal to the current interval's end. This guarantees correctness because we are explicitly checking all possibilities. However, its time complexity is O(n²), which is too slow for n up to 20,000.

The optimal solution takes advantage of sorting and binary search. The key insight is that we can sort the intervals by their start times and then, for each interval, perform a binary search to quickly find the smallest start that is greater than or equal to its end. This reduces the time complexity significantly because binary search is O(log n) for each interval.

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(1) Check all pairs of intervals for each interval
Optimal O(n log n) O(n) Sort intervals by start and use binary search for each interval

Algorithm Walkthrough

  1. Store the original indices of each interval because sorting will change their order. Create a list of tuples (start, index) for all intervals.
  2. Sort this list based on the start values. This allows binary search to work efficiently.
  3. Initialize a result array filled with -1 because some intervals may have no right interval.
  4. Iterate through each interval in the original list. For each interval, perform a binary search on the sorted start list to find the smallest start that is greater than or equal to the interval's end.
  5. If the binary search finds a valid index, update the result array at the original interval's index with the found interval's original index.
  6. Return the result array.

Why it works: Sorting ensures that the starts are in increasing order, which allows binary search to find the smallest start greater than or equal to a target efficiently. By keeping track of original indices, we ensure that the output corresponds to the original input order. The algorithm guarantees that for each interval, if a right interval exists, it will be found, otherwise -1 is returned.

Python Solution

from typing import List
import bisect

class Solution:
    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:
        n = len(intervals)
        start_with_index = [(intervals[i][0], i) for i in range(n)]
        start_with_index.sort()  # Sort by start times
        
        result = [-1] * n
        
        for i, (start, end) in enumerate(intervals):
            idx = bisect.bisect_left(start_with_index, (end, 0))
            if idx < n:
                result[i] = start_with_index[idx][1]
        
        return result

Implementation Walkthrough: We first map each interval to its start and original index and sort by start. For each interval, bisect_left finds the insertion point where the end of the interval could fit in the sorted list. If this index is within bounds, it gives the smallest start that is >= end. The result array is updated using the original indices to maintain alignment with the input.

Go Solution

import "sort"

func findRightInterval(intervals [][]int) []int {
    n := len(intervals)
    startWithIndex := make([][2]int, n)
    for i := 0; i < n; i++ {
        startWithIndex[i] = [2]int{intervals[i][0], i}
    }
    sort.Slice(startWithIndex, func(i, j int) bool {
        return startWithIndex[i][0] < startWithIndex[j][0]
    })
    
    result := make([]int, n)
    for i := range result {
        result[i] = -1
    }
    
    for i := 0; i < n; i++ {
        end := intervals[i][1]
        l, r := 0, n
        for l < r {
            m := l + (r-l)/2
            if startWithIndex[m][0] >= end {
                r = m
            } else {
                l = m + 1
            }
        }
        if l < n {
            result[i] = startWithIndex[l][1]
        }
    }
    
    return result
}

Go-specific Notes: Go does not have a built-in binary search for custom keys, so we implement it manually. We use [2]int tuples for (start, index). Slice initialization and bounds checks ensure safety.

Worked Examples

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

After creating start_with_index: [(3,0),(2,1),(1,2)]

After sorting: [(1,2),(2,1),(3,0)]

Iterate through each interval:

Interval End Binary Search Index Right Interval Index Result So Far
[3,4] 4 3 -1 [-1]
[2,3] 3 2 0 [-1,0]
[1,2] 2 1 1 [-1,0,1]

Complexity Analysis

Measure Complexity Explanation
Time O(n log n) Sorting takes O(n log n), and binary search for each interval takes O(log n), so overall O(n log n)
Space O(n) Storing start and index tuples requires O(n), and the result array also takes O(n)

The algorithm is efficient for up to 20,000 intervals because it avoids the O(n²) brute-force search.

Test Cases

# test cases
assert Solution().findRightInterval([[1,2]]) == [-1]  # Single interval
assert Solution().findRightInterval([[3,4],[2,3],[1,2]]) == [-1,0,1]  # Reverse sorted
assert Solution().findRightInterval([[1,4],[2,3],[3,4]]) == [-1,2,-1]  # Mixed intervals
assert Solution().findRightInterval([[1,1],[3,4]]) == [0,-1]  # Zero-length interval
assert Solution().findRightInterval([[1,1000000],[2,3],[4,5]]) == [-1,2,-1]  # Large end value
Test Why
Single interval Validates that the function returns -1 when no right interval exists
Reverse sorted Tests correct handling of non-sorted input
Mixed intervals Confirms correct binary search mapping for overlapping intervals
Zero-length interval Ensures intervals where start=end are handled
Large end value Checks handling of extreme values within constraints

Edge Cases

A key edge case is when there is only one interval. The function must return -1 because there is no other interval to consider. Another edge case is when intervals have ends that do not match any start in the array. This is handled by initializing the result array to -1 and only updating it if a valid right interval is found. A third edge case involves intervals with very large ranges or negative values. Sorting and binary search are robust to these values as long as the integer representation is valid. All these edge cases are correctly handled by the optimal algorithm.