Skip to main content
Talentd

Remove Interval - Solution & Explanation

MediumPremiumFree on FleetCodeArray7 min readAsked at: Google
Practice this problem

Problem Statement

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 <= 109

Approach Overview

Problem 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.

Solution

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).

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Interval SplittingO(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.

Video Solution

Leetcode 1272 Remove Interval • Ren Zhang • 791 views views

Watch 5 more video solutions →

Frequently Asked Questions

Is Remove Interval easy or hard?
Remove Interval is generally considered a medium-level problem. The implementation is straightforward once you identify the three overlap cases, but handling boundary conditions correctly can be tricky. It mainly tests understanding of interval overlap logic and careful conditional checks.
Remove Interval Python/Java solution
Most implementations iterate through the interval list and append valid segments to a result list. Python uses list append operations, while Java typically uses ArrayList<int[]>. The same case-based logic applies in C++ with vector and in Go with slices.
How to solve Remove Interval in O(n)?
Iterate through the interval list once and compare each interval with the removal range. If the interval is completely outside the removal interval, keep it unchanged. If it overlaps, append the remaining left portion or right portion after trimming the overlap. Each interval requires constant work, giving an overall O(n) runtime.
What is the best approach for Remove Interval?
The best approach is a case discussion method that scans the intervals once and handles overlap using boundary comparisons. For each interval, determine whether it is completely outside the removal range or partially overlaps it. Add the unaffected part(s) to the result. This runs in O(n) time with O(n) extra space.
Is Remove Interval asked at Google/Amazon/Meta?
Interval manipulation problems similar to Remove Interval appear frequently in interviews at companies like Google, Amazon, and Meta. Variants include merging intervals, inserting intervals, and interval intersection. These problems test reasoning about boundaries and efficient linear scans.
What data structure is used in Remove Interval?
The solution primarily uses arrays or lists to store intervals and build the resulting intervals after removal. The algorithm relies on simple comparisons of interval boundaries rather than advanced data structures. Understanding interval representation and iteration is the key requirement.
What is the time complexity of Remove Interval?
The optimal solution runs in O(n) time because each interval is processed exactly once. Only constant-time comparisons and append operations are performed per interval. The space complexity is O(n) in the worst case because the result list may store up to all intervals or split segments.

Ready to solve this problem?

Practice Remove Interval with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays