algoadvance

Leetcode 436. Find Right Interval

Problem Statement

Given a collection of intervals, find the interval that starts right after the end of each interval. In other words, for each interval i, you need to find an interval j such that start_j is the smallest start point that is greater than or equal to the end point of interval i. If no such interval j exists, return -1 for interval i.

Clarifying Questions

  1. Q: Can the intervals overlap?
    • A: Yes, intervals may overlap.
  2. Q: What should be returned if there are multiple intervals with the same start time?
    • A: Return the one with the smallest index.
  3. Q: Can intervals be empty or is the input always guaranteed to have at least one interval?
    • A: The input is guaranteed to have at least one interval.
  4. Q: What should be the format of the output?
    • A: Return an array where the i-th element is the index of the right interval for the i-th interval in the input, or -1 if no such interval exists.

Strategy

  1. Store Intervals with Original Indices:
    • Create an array of tuples where each tuple contains the start time, end time, and original index of each interval.
  2. Sort by Start Time:
    • Sort the array of tuples by their start times. This helps efficiently find the right interval for each end time using binary search.
  3. Binary Search:
    • For each original interval’s end time, use binary search to find the smallest start time that is greater than or equal to the end time in the sorted list.
  4. Output Construction:
    • Construct the output array where the i-th element corresponds to the index of the right interval for the i-th interval from the input.

Code

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

public class Solution {

    public int[] findRightInterval(int[][] intervals) {
        int n = intervals.length;
        int[] result = new int[n];

        // Step 1: Create an array of Tuple and sort by start time
        int[][] indexedIntervals = new int[n][3];
        for (int i = 0; i < n; i++) {
            indexedIntervals[i][0] = intervals[i][0]; // start time
            indexedIntervals[i][1] = intervals[i][1]; // end time
            indexedIntervals[i][2] = i; // original index
        }

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

        // Step 2: For each interval, find the right interval using binary search
        for (int i = 0; i < n; i++) {
            int end = intervals[i][1];
            int index = binarySearch(indexedIntervals, end);
            result[i] = index;
        }

        return result;
    }

    // Binary search to find the smallest start time >= end time
    private int binarySearch(int[][] intervals, int end) {
        int low = 0;
        int high = intervals.length - 1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (intervals[mid][0] >= end) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return low < intervals.length ? intervals[low][2] : -1;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[][] intervals = // use example above
        System.out.println(Arrays.toString(sol.findRightInterval(intervals))); // Output: [-1, 0, 1]
        
        intervals = new int[][]// use example above
        System.out.println(Arrays.toString(sol.findRightInterval(intervals))); // Output: [2, 2, -1]
    }
}

Time Complexity

Thus, the overall time complexity is (O(n \log n)).

Space Complexity

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI