Find Right Interval

Medium

Asked by:

31 views

Topics:

ArraysBinary Search

You are given an array of intervals, where intervals[i] = [start_i, end_i] and each start_i is unique.

The right interval for an interval i is an interval j such that start_j >= end_i and start_j 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 start₀ = 3 is the smallest start that is >= end₁ = 3.
The right interval for [1,2] is [2,3] since start₁ = 2 is the smallest start that is >= end₂ = 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 start₂ = 3 is the smallest start that is >= end₁ = 3.

Constraints:

1 <= intervals.length <= 2 * 10⁴
intervals[i].length == 2
-10⁶ <= start_i <= end_i <= 10⁶
The start point of each interval is unique.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the start and end points of the intervals? Can they be negative?
Is it possible for an interval to have a start value greater than its end value? What should I do in that case?
Are the intervals guaranteed to be distinct, or can there be overlapping or identical intervals?
If no 'right' interval exists for a given interval, what value should I return? Should I return -1?
What should I return if multiple 'right' intervals exist for a given interval? Should I return the one with the smallest start value's index?

Brute Force Solution

Approach

The brute force approach to finding the 'right interval' is like checking every possible pairing of intervals to see if one interval starts after another. It's about exhaustively comparing each interval with every other interval. If a 'right interval' can't be found for a particular interval, we'll just mark that we didn't find one.

Here's how the algorithm would work step-by-step:

Take the first interval from our group of intervals.
Now, one by one, look at every other interval in the group.
For each of those other intervals, check if its start point is greater than or equal to the end point of our first interval. This will determine if it is a 'right interval'.
If it is, remember this 'right interval'. We are trying to find the one with the smallest start point so save it to compare against the others.
If you go through all the other intervals and don't find any that start after the first interval ends, then note that down.
Do this process for every single interval in the group.
At the end, you'll have a list telling you for each interval either which 'right interval' you found (the one with the smallest start) or that you couldn't find any 'right interval'.

Code Implementation

def find_right_interval_brute_force(intervals):
    number_of_intervals = len(intervals)
    result = [-1] * number_of_intervals

    for interval_index in range(number_of_intervals):
        current_interval = intervals[interval_index]
        current_interval_end = current_interval[1]

        minimum_start = float('inf')
        right_interval_index = -1

        for other_interval_index in range(number_of_intervals):
            if interval_index == other_interval_index:
                continue

            other_interval = intervals[other_interval_index]
            other_interval_start = other_interval[0]

            # Check if it's a 'right interval'
            if other_interval_start >= current_interval_end:

                # Need to find the minimum start value
                if other_interval_start < minimum_start:
                    minimum_start = other_interval_start
                    right_interval_index = other_interval_index

        result[interval_index] = right_interval_index

    return result

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through each of the n intervals in the input array. For each interval, it then iterates through the remaining n-1 intervals to find a 'right interval'. This nested iteration results in approximately n * (n-1) comparisons. Since we drop constant factors and lower order terms in Big O notation, n * (n-1) simplifies to n². Thus, the time complexity is O(n²).

Space Complexity

O(1) – The provided algorithm iterates through the intervals and compares their start and end points. It uses a few variables to keep track of the best right interval found so far for each interval. The number of such variables remains constant irrespective of the number of intervals. Therefore, the auxiliary space required by the algorithm does not depend on the input size N (where N is the number of intervals), and it has constant space complexity.

Optimal Solution

Approach

The goal is to find, for each interval, another interval whose start is the smallest possible value that is greater than or equal to the end of the original interval. We can achieve this efficiently by sorting all the interval start points and then using a clever searching strategy to quickly locate the desired right interval.

Here's how the algorithm would work step-by-step:

First, remember where each interval was originally located, because we will need to return to it later.
Next, make a list of all the starting points of the intervals and sort them from smallest to largest. Importantly, also remember the original interval that each start point came from.
Now, for each original interval, find the right interval. To do this, look through the sorted start points to find the smallest start point that is greater than or equal to the end point of the original interval. This is done through a process of elimination of the other start points.
If you find a start point that meets the criteria, record the original interval that that start point came from. This is your 'right interval'.
If you can't find any start point that is greater than or equal to the end point, record that there is no 'right interval' for that interval.
Finally, put the 'right intervals' back in their original positions so that the answer matches the order of the original list of intervals.

