Jobs

Interviews

Discussions

Remove Interval

Medium

Asked by:

3 views

Topics:

Arrays

Given a sorted list of disjoint intervals, each interval intervals[i] = [a, b) represents the set of real numbers x such that a <= x < b.

We make a request to remove all real numbers in the interval toBeRemoved.

Return a sorted list of disjoint intervals after removing all real numbers in toBeRemoved.

You may assume the given input is well-formed in the sense that the intervals are disjoint and sorted:

intervals[i][0] < intervals[i][1]
intervals[i][0] < intervals[i+1][0]

Example 1:

Input: intervals = [[0,2],[3,4],[5,7]], toBeRemoved = [1,6]
Output: [[0,1],[6,7]]

Example 2:

Input: intervals = [[0,5]], toBeRemoved = [2,3]
Output: [[0,2],[3,5]]

Example 3:

Input: intervals = [[-5,-4],[-3,-2],[1,2],[3,5],[8,9]], toBeRemoved = [-1,4]
Output: [[-5,-4],[-3,-2],[4,5],[8,9]]

Constraints:

1 <= intervals.length <= 10⁴
-10⁹ <= intervals[i][0] < intervals[i][1] <= 10⁹
0 <= toBeRemoved[0] < toBeRemoved[1] <= 10⁹

Try coding it in LeetCode

Remove Interval

Medium

Asked by:

3 views

Topics:

Arrays

Given a sorted list of disjoint intervals, each interval intervals[i] = [a, b) represents the set of real numbers x such that a <= x < b.

We make a request to remove all real numbers in the interval toBeRemoved.

Return a sorted list of disjoint intervals after removing all real numbers in toBeRemoved.

You may assume the given input is well-formed in the sense that the intervals are disjoint and sorted:

intervals[i][0] < intervals[i][1]
intervals[i][0] < intervals[i+1][0]

Example 1:

Input: intervals = [[0,2],[3,4],[5,7]], toBeRemoved = [1,6]
Output: [[0,1],[6,7]]

Example 2:

Input: intervals = [[0,5]], toBeRemoved = [2,3]
Output: [[0,2],[3,5]]

Example 3:

Input: intervals = [[-5,-4],[-3,-2],[1,2],[3,5],[8,9]], toBeRemoved = [-1,4]
Output: [[-5,-4],[-3,-2],[4,5],[8,9]]

Constraints:

1 <= intervals.length <= 10⁴
-10⁹ <= intervals[i][0] < intervals[i][1] <= 10⁹
0 <= toBeRemoved[0] < toBeRemoved[1] <= 10⁹

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 are the possible ranges for the start and end values of the intervals in the input list and the interval to remove? Are they integers or floats?
What should I return if the input list of intervals is empty, or if the interval to remove encompasses all the intervals in the input list?
Can the input list of intervals be assumed to be sorted in any particular order (e.g., by start time)? If not, how should I handle overlapping intervals?
Can the intervals in the input list be adjacent or overlapping? How should such intervals be handled after the removal operation?
Is the input interval always valid (i.e., `intervalToRemove[0] <= intervalToRemove[1]`), and are the intervals in the input list always valid in the same way?

Brute Force Solution

Approach

The brute force way to remove an interval involves checking every part of the larger range to see if it overlaps with the interval we want to remove. We'll consider each small piece individually and decide whether to keep it or discard it based on the interval to be removed.

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

Look at the very beginning of the large range.
See if this part overlaps with the interval we want to remove.
If it doesn't overlap, keep that part.
If it does overlap, throw that part away.
Move to the next small part of the large range.
Repeat the overlap check: either keep it or throw it away.
Continue checking and either keeping or discarding until you've considered every single piece of the original range.
The parts you kept are the range with the specified interval removed.

Code Implementation

def remove_interval_brute_force(ranges, interval_to_remove):
    result = []
    for current_range in ranges:
        range_start = current_range[0]
        range_end = current_range[1]

        # Check if the current range is completely to the left of the interval to remove.
        if range_end <= interval_to_remove[0]:
            result.append(current_range)

        # Check if the current range is completely to the right of the interval to remove.
        elif range_start >= interval_to_remove[1]:
            result.append(current_range)

        # Handle cases where the current range overlaps with the interval.
        else:
            if range_start < interval_to_remove[0]:
                result.append([range_start, interval_to_remove[0]])

            if range_end > interval_to_remove[1]:
                result.append([interval_to_remove[1], range_end])
    return result

Big(O) Analysis

Time Complexity

O(n) – The proposed brute force approach iterates through each small piece of the input range. For each piece, it performs a constant-time overlap check with the interval to be removed. Since it examines every piece once and performs a constant-time operation per piece, where n represents the number of pieces in the original range, the time complexity is directly proportional to n. Thus, the overall time complexity is O(n).

Space Complexity

