LeetCode 436: Find Right Interval Solution in Python – A Step-by-Step Guide

What Is LeetCode 436: Find Right Interval?

In LeetCode 436: Find Right Interval, you’re given a list of intervals—each a pair of start and end times (e.g., [[1,2], [2,3], [0,1]])—and your task is to return an array where, for each interval, you identify the index of the interval whose start time is the smallest value greater than or equal to the current interval’s end time. If no such interval exists, return -1. It’s like finding the next event that can follow each one on a timeline, based on when they start.

Problem Statement

• Input: intervals (List[List[int]])—a list of [start, end] pairs.
• Output: List[int]—for each interval, the index of the “right interval” or -1.
• Rules:
• For interval [start_i, end_i], find j where start_j ≥ end_i with the smallest start_j.
• If multiple intervals qualify, any index is fine (we’ll pick the leftmost).
• If no such j exists, return -1.

Constraints

• 1 <= intervals.length <= 2000.
• intervals[i].length == 2.
• -10^6 <= start_i <= end_i <= 10^6.
• Start times may not be unique.

Examples to Kick Things Off

• Input: intervals = [[1,2],[2,3],[0,1]]
• Output: [1, -1, 0]
• [1,2] → end=2, [2,3] starts at 2 ≥ 2, index 1.
• [2,3] → end=3, no start ≥ 3, -1.
• [0,1] → end=1, [1,2] starts at 1 ≥ 1, index 0.
• Input: intervals = [[3,4],[2,3],[1,2]]
• Output: [-1, 0, 1]
• [3,4] → end=4, no start ≥ 4, -1.
• [2,3] → end=3, [3,4] starts at 3 ≥ 3, index 0.
• [1,2] → end=2, [2,3] starts at 2 ≥ 2, index 1.
• Input: intervals = [[1,4],[2,3],[3,4]]
• Output: [-1, 2, -1].

Understanding the Problem: Finding the Next Runner

To solve LeetCode 436: Find Right Interval in Python, we need to match each interval’s end time to the smallest start time that’s at least as big, while tracking original indices. A naive approach—checking every interval for each end time—would be O(n²), too slow for up to 2000 intervals. Instead, we’ll use:

• Best Solution (Binary Search): O(n log n) time, O(n) space—fast and scalable.
• Alternative Solution (Brute Force): O(n²) time, O(1) space—simple but inefficient.

Let’s dive into the binary search solution—it’s the star of this relay race.

Best Solution: Binary Search with Sorted Start Times

Why This Is the Best Solution

The binary search approach shines because it cuts the search time from O(n) to O(log n) per interval, yielding O(n log n) total time with O(n) space. By sorting start times and using binary search, we quickly find the next valid start for each end time. It’s like having a sorted roster of runners and instantly picking the next one up after each finish—efficient and smart!

How It Works

Here’s the playbook:

• Step 1: Create a list of (start, index) pairs and sort by start time.
• Step 2: For each interval’s end time:
• Binary search the sorted starts to find the smallest start ≥ end.
• Return its original index, or -1 if none found.
• Step 3: Build the result array.
• Why It Works:
• Sorting lets us use binary search to jump to the right spot.
• Preserving indices ensures we map back correctly.

Step-by-Step Example

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

• Setup:
• Starts: [(1,0), (2,1), (0,2)] → Sorted: [(0,2), (1,0), (2,1)].
• Result array: [?, ?, ?].
• Process:
• [1,2], end=2:
• Binary search: [(0,2), (1,0), (2,1)] → 2 ≥ 2 at index 1.
• Result[0] = 1.
• [2,3], end=3:
• Binary search: No start ≥ 3.
• Result[1] = -1.
• [0,1], end=1:
• Binary search: 1 ≥ 1 at index 0.
• Result[2] = 0.
• Result: [1, -1, 0].

Code with Detailed Line-by-Line Explanation

Here’s the Python code, broken down for clarity:

Copy codeclass Solution:
    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:
        # Step 1: Pair start times with original indices and sort
        start_times = [(interval[0], i) for i, interval in enumerate(intervals)]
        start_times.sort()  # Sort by start time

        # Step 2: Result array
        result = [-1] * len(intervals)

        # Step 3: For each interval, find right interval
        for i, (start, end) in enumerate(intervals):
            # Binary search for smallest start >= end
            left, right = 0, len(start_times) - 1
            while left <= right:
                mid = (left + right) // 2
                if start_times[mid][0] >= end:
                    result[i] = start_times[mid][1]  # Found a candidate
                    right = mid - 1  # Look for smaller start
                else:
                    left = mid + 1

        return result

• Line 3-4: Build and sort (start, index) pairs (e.g., [[1,2],[2,3]] → [(1,0), (2,1)]).
• Line 7: Initialize result with -1s (default if no right interval).
• Line 10-18: For each interval:
• Get end time (e.g., [1,2] → end=2).
• Binary search:
• If mid’s start ≥ end, record index, search left for smaller.
• If mid’s start < end, search right.
• Left pointer stops at first valid index or beyond array.
• Line 20: Return result.
• Time Complexity: O(n log n)—sorting + n binary searches.
• Space Complexity: O(n)—start_times and result.

It’s like a high-speed baton pass with pinpoint accuracy!

Alternative Solution: Brute Force Iteration

Why an Alternative Approach?

The brute force method checks every interval against each end time—O(n²) time, O(1) space (excluding output). It’s slower but dead simple, making it a good starting point or fallback when you’re brainstorming. It’s like manually scanning the roster for each runner’s handoff—exhaustive but effective.

How It Works

• Step 1: For each interval’s end time:
• Scan all intervals to find the smallest start ≥ end.
• Track the best index.
• Step 2: Build result array with indices or -1.

Step-by-Step Example

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

• Process:
• [1,2], end=2:
• Check: [1,2] (1<2), [2,3] (2≥2), [0,1] (0<2) → index 1.
• [2,3], end=3:
• Check: [1,2] (1<3), [2,3] (2<3), [0,1] (0<3) → no start ≥ 3, -1.
• [0,1], end=1:
• Check: [1,2] (1≥1), [2,3] (2>1), [0,1] (0<1) → index 0.
• Result: [1, -1, 0].

Code for Brute Force

Copy codeclass Solution:
    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:
        result = [-1] * len(intervals)

        for i in range(len(intervals)):
            end = intervals[i][1]
            min_start = float('inf')
            min_idx = -1
            # Scan all intervals
            for j in range(len(intervals)):
                if intervals[j][0] >= end and intervals[j][0] < min_start:
                    min_start = intervals[j][0]
                    min_idx = j
            result[i] = min_idx

        return result

• Time Complexity: O(n²)—nested loops.
• Space Complexity: O(1)—just the result array.

It gets the job done, but it’s a slog.

Comparing the Two Solutions

• Binary Search (Best):
• Pros: O(n log n), fast, scalable.
• Cons: O(n) space, slightly trickier.
• Brute Force (Alternative):
• Pros: O(n²), simple, no sorting.
• Cons: Slow for large inputs.

Binary search laps brute force.

Edge Cases and More Examples

• Input: [[1,1]] → [0] (self is valid).
• Input: [[1,2]] → [-1] (no other interval).
• Input: [[1,3],[1,2]] → [0, 0].

Both handle these cleanly.

Complexity Recap

• Binary Search: Time O(n log n), Space O(n).
• Brute Force: Time O(n²), Space O(1).

Binary search is the winner.

Key Takeaways

• Binary Search: Speed through sorting and searching.
• Brute Force: Slow but steady.
• Python Tip: Master binary search—see [Python Basics](/python/basics).

Final Thoughts: Pass That Baton

LeetCode 436: Find Right Interval in Python is a relay race of intervals, and binary search is your star runner. Brute force plods along, but it’s a solid warm-up. Want more interval action? Try LeetCode 252: Meeting Rooms or LeetCode 435: Non-overlapping Intervals. Ready to find those right intervals? Hit Solve LeetCode 436 on LeetCode and race to the finish today—your coding skills are ready to shine!