Code Implementation

def find_right_interval(intervals):
    number_of_intervals = len(intervals)
    right_intervals = [-1] * number_of_intervals

    start_points_with_index = []
    for index, interval in enumerate(intervals):
        start_points_with_index.append((interval[0], index))

    # Sort start points to enable efficient searching
    start_points_with_index.sort()

    for index, interval in enumerate(intervals):
        end_point = interval[1]
        right_interval_index = -1

        # Find the smallest start point >= end_point
        left_index = 0
        right_index = number_of_intervals - 1

        while left_index <= right_index:
            middle_index = (left_index + right_index) // 2
            if start_points_with_index[middle_index][0] >= end_point:
                right_interval_index = start_points_with_index[middle_index][1]
                right_index = middle_index - 1
            else:
                left_index = middle_index + 1

        right_intervals[index] = right_interval_index

    return right_intervals

Big(O) Analysis

Time Complexity

O(n log n) – The algorithm begins by sorting the starting points of the intervals, which takes O(n log n) time. Then, for each of the n intervals, it searches for the right interval among the sorted start points. This search can be efficiently performed using binary search, taking O(log n) time for each interval. Therefore, the total time complexity is dominated by the sorting step and the n binary searches, resulting in O(n log n) + n * O(log n), which simplifies to O(n log n).

Space Complexity

O(N) – The auxiliary space complexity is O(N) due to the creation of a list of starting points of the intervals and storing the original index of each interval. This sorted list, which includes both the start point and original index for each of the N intervals, requires space proportional to the number of intervals. While other variables are used, they occupy constant space, and therefore the dominant factor is the storage of the start points and indices. Thus, the space used scales linearly with the input size N.

Edge Cases

Case	How to Handle
Null or empty input array	Return an empty array immediately as there are no intervals to process.
Input array with a single interval	Return an array containing -1 since a single interval cannot have a 'right' interval.
Intervals with identical start values	The algorithm should correctly identify the right interval based on the specified comparison (start value greater than or equal) after sorting based on start values.
No right interval exists for a given interval	The solution should return -1 for intervals that do not have a right interval.
Input array with intervals having very large start/end values (potential integer overflow)	Use long or appropriate data types to prevent integer overflow during comparisons and calculations if necessary.
Input array where all intervals are overlapping	Each interval should be assigned -1 in the result array, since no interval has a right interval.
A right interval exists, but its start value is extremely close to the end value of the original interval (floating point precision issues if using floats)	Ensure the comparison is robust against floating-point inaccuracies by using appropriate tolerance or integer-based representations.
Maximum number of intervals allowed by the problem constraint	Ensure the solution doesn't exceed time or space complexity limits for the maximum allowed input size, potentially causing timeouts or out-of-memory errors.

Null or empty input array

How to Handle:

Return an empty array immediately as there are no intervals to process.

Input array with a single interval

How to Handle:

Return an array containing -1 since a single interval cannot have a 'right' interval.

Intervals with identical start values

How to Handle:

The algorithm should correctly identify the right interval based on the specified comparison (start value greater than or equal) after sorting based on start values.

No right interval exists for a given interval

How to Handle:

The solution should return -1 for intervals that do not have a right interval.

Input array with intervals having very large start/end values (potential integer overflow)

How to Handle:

Use long or appropriate data types to prevent integer overflow during comparisons and calculations if necessary.

Input array where all intervals are overlapping

How to Handle:

Each interval should be assigned -1 in the result array, since no interval has a right interval.

A right interval exists, but its start value is extremely close to the end value of the original interval (floating point precision issues if using floats)

How to Handle:

Ensure the comparison is robust against floating-point inaccuracies by using appropriate tolerance or integer-based representations.

Maximum number of intervals allowed by the problem constraint

How to Handle:

Ensure the solution doesn't exceed time or space complexity limits for the maximum allowed input size, potentially causing timeouts or out-of-memory errors.