# Find Right Interval
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/find-right-interval)
Canonical: https://scaleengineer.com/dsa/problems/find-right-interval
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search), [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
---
## Problem
You are given an array of `intervals`, where `intervals[i] = [starti, endi]` and each `starti` is **unique**.

The **right interval** for an interval `i` is an interval `j` such that `startj >= endi` and `startj` is **minimized**. Note that `i` may equal `j`.

Return _an array of **right interval** indices for each interval `i`_. If no **right interval** exists for interval `i`, then put `-1` at index `i`.

**Example 1:**

**Input:** intervals = [[1,2]]
**Output:** [-1]
**Explanation:** There is only one interval in the collection, so it outputs -1.

**Example 2:**

**Input:** intervals = [[3,4],[2,3],[1,2]]
**Output:** [-1,0,1]
**Explanation:** There is no right interval for [3,4].
The right interval for [2,3] is [3,4] since start0 = 3 is the smallest start that is >= end1 = 3.
The right interval for [1,2] is [2,3] since start1 = 2 is the smallest start that is >= end2 = 2.

**Example 3:**

**Input:** intervals = [[1,4],[2,3],[3,4]]
**Output:** [-1,2,-1]
**Explanation:** There is no right interval for [1,4] and [3,4].
The right interval for [2,3] is [3,4] since start2 = 3 is the smallest start that is >= end1 = 3.

**Constraints:**

* `1 <= intervals.length <= 2 * 104`
* `intervals[i].length == 2`
* `-106 <= starti <= endi <= 106`
* The start point of each interval is **unique**.

# Approaches
## Brute Force
The brute-force approach is the most direct and intuitive way to solve the problem. For each interval in the input array, we perform a linear scan through the entire array to find a suitable 'right interval'. We keep track of the interval that satisfies the condition (`start_j >= end_i`) and has the minimum possible start time.
**Time:** O(N^2), where N is the number of intervals. The nested loops lead to a quadratic number of comparisons. · **Space:** O(N) to store the result array. If the space for the output is not considered, the space complexity is O(1).
**Pros:** Simple to understand and implement.; Requires minimal extra space (only for the result array).
**Cons:** Highly inefficient due to its O(N^2) time complexity.; Will likely result in a 'Time Limit Exceeded' error for large inputs as specified in the problem constraints.
### Explanation
In this method, we use two nested loops. The outer loop selects an interval `i` for which we need to find the right interval. The inner loop iterates through all intervals `j` in the list to find a candidate. A candidate `j` must have its start time `start_j` greater than or equal to the end time `end_i` of the interval `i`. Among all such valid candidates, we choose the one whose start time `start_j` is the smallest. We maintain a variable to keep track of this minimum start time and the index of the corresponding interval. If no such interval is found after checking all possibilities, the index remains -1.

```java
class Solution {
    public int[] findRightInterval(int[][] intervals) {
        int n = intervals.length;
        int[] result = new int[n];
        for (int i = 0; i < n; i++) {
            int minStart = Integer.MAX_VALUE;
            int minIndex = -1;
            for (int j = 0; j < n; j++) {
                if (intervals[j][0] >= intervals[i][1]) {
                    if (intervals[j][0] < minStart) {
                        minStart = intervals[j][0];
                        minIndex = j;
                    }
                }
            }
            result[i] = minIndex;
        }
        return result;
    }
}
```
### Algorithm
- Initialize a result array `ans` of size `n` (number of intervals) with `-1`.
- Iterate through each interval `i` from `0` to `n-1`.
- For each `i`, initialize `min_start` to a very large value (e.g., `Integer.MAX_VALUE`) and `min_index` to `-1`.
- Start a nested loop to iterate through every interval `j` from `0` to `n-1`.
- Check if the start of interval `j` is greater than or equal to the end of interval `i` (`intervals[j][0] >= intervals[i][1]`).
- If it is, check if this start is smaller than the current `min_start`.
- If `intervals[j][0] < min_start`, update `min_start` to `intervals[j][0]` and `min_index` to `j`.
- After the inner loop completes, `min_index` will hold the index of the right interval for `i`.
- Assign `ans[i] = min_index`.
- After the outer loop completes, return the `ans` array.

## Two Pointers with Sorting
A more optimized approach involves sorting. By sorting the start and end points of the intervals separately while retaining their original indices, we can find the right intervals efficiently. We can then use a two-pointer technique to match each end point with its corresponding smallest valid start point in a single pass over the sorted arrays.
**Time:** O(N log N). The sorting of two arrays of size N dominates the time complexity. The subsequent two-pointer scan is O(N). · **Space:** O(N) for storing the `starts` and `ends` arrays, plus the result array.
**Pros:** Significantly more efficient than the brute-force approach with O(N log N) time complexity.; The two-pointer scan is very fast (linear time) after the initial sorting.
**Cons:** Requires sorting two separate arrays, which might have a higher constant factor in its time complexity compared to a single sort.; Uses more auxiliary space than the binary search approach due to needing two extra arrays for sorting.
### Explanation
The core idea is to process the end points in increasing order. For the smallest end point, we find the smallest start point that is greater than or equal to it. For the next smallest end point, we don't need to restart our search for a start point from the beginning; we can continue from where we left off. This is the essence of the two-pointer approach.

First, we decouple the start and end points from the intervals, creating two lists of pairs: `(start_value, original_index)` and `(end_value, original_index)`. We sort both lists. Then, we iterate through the sorted `ends` list with a pointer `i` and the sorted `starts` list with a pointer `j`. For each `end` at `ends[i]`, we advance `j` until `starts[j]` is a valid right interval. Because `starts` is sorted, this `starts[j]` is guaranteed to be the one with the minimum start time. We then record this match and move to the next end point `ends[i+1]`, continuing the search for `j` from its current position.

```java
import java.util.Arrays;
import java.util.Comparator;

class Solution {
    public int[] findRightInterval(int[][] intervals) {
        int n = intervals.length;
        int[][] starts = new int[n][2];
        int[][] ends = new int[n][2];

        for (int i = 0; i < n; i++) {
            starts[i][0] = intervals[i][0];
            starts[i][1] = i;
            ends[i][0] = intervals[i][1];
            ends[i][1] = i;
        }

        Arrays.sort(starts, Comparator.comparingInt(a -> a[0]));
        Arrays.sort(ends, Comparator.comparingInt(a -> a[0]));

        int[] result = new int[n];
        Arrays.fill(result, -1);

        int j = 0;
        for (int i = 0; i < n; i++) {
            while (j < n && starts[j][0] < ends[i][0]) {
                j++;
            }
            if (j < n) {
                result[ends[i][1]] = starts[j][1];
            }
        }
        return result;
    }
}
```
### Algorithm
- Create two 2D arrays, `starts` and `ends`, of size `n`. Each element will store a pair `[value, original_index]`.
- Populate `starts` with `[intervals[i][0], i]` and `ends` with `[intervals[i][1], i]` for all `i` from `0` to `n-1`.
- Sort the `starts` array based on the start values in ascending order.
- Sort the `ends` array based on the end values in ascending order.
- Initialize a result array `ans` of size `n` and fill it with `-1`.
- Use two pointers: `i` for the `ends` array and `j` for the `starts` array, both starting at `0`.
- Iterate through the sorted `ends` array with pointer `i`.
- For each `ends[i]`, advance pointer `j` in the `starts` array until `starts[j][0] >= ends[i][0]`.
- Once such a `j` is found, `starts[j]` is the best candidate for `ends[i]` because both arrays are sorted. The original index of the right interval is `starts[j][1]`.
- Store the result: `ans[ends[i][1]] = starts[j][1]`.
- If `j` reaches the end of the `starts` array, no right interval exists for the current and subsequent `ends`.
- Return the `ans` array.

## Sorting and Binary Search
This is one of the most efficient approaches. The main bottleneck in the brute-force method is the search for the minimum `start_j`. We can optimize this search significantly. By first sorting all the start points of the intervals, we can use binary search to find the required `start_j` for each interval's `end_i` in logarithmic time.
**Time:** O(N log N). Sorting the `startPoints` array takes O(N log N). The loop runs N times, and each binary search takes O(log N), contributing another O(N log N). The total complexity is O(N log N). · **Space:** O(N) to store the `startPoints` array for sorting and the result array.
**Pros:** Very efficient with O(N log N) time complexity.; Generally faster in practice than the two-pointer approach as it involves only one major sort operation followed by N fast binary searches.
**Cons:** The implementation of binary search to find the lower bound requires careful handling of pointers and conditions.
### Explanation
To implement this, we first need to store the original indices of the intervals because sorting will change their order. We can create an auxiliary array, say `startPoints`, where each element is a pair containing an interval's start time and its original index. We then sort this `startPoints` array based on the start times.

After sorting, we iterate through each interval `i` of the original input array. For each interval's end time `end_i`, we perform a binary search on the sorted `startPoints` array. The goal of the binary search is to find the smallest start time that is greater than or equal to `end_i`. This is a classic 'lower bound' search. If we find such a start time, we retrieve its associated original index from `startPoints` and store it in our result array at index `i`. If the binary search completes without finding such a start time (e.g., `end_i` is larger than all start times), we store -1.

```java
import java.util.Arrays;
import java.util.Comparator;

class Solution {
    public int[] findRightInterval(int[][] intervals) {
        int n = intervals.length;
        int[][] startPoints = new int[n][2];
        for (int i = 0; i < n; i++) {
            startPoints[i][0] = intervals[i][0];
            startPoints[i][1] = i;
        }

        Arrays.sort(startPoints, Comparator.comparingInt(a -> a[0]));

        int[] result = new int[n];
        for (int i = 0; i < n; i++) {
            int targetEnd = intervals[i][1];
            
            // Binary search for the lower bound
            int low = 0, high = n - 1;
            int foundIndex = -1;
            
            while (low <= high) {
                int mid = low + (high - low) / 2;
                if (startPoints[mid][0] >= targetEnd) {
                    foundIndex = startPoints[mid][1];
                    high = mid - 1; // Try to find an even better (smaller) start on the left
                } else {
                    low = mid + 1;
                }
            }
            result[i] = foundIndex;
        }
        return result;
    }
}
```
### Algorithm
- Create a 2D array `startPoints` of size `n` to store pairs of `[start_value, original_index]`.
- Populate this array by iterating through the input `intervals`.
- Sort the `startPoints` array based on the `start_value`.
- Initialize a result array `ans` of size `n`.
- Iterate through the original `intervals` array from `i = 0` to `n-1`.
- For each interval `i`, take its end time `targetEnd = intervals[i][1]`.
- Perform a binary search on the sorted `startPoints` array to find the first element whose start value is greater than or equal to `targetEnd`.
- The binary search should be tailored to find the 'lower bound' or 'ceiling'.
- If the binary search finds a valid element at index `k` in `startPoints`, its original index is `startPoints[k][1]`. Set `ans[i] = startPoints[k][1]`.
- If no such element is found (i.e., `targetEnd` is larger than all start times), the binary search will indicate failure. In this case, set `ans[i] = -1`.
- Return the `ans` array.

# Solutions
### Java

```java
class Solution {
public
  int[] findRightInterval(int[][] intervals) {
    int n = intervals.length;
    List<int[]> starts = new ArrayList<>();
    for (int i = 0; i < n; ++i) {
      starts.add(new int[]{intervals[i][0], i});
    }
    starts.sort(Comparator.comparingInt(a->a[0]));
    int[] res = new int[n];
    int i = 0;
    for (int[] interval : intervals) {
      int left = 0, right = n - 1;
      int end = interval[1];
      while (left < right) {
        int mid = (left + right) >> 1;
        if (starts.get(mid)[0] >= end) {
          right = mid;
        } else {
          left = mid + 1;
        }
      }
      res[i++] = starts.get(left)[0] < end ? -1 : starts.get(left)[1];
    }
    return res;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> findRightInterval(vector<vector<int>> &intervals) {
    int n = intervals.size();
    vector<pair<int, int>> starts;
    for (int i = 0; i < n; ++i) {
      starts.emplace_back(make_pair(intervals[i][0], i));
    }
    sort(starts.begin(), starts.end());
    vector<int> res;
    for (auto interval : intervals) {
      int left = 0, right = n - 1;
      int end = interval[1];
      while (left < right) {
        int mid = left + right >> 1;
        if (starts[mid].first >= end)
          right = mid;
        else
          left = mid + 1;
      }
      res.push_back(starts[left].first < end ? -1 : starts[left].second);
    }
    return res;
  }
};

```

### Python

```python
class Solution:
    def findRightInterval(self, intervals: List[List[int]]) -> List[int]: for i, v in enumerate(intervals): v . append(i) intervals . sort() n = len(intervals) ans = [- 1] * n for _, e, i in intervals: j = bisect_left(intervals, [e]) if j < n: ans[i] = intervals[j][2] return ans

```