Remove Interval

Remove Interval - Problem

Array Medium

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.

Input & Output

Example 1 — Basic Interval Removal

$ Input: intervals = [[0,2],[3,4],[4,6]], toBeRemoved = [1,3]

› Output: [[0,1],[3,4],[4,6]]

💡 Note: Interval [0,2] overlaps with [1,3], so we keep [0,1]. Intervals [3,4] and [4,6] don't overlap with [1,3], so they remain unchanged.

Example 2 — Complete Removal

$ Input: intervals = [[0,5]], toBeRemoved = [2,3]

› Output: [[0,2],[3,5]]

💡 Note: The interval [0,5] contains [2,3], so we split it into two parts: [0,2] and [3,5], removing the middle section [2,3].

Example 3 — No Overlap

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

› Output: [[0,1],[2,3],[4,5]]

💡 Note: No intervals overlap with [6,7], so all original intervals remain unchanged.

Constraints

1 ≤ intervals.length ≤ 10⁴
-10⁹ ≤ a_i < b_i ≤ 10⁹

Visualization

Tap to expand

Asked in

G Google 25 a Amazon 18 M Microsoft 15

The key insight is that each interval can have 5 possible relationships with the removal interval: no overlap, complete containment, left overlap, right overlap, or being completely contained. The optimal approach processes each interval once in O(n) time, checking these cases and keeping the non-overlapping parts. Time: O(n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Check All Points	O(R)	O(R)	Generate all points in intervals, filter out removed points, reconstruct intervals
One-Pass Interval Processing	O(n)	O(n)	Process each interval once, handling all overlap cases directly

Brute Force - Check All Points — Algorithm Steps

Step 1: Generate all integer points from intervals
Step 2: Filter out points in toBeRemoved
Step 3: Group consecutive points back into intervals

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Points

Convert intervals to discrete points

Filter Points

Remove points in toBeRemoved range

Reconstruct

Group remaining points back to intervals

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int** solution(int** intervals, int intervalsSize, int* toBeRemoved, int* returnSize) {
    int** result = malloc(intervalsSize * 2 * sizeof(int*));
    int count = 0;
    int removeStart = toBeRemoved[0];
    int removeEnd = toBeRemoved[1];
    
    for (int i = 0; i < intervalsSize; i++) {
        int start = intervals[i][0];
        int end = intervals[i][1];
        
        // Case 1: No overlap
        if (end <= removeStart || start >= removeEnd) {
            result[count] = malloc(2 * sizeof(int));
            result[count][0] = start;
            result[count][1] = end;
            count++;
        }
        // Case 2: Partial overlap
        else {
            // Left part remains
            if (start < removeStart) {
                result[count] = malloc(2 * sizeof(int));
                result[count][0] = start;
                result[count][1] = removeStart;
                count++;
            }
            // Right part remains
            if (end > removeEnd) {
                result[count] = malloc(2 * sizeof(int));
                result[count][0] = removeEnd;
                result[count][1] = end;
                count++;
            }
        }
    }
    
    *returnSize = count;
    return result;
}

int main() {
    // Simple parsing for demo - read intervals and toBeRemoved
    int intervals[10][2] = {{0,2},{3,4},{4,6}};
    int* intervalPtrs[3];
    for (int i = 0; i < 3; i++) {
        intervalPtrs[i] = intervals[i];
    }
    
    int toBeRemoved[2] = {1, 3};
    int returnSize;
    
    int** result = solution(intervalPtrs, 3, toBeRemoved, &returnSize);
    
    // Print result
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        if (i > 0) printf(",");
        printf("[%d,%d]", result[i][0], result[i][1]);
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(R)

R is the total range of all intervals - must process each point

✓ Linear Growth

Space Complexity

O(R)

Store all discrete points in the range

✓ Linear Space

12.5K Views

Medium Frequency

~15 min Avg. Time

456 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Check All Points — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler