Remove Interval

Problem Statement

Given a sorted set of disjoint intervals and an interval to remove, return the remaining intervals after the removal — with overlapping portions carved out.

Input

• intervals — a sorted list of disjoint intervals.
• toBeRemoved — a single interval [start, end] to carve out.

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

Output

The remaining intervals in sorted order, after toBeRemoved has been erased from each overlapping interval.

[[0,1],[6,7]]

Constraints

• 1 ≤ intervals.length ≤ 10⁴
• -10⁹ ≤ startᵢ < endᵢ ≤ 10⁹
• intervals is sorted by startᵢ.
• toBeRemoved.length == 2.

Intuition

Walk through each interval once. For each one, ask: does it overlap the removal range?

• No overlap → keep it unchanged.
• Overlap → keep whatever sits outside the removal zone: a left remnant and/or a right remnant.

Every original interval produces 0, 1, or 2 output intervals.

Interval:     [══════════════════════]
Remove:              [════════════]
Left part:    [══════]                       ← kept if s < rm_s
Right part:                        [══════]  ← kept if e > rm_e

Solution

def removeInterval(intervals, toBeRemoved):
    result = []
    rm_s, rm_e = toBeRemoved
 
    for s, e in intervals:
        if e <= rm_s or s >= rm_e:
            result.append([s, e])       # no overlap
        else:
            if s < rm_s:
                result.append([s, rm_s])  # left remnant
            if e > rm_e:
                result.append([rm_e, e])  # right remnant
 
    return result

function removeInterval(intervals: number[][], toBeRemoved: number[]): number[][] {
    const result: number[][] = [];
    const [rmS, rmE] = toBeRemoved;
 
    for (const [s, e] of intervals) {
        if (e <= rmS || s >= rmE) {
            result.push([s, e]);
        } else {
            if (s < rmS) result.push([s, rmS]);
            if (e > rmE) result.push([rmE, e]);
        }
    }
 
    return result;
}

Complexity

Edge Case Thinking