Scale Engineer

Find Right Interval

Med
#0423Time: 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).
Algorithms
Binary SearchSorting
Data structures
Array

Prompt

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

3 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

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;    }}

Complexity

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).

Trade-offs

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.

Solutions

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;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem