Problem Description

You are given an array of intervals where each interval is represented as intervals[i] = [start_i, end_i]. Each starting point start_i is unique across all intervals.

For each interval i, you need to find its "right interval". A right interval for interval i is defined as an interval j that satisfies two conditions:

1. The start point of interval j must be greater than or equal to the end point of interval i (i.e., start_j >= end_i)
2. Among all intervals satisfying condition 1, interval j should have the minimum possible start point

Note that an interval can be its own right interval if its start point is greater than or equal to its own end point.

Your task is to return an array where each element at index i contains the index of the right interval for intervals[i]. If no right interval exists for a particular interval, put -1 at that position in the result array.

For example, if you have intervals [[1,2], [2,3], [0,1]]:

• For interval [1,2] at index 0, its right interval is [2,3] at index 1 (since 2 >= 2)
• For interval [2,3] at index 1, there's no interval with start >= 3, so the answer is -1
• For interval [0,1] at index 2, its right interval is [1,2] at index 0 (since 1 >= 1)

The output would be [1, -1, 0].

Intuition

The key insight is that we need to efficiently find, for each interval's end point, the smallest start point that is greater than or equal to it. This naturally suggests a searching problem.

If we had all the start points sorted in ascending order, we could use binary search to quickly find the smallest start point that meets our criteria. For any given end point ed, we want to find the leftmost position in the sorted array where a start point is >= ed.

However, there's a complication: we need to return the original indices of the intervals, not just the start points. So we can't just sort the start points alone - we need to keep track of which interval each start point belongs to.

This leads us to the approach of creating pairs of (start_point, original_index) and sorting these pairs by start point. Now when we search for a right interval:

1. We take each interval's end point
2. Use binary search on our sorted array to find the first start point >= end
3. If found, we retrieve the original index that was paired with that start point
4. If not found (binary search returns a position beyond the array), we return -1

The binary search specifically looks for the leftmost position where we could insert (ed, -inf) while maintaining sorted order. Using -inf as the second element ensures that if there are multiple intervals with the same start point as ed, we get the leftmost one. This gives us the interval with the minimum start point that satisfies our condition.

Solution Approach

Let's walk through the implementation step by step:

Step 1: Create and Sort the Array

First, we create an array arr that stores pairs of (start_point, original_index) for each interval:

arr = sorted((st, i) for i, (st, _) in enumerate(intervals))

• We enumerate through intervals to get both the index i and the interval [st, ed]
• We only care about the start point st for sorting, so we ignore the end point using _
• Each element in arr becomes a tuple (start_point, original_index)
• The array is sorted by start points in ascending order

Step 2: Initialize the Answer Array

We create an answer array initialized with -1 values:

ans = [-1] * n

This handles the default case where no right interval exists.

Step 3: Find Right Intervals Using Binary Search

For each interval, we find its right interval:

for i, (_, ed) in enumerate(intervals):
    j = bisect_left(arr, (ed, -inf))
    if j < n:
        ans[i] = arr[j][1]

Breaking this down:

• We iterate through the original intervals array with its indices
• For each interval, we only need its end point ed to find the right interval
• bisect_left(arr, (ed, -inf)) performs binary search to find the leftmost position where we could insert (ed, -inf)
  • Since arr is sorted by the first element of each tuple, this finds the first interval with start >= ed
  • Using -inf as the second element ensures that if there's an interval with start == ed, we'll find it
• The binary search returns an index j in the sorted array
• If j < n, a valid right interval exists:
  • arr[j] gives us the tuple (start_point, original_index)
  • arr[j][1] extracts the original index
  • We store this original index in ans[i]
• If j >= n, no right interval exists, and ans[i] remains -1

Time Complexity: O(n log n) where n is the number of intervals

• Sorting takes O(n log n)
• For each of the n intervals, we perform binary search which takes O(log n)
• Total: O(n log n) + O(n * log n) = O(n log n)

Space Complexity: O(n) for storing the sorted array and answer array

Example Walkthrough

Let's walk through the solution with a concrete example: intervals = [[3,4], [2,3], [1,2]]

