Domain 2MediumMEDIUM

Remove Interval

LeetCode problem 1272: Remove Interval (medium).

Domain: medium•Updated: 2026-09-13
#Math#Line Sweep

Problem Breakdown

We are given a sorted list of disjoint intervals representing a set of real numbers (half-open ranges [a, b)). We also have one specific interval toBeRemoved that we need to subtract from this collection. The goal is to return the remaining parts as a new sorted list of disjoint intervals.

Inputs:

  • intervals: A 2D array where each row represents an interval [start, end). Sorted by start time and guaranteed to be non-overlapping (disjoint).
  • toBeRemoved: An array representing the single range [remove_start, remove_end) that must be excluded.

Outputs:

  • A list of intervals representing the set difference: (intervals - toBeRemoved). The result must remain sorted and disjoint.

Implicit Constraints & Edge Cases:

  1. Disjointness: Since input is already disjoint and sorted, we don’t need to merge adjacent results (e.g., [0,2) and [2,3) are distinct but touching; the problem treats them as separate entities unless they overlap). However, if an interval gets split by toBeRemoved, we must ensure valid intervals (start < end) before adding.
  2. Containment: An existing interval might be fully contained within toBeRemoved (resulting in no output for that specific input row) or completely outside it.
  3. Partial Overlap: The removal range cuts through an existing interval, creating a left remainder and/or a right remainder. We must handle both cases independently to avoid gaps or duplicates.

Intuition

A brute force approach would involve iterating over every number in the real line (impossible) or checking intersection for each point, which is O(N⋅M)O(N \cdot M) where N is interval count and M is range size—inefficient given infinite precision requirements. Since we are dealing with intervals on a continuous domain but represented by discrete bounds, this becomes an interval arithmetic problem.

The key insight is that since intervals is sorted, we can process each one in linear time O(N)O(N). For every interval [start, end) from the input:

  1. If it ends before removal starts -> Keep as is (Before).
  2. If it starts after removal ends -> Keep as is (After).
  3. Otherwise -> It overlaps with toBeRemoved. We must split this interval into valid parts that fall outside [remove_start, remove_end):
    • Left Part: From current start up to the minimum of our end or removal’s start.
    • Right Part: From maximum of current start and removal’s end up to current end.

Approach

  1. Initialize an empty result list res.
  2. Extract bounds from toBeRemoved into variables for easier comparison (r_start, r_end).
  3. Iterate through each [start, end] in the input intervals:
    • Case A (No Overlap - Before): If end <= r_start. The interval is completely to the left of removal. Append original interval.
    • Case B (No Overlap - After): If start >= r_end. The interval is completely to the right. Append original interval.
    • Case C (Overlap Exists): Otherwise, we have an intersection. We need to calculate valid sub-intervals:
      1. Calculate potential left boundary end point: min(end, r_start). If this value is greater than start, append [start, min_val].
      2. Calculate potential right boundary start point: max(start, r_end). If this value is less than end, append [right_val, end].
  4. Return the accumulated list in res.

Complexity Analysis

  • Time Complexity: O(N)O(N) where NN is the number of intervals. We iterate through the input list exactly once performing constant-time arithmetic operations per interval. Sorting is not required as output order matches input order naturally due to processing sequence.
  • Space Complexity: O(1)O(1) auxiliary space (excluding the space required for the result array). The logic only uses a few pointers and variables regardless of input size.

Solution

from typing import List

def removeInterval(intervals: List[List[int]], toBeRemoved: List[int]) -> List[List[int]]:
    res = []
    
    # Extract removal bounds for cleaner comparison
    r_start, r_end = toBeRemoved[0], toBeRemoved[1]
    
    for start, end in intervals:
        # Case 1: Interval is completely before the removed range.
        if end <= r_start:
            res.append([start, end])
        
        # Case 2: Interval is completely after the removed range.
        elif start >= r_end:
            res.append([start, end])
            
        else:
            # Case 3: Overlap exists. We need to split or truncate this interval.
            
            # Check for a valid left part (before removal starts)
            # The right boundary of the kept segment is min(current_end, remove_start)
            if start < min(end, r_start):
                res.append([start, min(end, r_start)])
                
            # Check for a valid right part (after removal ends)
            # The left boundary of this new segment is max(current_start, remove_end)
            if max(start, r_end) < end:
                res.append([max(start, r_end), end])

    return res

Edge Cases Handled

  • No Intersection: If toBeRemoved falls entirely outside all intervals (e.g., removal is [10, 20], interval ends at 5 or starts at 30), the code adds them unchanged.
  • Full Containment: If an input interval like [2, 8] overlaps with removal [4, 6], it splits into [2, 4) and [6, 8). If an interval is fully inside (e.g., [3, 5] vs remove [1, 7]), both split conditions fail validity checks (start < min_val) or result in empty ranges, so nothing is added for that row.
  • Empty Result: If all intervals are removed by toBeRemoved, the loop finishes without appending anything to res, returning an empty list correctly.