O(N) – The 'brute force' algorithm described constructs a new range by iterating through the original range and selectively keeping or discarding portions. The kept portions are essentially being added to a new collection. In the worst-case scenario, where no parts of the large range overlap with the interval to be removed, we would keep all the parts, resulting in a new range of the same size as the original. Therefore, the algorithm uses auxiliary space proportional to the size of the input range, N, to store the parts that are kept, which is the new range created.

Optimal Solution

Approach

The goal is to efficiently remove parts of intervals from a list of intervals. Instead of complex comparisons, we'll check how each interval relates to the removal interval and construct a new list of intervals that represents the result after the removal.

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

Go through each interval in the original list one by one.
For each interval, check if it completely lies before the interval we want to remove. If so, keep the original interval because it's unaffected.
If the interval is completely after the removal interval, also keep it as is.
If the interval overlaps with the removal interval, determine if the interval is partially overlapping before the removal, or partially overlapping after the removal interval. If before, keep the portion before removal as a new interval.
If after, keep the portion after removal as a new interval.
If the entire original interval falls within the removal interval, do nothing, because we want to remove this part.
Combine all the kept and newly created partial intervals into a final list. This list represents all the intervals after the requested portion is removed.

Code Implementation

def remove_interval(intervals, interval_to_remove):
    resulting_intervals = []

    for current_interval in intervals:
        # Check if the interval is completely before the interval to remove
        if current_interval[1] <= interval_to_remove[0]:
            resulting_intervals.append(current_interval)

        # Check if the interval is completely after the interval to remove
        elif current_interval[0] >= interval_to_remove[1]:
            resulting_intervals.append(current_interval)

        else:
            # Handle overlapping intervals
            if current_interval[0] < interval_to_remove[0]:
                # Add the portion of the interval before the removed interval
                resulting_intervals.append([current_interval[0], interval_to_remove[0]])

            if current_interval[1] > interval_to_remove[1]:
                # Add the portion of the interval after the removed interval
                resulting_intervals.append([interval_to_remove[1], current_interval[1]])

    return resulting_intervals

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through each interval in the input list of intervals once. For each interval, it performs a constant number of comparisons to determine its relationship with the removal interval and potentially creates at most two new intervals. Therefore, the time complexity is directly proportional to the number of intervals in the input list, which we denote as n. Thus, the overall time complexity is O(n).

Space Complexity

O(N) – The algorithm iterates through each of the N intervals in the original list and potentially creates new intervals based on overlaps with the removal interval. In the worst-case scenario, each original interval is split into at most two new intervals (one before the removal interval and one after), resulting in a new list containing up to 2N intervals. Thus, the auxiliary space required to store this new list is proportional to N. Therefore, the space complexity is O(N).

Edge Cases

Case	How to Handle
intervals or toBeRemoved is null or empty	If intervals is null/empty, return an empty list; if toBeRemoved is null, return intervals.
intervals array is not sorted	The problem statement may imply sorted input, but explicitly sort intervals by start time to guarantee correctness.
toBeRemoved completely contains all intervals	Return an empty list, as all intervals are removed.
toBeRemoved is completely disjoint from all intervals	Return the original intervals array.
An interval is completely contained within toBeRemoved	This interval should be removed entirely (not added to the result).
Overlapping intervals within intervals array	Handle overlaps correctly by splitting intervals into smaller, non-overlapping intervals according to toBeRemoved.
Extreme start and end values for intervals (Integer.MIN_VALUE, Integer.MAX_VALUE)	Ensure the comparison and arithmetic operations involving start and end times do not cause integer overflow.
toBeRemoved interval has Integer.MIN_VALUE or Integer.MAX_VALUE as bounds	Account for edge cases related to comparisons against these boundary values without causing exceptions.

intervals or toBeRemoved is null or empty

How to Handle:

If intervals is null/empty, return an empty list; if toBeRemoved is null, return intervals.

intervals array is not sorted

How to Handle:

The problem statement may imply sorted input, but explicitly sort intervals by start time to guarantee correctness.

toBeRemoved completely contains all intervals

How to Handle:

Return an empty list, as all intervals are removed.

toBeRemoved is completely disjoint from all intervals

How to Handle:

Return the original intervals array.

An interval is completely contained within toBeRemoved

How to Handle:

This interval should be removed entirely (not added to the result).

Overlapping intervals within intervals array

How to Handle:

Handle overlaps correctly by splitting intervals into smaller, non-overlapping intervals according to toBeRemoved.

Extreme start and end values for intervals (Integer.MIN_VALUE, Integer.MAX_VALUE)

How to Handle:

Ensure the comparison and arithmetic operations involving start and end times do not cause integer overflow.

toBeRemoved interval has Integer.MIN_VALUE or Integer.MAX_VALUE as bounds

How to Handle:

Account for edge cases related to comparisons against these boundary values without causing exceptions.

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 are the possible ranges for the start and end values of the intervals in the input list and the interval to remove? Are they integers or floats?
What should I return if the input list of intervals is empty, or if the interval to remove encompasses all the intervals in the input list?
Can the input list of intervals be assumed to be sorted in any particular order (e.g., by start time)? If not, how should I handle overlapping intervals?
Can the intervals in the input list be adjacent or overlapping? How should such intervals be handled after the removal operation?
Is the input interval always valid (i.e., `intervalToRemove[0] <= intervalToRemove[1]`), and are the intervals in the input list always valid in the same way?

