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:
- The start of interval
j(intervals[j][0]) is greater than or equal to the end of intervali(intervals[i][1]). - 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: up to 20,000. This suggests that an solution will likely time out (roughly operations), so we need something closer to .
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 because we do a linear scan for every element. Given the constraints (), this will almost certainly exceed time limits in Python or C++.
The core operation here is: “Find the smallest value .”
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
- Preparation: Create a new list containing tuples of
(start_time, original_index)for every interval inintervals. - 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. - 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_timesfrom 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. - 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 astart_time >= end_iexists 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 positioni. - Otherwise, keep
-1.
- Get its
Complexity Analysis
- Time:
- Sorting the intervals by start time takes .
- We perform a binary search for each of the intervals. Binary search is per query. Total loop cost: .
- Overall Time Complexity: . This fits comfortably within limits for .
- Space:
- We store a list of tuples and an auxiliary array for start times. Both scale linearly with input size.
- Overall Space Complexity: (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_leftreturns an index equal to or greater than the length ofsorted_starts, it means no interval satisfiesstart >= end. The code leaves-1in place (initialized value), which is correct. - Exact Match: Since we use
bisect_left, if there exists a start time exactly equal toend_val, it will be included as the right interval, satisfying the conditionstart_j >= end_i. This matches problem requirements. - Empty Input: Constraints state , but logic holds regardless (returns empty list).
- Negative Coordinates: The values can range from to . Python handles arbitrary integer sizes, so overflow is not an issue here. Binary search works correctly on negative integers as well.