We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Remove Interval

Number: 1200

Difficulty: Medium

Paid? Yes

Companies: Google

Problem Description

Given a sorted list of disjoint intervals (each represented as [a, b) where a ≤ x < b), remove the numbers that fall into a given interval (toBeRemoved). The result should be the remaining parts of the original intervals as a sorted list of disjoint intervals.

Key Insights

  • Iterate over each interval and check if it overlaps with the toBeRemoved interval.
  • If the current interval is completely outside of toBeRemoved, add it to the result as is.
  • For overlapping intervals, compute the non-overlapping portions:
    • If the left side of the interval lies before toBeRemoved, include [start, min(end, toBeRemoved.start)].
    • If the right side of the interval lies after toBeRemoved, include [max(start, toBeRemoved.end), end].

Space and Time Complexity

Time Complexity: O(n), where n is the number of intervals. Space Complexity: O(n), for storing the resulting intervals.

Solution

The approach involves iterating through the list of sorted disjoint intervals and checking for overlap with the toBeRemoved interval. For each interval:

  1. If it is completely before or after the removal interval, add it directly to the result.
  2. If it overlaps with toBeRemoved, determine the remaining portion(s):
    • The left side of the interval that does not intersect (if any).
    • The right side of the interval that does not intersect (if any). Use simple conditional checks and list manipulation to form the final set of intervals.

Code Solutions

def removeInterval(intervals, toBeRemoved):
    # Unpack the removal interval boundaries.
    remove_start, remove_end = toBeRemoved
    result = []
    
    # Iterate over each interval.
    for interval in intervals:
        start, end = interval
        
        # If the interval is completely outside toBeRemoved, add as is.
        if end <= remove_start or start >= remove_end:
            result.append([start, end])
        else:
            # If there is a non-overlapping left part, add it.
            if start < remove_start:
                result.append([start, remove_start])
            # If there is a non-overlapping right part, add it.
            if end > remove_end:
                result.append([remove_end, end])
    
    return result

# Example usage:
intervals = [[0,2],[3,4],[5,7]]
toBeRemoved = [1,6]
print(removeInterval(intervals, toBeRemoved))  # Expected output: [[0,1],[6,7]]
← Back to All Questions