A set of real numbers can be represented as the union of several disjoint intervals, where each interval is in the form [a, b). A real number x is in the set if one of its intervals [a, b) contains x (i.e. a <= x < b).
You are given a sorted list of disjoint intervals intervals representing a set of real numbers as described above, where intervals[i] = [ai, bi] represents the interval [ai, bi). You are also given another interval toBeRemoved.
Return the set of real numbers with the interval toBeRemoved removed from intervals. In other words, return the set of real numbers such that every x in the set is in intervals but not in toBeRemoved. Your answer should be a sorted list of disjoint intervals as described above.
Example 1:
Input: intervals = [[0,2],[3,4],[5,7]], toBeRemoved = [1,6] Output: [[0,1],[6,7]]
Example 2:
Input: intervals = [[0,5]], toBeRemoved = [2,3] Output: [[0,2],[3,5]]
Example 3:
Input: intervals = [[-5,-4],[-3,-2],[1,2],[3,5],[8,9]], toBeRemoved = [-1,4] Output: [[-5,-4],[-3,-2],[4,5],[8,9]]
Constraints:
1 <= intervals.length <= 104-109 <= ai < bi <= 109Problem Overview: You are given a list of disjoint intervals and another interval toBeRemoved. The task is to remove the overlapping portion of toBeRemoved from each interval and return the remaining parts. Any interval partially overlapping may split into two smaller intervals.
Approach 1: Brute Force Interval Splitting (O(n) time, O(n) space)
Iterate through every interval and explicitly compute the overlap with toBeRemoved. For each interval [l, r], determine whether it lies completely outside the removal range or intersects it. If there is no overlap, append the interval directly to the result. If an overlap exists, split the interval into possible remaining parts: [l, removeStart] and [removeEnd, r], adding only the valid segments. This method directly models the geometry of interval subtraction and works well when reasoning step‑by‑step about interval boundaries.
Approach 2: Case Discussion (Optimal) (O(n) time, O(n) space)
The optimal solution performs a single pass through the intervals and handles three clear cases using simple comparisons. First, if the current interval lies completely before or after toBeRemoved, append it unchanged. Second, if the interval overlaps on the left side, keep the portion [start, removeStart]. Third, if it overlaps on the right side, keep [removeEnd, end]. Some intervals may generate two pieces when the removal range sits strictly inside them. This works because the intervals are already disjoint, so you only need constant-time checks per interval.
The key insight is that removing an interval only affects intervals that intersect its range. Instead of modifying the structure in place, you construct the resulting list while scanning once. Each interval contributes zero, one, or two segments depending on its relationship with toBeRemoved. The algorithm uses simple comparisons and append operations, making it efficient and easy to implement.
Problems like this commonly appear in interval manipulation tasks involving arrays and boundary comparisons. The logic is similar to other interval operations such as merging or clipping ranges, which are core techniques in greedy and interval-based problems.
Recommended for interviews: The case discussion approach is what interviewers expect. It shows that you understand how interval overlap works and can reason through boundary conditions. Explaining the brute-force splitting idea first demonstrates correctness, while the final O(n) scan highlights practical problem-solving skills.
We denote the interval to be removed as [x, y). We traverse the interval list, and for each interval [a, b), there are three cases:
a geq y or b leq x, which means that this interval does not intersect with the interval to be removed. We directly add this interval to the answer.a \lt x, b \gt y, which means that this interval intersects with the interval to be removed. We split this interval into two intervals and add them to the answer.a geq x, b leq y, which means that this interval is completely covered by the interval to be removed. We do not add it to the answer.The time complexity is O(n), where n is the length of the interval list. The space complexity is O(1).
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Interval Splitting | O(n) | O(n) | When first reasoning about interval subtraction or implementing a straightforward overlap check. |
| Case Discussion (Optimal) | O(n) | O(n) | Best for interviews and production. Single pass with simple boundary comparisons. |
Leetcode 1272 Remove Interval • Ren Zhang • 787 views views
Watch 4 more video solutions →Practice Remove Interval with our built-in code editor and test cases.
Practice on FleetCode