Brute Force Solution

Approach

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

Look at the very beginning of the large range.
See if this part overlaps with the interval we want to remove.
If it doesn't overlap, keep that part.
If it does overlap, throw that part away.
Move to the next small part of the large range.
Repeat the overlap check: either keep it or throw it away.
Continue checking and either keeping or discarding until you've considered every single piece of the original range.
The parts you kept are the range with the specified interval removed.

Code Implementation

def remove_interval_brute_force(ranges, interval_to_remove):
    result = []
    for current_range in ranges:
        range_start = current_range[0]
        range_end = current_range[1]

        # Check if the current range is completely to the left of the interval to remove.
        if range_end <= interval_to_remove[0]:
            result.append(current_range)

        # Check if the current range is completely to the right of the interval to remove.
        elif range_start >= interval_to_remove[1]:
            result.append(current_range)

        # Handle cases where the current range overlaps with the interval.
        else:
            if range_start < interval_to_remove[0]:
                result.append([range_start, interval_to_remove[0]])

            if range_end > interval_to_remove[1]:
                result.append([interval_to_remove[1], range_end])
    return result

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Go through each interval in the original list one by one.
For each interval, check if it completely lies before the interval we want to remove. If so, keep the original interval because it's unaffected.
If the interval is completely after the removal interval, also keep it as is.
If the interval overlaps with the removal interval, determine if the interval is partially overlapping before the removal, or partially overlapping after the removal interval. If before, keep the portion before removal as a new interval.
If after, keep the portion after removal as a new interval.
If the entire original interval falls within the removal interval, do nothing, because we want to remove this part.
Combine all the kept and newly created partial intervals into a final list. This list represents all the intervals after the requested portion is removed.

Code Implementation

def remove_interval(intervals, interval_to_remove):
    resulting_intervals = []

    for current_interval in intervals:
        # Check if the interval is completely before the interval to remove
        if current_interval[1] <= interval_to_remove[0]:
            resulting_intervals.append(current_interval)

        # Check if the interval is completely after the interval to remove
        elif current_interval[0] >= interval_to_remove[1]:
            resulting_intervals.append(current_interval)

        else:
            # Handle overlapping intervals
            if current_interval[0] < interval_to_remove[0]:
                # Add the portion of the interval before the removed interval
                resulting_intervals.append([current_interval[0], interval_to_remove[0]])

            if current_interval[1] > interval_to_remove[1]:
                # Add the portion of the interval after the removed interval
                resulting_intervals.append([interval_to_remove[1], current_interval[1]])

    return resulting_intervals

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
intervals or toBeRemoved is null or empty	If intervals is null/empty, return an empty list; if toBeRemoved is null, return intervals.
intervals array is not sorted	The problem statement may imply sorted input, but explicitly sort intervals by start time to guarantee correctness.
toBeRemoved completely contains all intervals	Return an empty list, as all intervals are removed.
toBeRemoved is completely disjoint from all intervals	Return the original intervals array.
An interval is completely contained within toBeRemoved	This interval should be removed entirely (not added to the result).
Overlapping intervals within intervals array	Handle overlaps correctly by splitting intervals into smaller, non-overlapping intervals according to toBeRemoved.
Extreme start and end values for intervals (Integer.MIN_VALUE, Integer.MAX_VALUE)	Ensure the comparison and arithmetic operations involving start and end times do not cause integer overflow.
toBeRemoved interval has Integer.MIN_VALUE or Integer.MAX_VALUE as bounds	Account for edge cases related to comparisons against these boundary values without causing exceptions.

intervals or toBeRemoved is null or empty

How to Handle:

If intervals is null/empty, return an empty list; if toBeRemoved is null, return intervals.

intervals array is not sorted

How to Handle:

The problem statement may imply sorted input, but explicitly sort intervals by start time to guarantee correctness.

toBeRemoved completely contains all intervals

How to Handle:

Return an empty list, as all intervals are removed.

toBeRemoved is completely disjoint from all intervals

How to Handle:

Return the original intervals array.

An interval is completely contained within toBeRemoved

How to Handle:

This interval should be removed entirely (not added to the result).

Overlapping intervals within intervals array

How to Handle:

Handle overlaps correctly by splitting intervals into smaller, non-overlapping intervals according to toBeRemoved.

Extreme start and end values for intervals (Integer.MIN_VALUE, Integer.MAX_VALUE)

How to Handle:

Ensure the comparison and arithmetic operations involving start and end times do not cause integer overflow.

toBeRemoved interval has Integer.MIN_VALUE or Integer.MAX_VALUE as bounds

How to Handle:

Account for edge cases related to comparisons against these boundary values without causing exceptions.