Step 1: Create and Sort the Array

First, we create pairs of (start_point, original_index):

• Interval at index 0: [3,4] → (3, 0)
• Interval at index 1: [2,3] → (2, 1)
• Interval at index 2: [1,2] → (1, 2)

After sorting by start points:

arr = [(1, 2), (2, 1), (3, 0)]

Step 2: Initialize Answer Array

ans = [-1, -1, -1]

Step 3: Find Right Intervals

For interval at index 0: [3,4]

• End point = 4
• Binary search for (4, -inf) in arr
• All start points (1, 2, 3) are < 4, so bisect_left returns index 3
• Since 3 >= len(arr), no right interval exists
• ans[0] remains -1

For interval at index 1: [2,3]

• End point = 3
• Binary search for (3, -inf) in arr
• The first start point >= 3 is at position 2: (3, 0)
• j = 2, which is < 3, so we found a valid right interval
• arr[2][1] = 0, so ans[1] = 0
• This means interval at index 0 [3,4] is the right interval for [2,3]

For interval at index 2: [1,2]

• End point = 2
• Binary search for (2, -inf) in arr
• The first start point >= 2 is at position 1: (2, 1)
• j = 1, which is < 3, so we found a valid right interval
• arr[1][1] = 1, so ans[2] = 1
• This means interval at index 1 [2,3] is the right interval for [1,2]

Final Result: [-1, 0, 1]

This tells us:

• [3,4] has no right interval (no interval starts at or after 4)
• [2,3]'s right interval is [3,4] (starts at 3, which is >= 3)
• [1,2]'s right interval is [2,3] (starts at 2, which is >= 2)

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × log n)

The time complexity is dominated by two main operations:

1. Sorting the array arr with n elements, which takes O(n × log n) time
2. For each of the n intervals, performing a binary search using bisect_left on the sorted array, which takes O(log n) per search, resulting in O(n × log n) total

Since both operations have the same complexity of O(n × log n), the overall time complexity is O(n × log n).

Space Complexity: O(n)

The space complexity comes from:

1. The ans list which stores n elements: O(n)
2. The arr list which stores n tuples of (start, index): O(n)

The total auxiliary space used is O(n) + O(n) = O(n), where n is the length of the intervals.

Common Pitfalls

Pitfall 1: Using Wrong Comparison Value in Binary Search

The Problem: A common mistake is using just the end value for binary search instead of a tuple:

# WRONG approach
position = bisect_left(sorted_starts, end)  # This won't work correctly!

This fails because sorted_starts contains tuples (start, index), not just integers. Python will attempt to compare an integer with a tuple, which either raises an error or produces incorrect results.

The Solution: Always use a tuple with the same structure for comparison:

# CORRECT approach
position = bisect_left(sorted_starts, (end, float('-inf')))

Using float('-inf') as the second element ensures that if multiple intervals have the same start time equal to end, we get the leftmost one.

Pitfall 2: Forgetting to Store Original Indices

The Problem: After sorting the intervals, developers might forget that we need to return the original indices, not the sorted positions:

# WRONG approach
sorted_intervals = sorted(intervals)
# ... binary search ...
result[i] = j  # j is the position in sorted array, not original index!

The Solution: Always pair each interval's start point with its original index before sorting:

# CORRECT approach
sorted_starts = sorted((start, idx) for idx, (start, _) in enumerate(intervals))
# ... binary search ...
result[i] = sorted_starts[j][1]  # Extract the original index

Pitfall 3: Incorrect Handling of Self-Referencing Intervals

The Problem: Some might think an interval cannot be its own right interval and add extra checks:

# UNNECESSARY complexity
if j < n and sorted_starts[j][1] != i:  # Wrong - an interval CAN be its own right interval
    result[i] = sorted_starts[j][1]

The Solution: The problem states that an interval can be its own right interval if start >= end. No special handling needed:

# CORRECT approach - let the binary search handle it naturally
if j < n:
    result[i] = sorted_starts[j][1]

For example, interval [3, 2] has itself as its right interval since 3 >= 2.