LeetCode 1272 - Remove Interval

The problem asks us to remove a given interval toBeRemoved from a list of non-overlapping, sorted intervals intervals. E

leetcodemediumarray

LeetCode Problem 1272

Difficulty: 🟡 Medium
Topics: Array

Solution

Problem Understanding

The problem asks us to remove a given interval toBeRemoved from a list of non-overlapping, sorted intervals intervals. Each interval is represented as [a, b) and includes all numbers x such that a <= x < b. Removing an interval means we need to adjust or split any existing intervals that overlap with toBeRemoved, producing a new list of intervals that excludes all numbers in toBeRemoved.

The input intervals is guaranteed to be sorted by start time and non-overlapping. This ensures that each interval can be considered independently for intersection with toBeRemoved. The output should also be sorted and non-overlapping, consistent with the input representation.

Important edge cases include intervals that are completely before or after toBeRemoved, intervals that are completely contained within toBeRemoved, and intervals that partially overlap at the beginning or end. The constraints 1 <= intervals.length <= 10^4 and -10^9 <= ai < bi <= 10^9 indicate that an O(n) solution is acceptable, but anything significantly slower may not perform well.

Approaches

The brute-force approach would involve generating all numbers represented by each interval, removing any numbers that fall into toBeRemoved, and then reconstructing intervals. While correct, this is inefficient because it requires processing potentially billions of numbers when intervals are large.

The optimal approach leverages the fact that intervals are sorted and disjoint. For each interval [start, end):

  1. If it lies completely before toBeRemoved, it is untouched.
  2. If it lies completely after toBeRemoved, it is untouched.
  3. If it overlaps with toBeRemoved, it may need to be split into two intervals: one before toBeRemoved and one after toBeRemoved.

This can be done in a single pass through intervals in O(n) time without creating intermediate lists of numbers.

Approach Time Complexity Space Complexity Notes
Brute Force O(M) O(M) Generate all numbers in intervals and remove those in toBeRemoved, where M is the sum of lengths of all intervals. Too slow for large ranges.
Optimal O(n) O(n) Single pass, splitting only overlapping intervals. Efficient and simple.

Algorithm Walkthrough

  1. Initialize an empty list result to store the intervals after removal.
  2. Iterate over each interval [start, end) in intervals.
  3. If end <= toBeRemoved[0] or start >= toBeRemoved[1], append [start, end) to result since it does not overlap.
  4. If start < toBeRemoved[0] and end > toBeRemoved[0], append [start, toBeRemoved[0]] to result. This handles the left portion of the overlap.
  5. If start < toBeRemoved[1] and end > toBeRemoved[1], append [toBeRemoved[1], end] to result. This handles the right portion of the overlap.
  6. Continue iterating until all intervals are processed.
  7. Return result.

Why it works: The key invariant is that intervals are disjoint and sorted, so each interval can be considered independently. By splitting overlapping intervals into at most two parts and keeping non-overlapping intervals unchanged, we guarantee the output remains sorted and disjoint and excludes all numbers in toBeRemoved.

Python Solution

from typing import List

class Solution:
    def removeInterval(self, intervals: List[List[int]], toBeRemoved: List[int]) -> List[List[int]]:
        result = []
        remove_start, remove_end = toBeRemoved
        
        for start, end in intervals:
            if end <= remove_start or start >= remove_end:
                result.append([start, end])
            else:
                if start < remove_start:
                    result.append([start, remove_start])
                if end > remove_end:
                    result.append([remove_end, end])
                    
        return result

Explanation: We iterate over each interval. If it lies completely outside toBeRemoved, we add it unchanged. If it overlaps, we check for left and right portions that are outside toBeRemoved and append them separately. This ensures no numbers in toBeRemoved remain in the output.

Go Solution

func removeInterval(intervals [][]int, toBeRemoved []int) [][]int {
    result := [][]int{}
    removeStart, removeEnd := toBeRemoved[0], toBeRemoved[1]
    
    for _, interval := range intervals {
        start, end := interval[0], interval[1]
        if end <= removeStart || start >= removeEnd {
            result = append(result, []int{start, end})
        } else {
            if start < removeStart {
                result = append(result, []int{start, removeStart})
            }
            if end > removeEnd {
                result = append(result, []int{removeEnd, end})
            }
        }
    }
    
    return result
}

Go-specific notes: We use slices to store intervals, and appending automatically handles dynamic resizing. Nil slices are not an issue because we initialize result to an empty slice.

Worked Examples

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

Interval Overlaps Action Result
[0,2] yes split left: [0,1] [0,1]
[3,4] yes fully inside remove, discard [0,1]
[5,7] yes split right: [6,7] [0,1],[6,7]

Output: [[0,1],[6,7]]

Example 2: intervals = [[0,5]], toBeRemoved = [2,3]

Interval Overlaps Action Result
[0,5] yes split left: [0,2], split right: [3,5] [0,2],[3,5]

Output: [[0,2],[3,5]]

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

Interval Overlaps Action Result
[-5,-4] no keep [-5,-4]
[-3,-2] no keep [-5,-4],[-3,-2]
[1,2] yes fully inside remove, discard [-5,-4],[-3,-2]
[3,5] yes split right: [4,5] [-5,-4],[-3,-2],[4,5]
[8,9] no keep [-5,-4],[-3,-2],[4,5],[8,9]

Output: [[-5,-4],[-3,-2],[4,5],[8,9]]

Complexity Analysis

Measure Complexity Explanation
Time O(n) Single pass over intervals of length n, constant work per interval.
Space O(n) Output list stores at most two intervals per input interval.

The algorithm is linear in the number of input intervals, and it only uses extra space for the output.

Test Cases

# Provided examples
assert Solution().removeInterval([[0,2],[3,4],[5,7]], [1,6]) == [[0,1],[6,7]] # overlaps multiple intervals
assert Solution().removeInterval([[0,5]], [2,3]) == [[0,2],[3,5]] # single interval split
assert Solution().removeInterval([[-5,-4],[-3,-2],[1,2],[3,5],[8,9]], [-1,4]) == [[-5,-4],[-3,-2],[4,5],[8,9]] # negative numbers and gaps

# Edge cases
assert Solution().removeInterval([[0,1]], [0,1]) == [] # fully removed interval
assert Solution().removeInterval([[0,1]], [2,3]) == [[0,1]] # no overlap
assert Solution().removeInterval([[0,2],[3,5]], [1,4]) == [[0,1],[4,5]] # overlap both intervals

# Large numbers
assert Solution().removeInterval([[ -10**9, 10**9 ]], [0,0]) == [[ -10**9, 10**9 ]] # zero-length remove interval
assert Solution().removeInterval([[ -10**9, 10**9 ]], [-10**9, 10**9]) == [] # remove entire interval
Test Why
[[0,2],[3,4],[5,7]], [1,6] Multiple overlapping intervals, split and discard
[[0,5]], [2,3] Single interval split into two
[[-5,-4],[-3,-2],[1,2],[3,5],[8,9]], [-1