Remove Interval

Remove Interval

What is this problem about?

The Remove Interval interview question presents you with a list of non-overlapping intervals sorted by their start points, and a separate interval to remove. You must delete the portion of each interval in the list that overlaps with the removal interval, splitting intervals as necessary, and return the resulting list of intervals. Intervals that fall entirely within the removal zone are deleted; partial overlaps are trimmed.

Why is this asked in interviews?

Google asks this problem because it is a precise test of interval reasoning and boundary arithmetic. It requires candidates to carefully enumerate the three cases for each interval relative to the removal range: no overlap (keep as-is), full overlap (discard), or partial overlap (trim from left or right, or split into two). Handling all edge cases cleanly with correct comparisons is the challenge.

Algorithmic pattern used

The pattern is linear scan with case analysis on interval boundaries. For each interval [a, b] and removal range [lo, hi]:

1. If b <= lo or a >= hi: no overlap → keep [a, b] unchanged.
2. If a >= lo and b <= hi: fully covered → discard.
3. If a < lo: left portion [a, lo] survives → add it.
4. If b > hi: right portion [hi, b] survives → add it. Cases 3 and 4 can both apply to the same interval (split scenario).

Example explanation

Intervals: [[0,2],[3,4],[5,7]], remove [1,6].

• [0,2]: overlaps with [1,6]. Left part [0,1] survives (0 < 1). Right part: b=2 ≤ hi=6, so no right part.
• [3,4]: fully inside [1,6] (3 ≥ 1 and 4 ≤ 6) → discard.
• [5,7]: overlaps. Left part: a=5 ≥ lo=1, so no left part. Right part: b=7 > hi=6 → add [6,7].

Result: [[0,1],[6,7]].

Common mistakes candidates make

• Using strict vs. non-strict inequalities incorrectly — boundary conditions like b == lo or a == hi mean no overlap, not overlap.
• Forgetting that one interval can produce two output intervals (the split case).
• Assuming the intervals are sorted but not using that property to early-exit.
• Incorrectly handling intervals that are completely outside the removal zone.

Interview preparation tip

For the Remove Interval coding problem, draw a number line and mark your interval and the removal range before coding. Label the four boundary cases visually. Google interviewers appreciate when you enumerate all cases explicitly and explain your inequality choices. The array interview pattern here is purely case-driven — clean conditional logic is more important than any clever data structure.