1272. Remove Interval

Problem Description

In this problem, we're dealing with a mathematical representation of sets using intervals of real numbers. Each interval is represented as [a, b), which means it includes all real numbers x such that a <= x < b.

We are provided with two things:

A sorted list of disjoint intervals, intervals, which together make up a set. The intervals are disjoint, meaning they do not overlap, and they are sorted in ascending order based on their starting points.
Another interval, toBeRemoved, which we need to remove from the set represented by intervals.

Our objective is to return a new set of real numbers obtained by removing toBeRemoved from intervals. This set also needs to be represented as a sorted list of disjoint intervals. We need to consider that part of an interval might be removed, all of it might be removed, or it might not be affected at all, depending on whether it overlaps with toBeRemoved.

Intuition

The key to solving this problem is to examine each interval in intervals and figure out its relation with toBeRemoved. There are three possibilities:

The interval is completely outside the range of toBeRemoved and therefore remains unaffected.
The interval is partially or completely inside the range of toBeRemoved and needs to be trimmed or removed.
The interval straddles the edges of toBeRemoved and might need to be split into two intervals.

Given that intervals is sorted, we can iterate over each interval and handle the cases as follows:

If the current interval ends before toBeRemoved starts or starts after toBeRemoved ends, it's disjoint and can be added to the result as is.
If there is overlap, we may need to trim the current interval. If the start of the current interval is before toBeRemoved, we can take the portion from the interval's start up to the start of toBeRemoved. Similarly, if the interval ends after toBeRemoved, we can take the portion from the end of toBeRemoved to the interval's end.
We need to handle the edge cases where toBeRemoved completely covers an interval, in which case we add nothing to the result for that interval.

By iterating through each interval once, and considering these cases, we can construct our output set of intervals with toBeRemoved taken out.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

How would you design a stack which has a function min that returns the minimum element in the stack, in addition to push and pop? All push, pop, min should have running time O(1).

Add another stack to store the minimumsAdd a heap to store the minimumsAdd a variable to track the minimumAdd a queue to store the minumums

I don’t know

Solution Approach

The provided solution employs a straightforward approach to tackle the problem by iterating through each interval in the given sorted list intervals and comparing it with the toBeRemoved interval. Here's a step by step process used in the implementation:

The solution starts by initializing an empty list ans, which will eventually contain the resulting set of intervals after the removal process.
It then enters a loop over each interval [a, b] in the intervals list.
For each interval, it checks whether there is an intersection with the toBeRemoved interval, [x, y]. It does this by verifying two conditions:
- If a >= y, then the interval [a, b] is completely after toBeRemoved and thus is unaffected.
- If b <= x, then the interval [a, b] is completely before toBeRemoved and also remains unaffected.
When either of the above conditions is true, the current interval can be added directly to the ans list without modification since it doesn't intersect with toBeRemoved.
If the interval does intersect with toBeRemoved, the solution needs to handle slicing the interval into potentially two parts:
- If the start of the interval a is before x (the start of toBeRemoved), then the segment [a, x) of the original interval is unaffected by the removal and is added to ans.
- Similarly, if the end of the interval b is after y (the end of toBeRemoved), then the segment [y, b) remains after the removal and is also added to ans.
The loops continue for all intervals in intervals, applying the above logic.
After processing all intervals, the solution returns the ans list, which now contains the modified set of intervals, representing the original set with the toBeRemoved interval excluded.

The algorithm makes use of simple conditional checks and relies on the sorted nature of the input intervals for its correctness and efficiency. The overall time complexity is O(n), where n is the number of intervals in intervals, since it processes each interval exactly once.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Example Walkthrough

Let's consider the following small example to illustrate the solution approach. Assume we have the following intervals list and toBeRemoved interval:

intervals = [[1, 4), [6, 8), [10, 13)]
toBeRemoved = [7, 12)

Using the steps outlined in the solution approach:

Step 1: Initialize Result List

ans = [] (empty to begin with)

Step 2: Loop Over Each Interval in `intervals`

Current interval [1, 4).

Step 3: Check for Intersection with `toBeRemoved`

The interval [1, 4) does not intersect with [7, 12), as 4 < 7.
Since the interval is completely before toBeRemoved, add it to ans: ans = [[1, 4)].

Next, we take the interval [6, 8).

Step 3: Check for Intersection with `toBeRemoved`

The interval [6, 8) does intersect with [7, 12) since the interval starts before and ends in the range of toBeRemoved.

Step 5: Handle Slicing the Interval

The start of the interval 6 is before the start of toBeRemoved 7.
Add the segment [6, 7) to ans: ans = [[1, 4), [6, 7)].

Next, we take the interval [10, 13).

Step 3: Check for Intersection with `toBeRemoved`

The interval [10, 13) does intersect with [7, 12), because the interval starts inside and ends after the range of toBeRemoved.

Step 5: Handle Slicing the Interval

Since the end of the interval 13 is after the end of toBeRemoved 12, we add the segment [12, 13) to ans: ans = [[1, 4), [6, 7), [12, 13)].

Step 6: Continue the Loop

No more intervals to process.

Step 7: Return the `ans` List

The final result is ans = [[1, 4), [6, 7), [12, 13)].

The solution approach has efficiently handled the example intervals list by considering the toBeRemoved interval and has produced a result that correctly represents the set after removal.

Solution Implementation

1from typing import List
2
3class Solution:
4    def removeInterval(self, intervals: List[List[int]], toBeRemoved: List[int]) -> List[List[int]]:
5        # Extracting start and end points of the interval to be removed
6        removal_start, removal_end = toBeRemoved
7      
8        # This will store the final list of intervals after removing the specified interval
9        updated_intervals = []
10      
11        # Iterate through each interval in the provided list of intervals
12        for interval_start, interval_end in intervals:
13            # If the current interval doesn't overlap with the interval to be removed,
14            # we can add it to the updated list as-is
15            if interval_start >= removal_end or interval_end <= removal_start:
16                updated_intervals.append([interval_start, interval_end])
17            else:
18                # If there is an overlap and the start of the current interval
19                # is before the start of the interval to be removed,
20                # add the non-overlapping part to the result.
21                if interval_start < removal_start:
22                    updated_intervals.append([interval_start, removal_start])
23              
24                # Similarly, if the end of the current interval is after the end of
25                # the interval to be removed, add the non-overlapping part to the result.
26                if interval_end > removal_end:
27                    updated_intervals.append([removal_end, interval_end])
28      
29        # Return the updated list of intervals after removal
30        return updated_intervals
31

1class Solution {
2
3    // Function to remove a specific interval from a list of intervals
4    public List<List<Integer>> removeInterval(int[][] intervals, int[] toBeRemoved) {
5        // x and y represents the start and end of the interval to be removed
6        int removeStart = toBeRemoved[0];
7        int removeEnd = toBeRemoved[1];
8
9        // Preparing a list to store the resulting intervals after removal
10        List<List<Integer>> updatedIntervals = new ArrayList<>();
11
12        // Iterate through each interval in the input intervals array
13        for (int[] interval : intervals) {
14            // a and b represents the start and end of the current interval
15            int start = interval[0];
16            int end = interval[1];
17
18            // Check if the current interval is completely before or after the interval to be removed
19            if (start >= removeEnd || end <= removeStart) {
20                // Add to the result as there is no overlap
21                updatedIntervals.add(Arrays.asList(start, end));
22            } else {
23                // If there's an overlap, we may need to add the non-overlapping parts of the interval
24                if (start < removeStart) {
25                    // Add the part of the interval before the interval to be removed
26                    updatedIntervals.add(Arrays.asList(start, removeStart));
27                }
28                if (end > removeEnd) {
29                    // Add the part of the interval after the interval to be removed
30                    updatedIntervals.add(Arrays.asList(removeEnd, end));
31                }
32            }
33        }
34
35        // Return the list of updated intervals
36        return updatedIntervals;
37    }
38}
39

1class Solution {
2public:
3    // Function to remove the interval `toBeRemoved` from the list of `intervals`
4    vector<vector<int>> removeInterval(vector<vector<int>>& intervals, vector<int>& toBeRemoved) {
5        // toBeRemoved[0] is the start of the interval to be removed, toBeRemoved[1] is the end
6        int removeStart = toBeRemoved[0], removeEnd = toBeRemoved[1];
7        vector<vector<int>> updatedIntervals; // This will store the final intervals after removal
8      
9        // Iterate through all intervals
10        for (auto& interval : intervals) {
11            int start = interval[0], end = interval[1]; // Start and end of the current interval
12          
13            // Check if the current interval is completely outside the toBeRemoved interval
14            if (start >= removeEnd || end <= removeStart) {
15                // Add interval to the result as it doesn't overlap with toBeRemoved
16                updatedIntervals.push_back(interval);
17            } else {
18                // Check if part of the interval is before toBeRemoved
19                if (start < removeStart) {
20                    // Add the part of interval before toBeRemoved
21                    updatedIntervals.push_back({start, removeStart});
22                }
23                // Check if part of the interval is after toBeRemoved
24                if (end > removeEnd) {
25                    // Add the part of interval after toBeRemoved
26                    updatedIntervals.push_back({removeEnd, end});
27                }
28            }
29        }
30        // Return the final list of intervals after removal
31        return updatedIntervals;
32    }
33};
34

1// Define the interval type as a tuple of two numbers
2type Interval = [number, number];
3
4// Function to remove the interval `toBeRemoved` from the list of `intervals`
5function removeInterval(intervals: Interval[], toBeRemoved: Interval): Interval[] {
6    // `toBeRemoved[0]` is the start of the interval to be removed, `toBeRemoved[1]` is the end
7    const removeStart = toBeRemoved[0];
8    const removeEnd = toBeRemoved[1];
9  
10    // This will store the final intervals after removal
11    const updatedIntervals: Interval[] = [];
12  
13    // Iterate through all intervals
14    for (const interval of intervals) {
15        // `start` and `end` of the current interval
16        const start = interval[0];
17        const end = interval[1];
18      
19        // Check if the current interval is completely outside the toBeRemoved interval
20        if (start >= removeEnd || end <= removeStart) {
21            // Add the interval to the result as it doesn't overlap with toBeRemoved
22            updatedIntervals.push(interval);
23        } else {
24            // Check if part of the interval is before toBeRemoved
25            if (start < removeStart) {
26                // Add the part of the interval before toBeRemoved
27                updatedIntervals.push([start, removeStart]);
28            }
29            // Check if part of the interval is after toBeRemoved
30            if (end > removeEnd) {
31                // Add the part of the interval after toBeRemoved
32                updatedIntervals.push([removeEnd, end]);
33            }
34        }
35    }
36  
37    // Return the final list of intervals after removal
38    return updatedIntervals;
39}
40

Not Sure What to Study? Take the 2-min Quiz：

What are the most two important steps in writing a depth first search function? (Select 2)

Determine state to pass down to recursive function callDetermine return valueDetermine how many recursive calls will be madeTracing the recursive calls

Time and Space Complexity

The code snippet provided is for a function that removes an interval from a list of existing intervals and returns the resulting list of disjoint intervals after the removal. The computational complexity analysis for time and space complexity is as follows:

Time complexity:

The primary operation in this function occurs within a single loop that iterates over all the original intervals in the list intervals. Within each iteration of the loop, the function performs constant-time checks and operations to possibly add up to two intervals to the ans list. Since there are no nested loops and the operations inside the loop are of constant time complexity, the overall time complexity of the function is directly proportional to the number of intervals n in the input list. Therefore, the time complexity is O(n).

Space complexity:

For space complexity, the function creates a new list ans to store the resulting intervals after the potential removal and modification of the existing intervals. In the worst-case scenario, where no interval is completely removed and every interval needs to be split into two parts (one occurring before x and one after y of the toBeRemoved interval), the resulting list could potentially hold up to 2n intervals - doubling the input size. However, notice that this is a linear relationship with respect to the number of input intervals n. Therefore, the space complexity of the function is O(n) as well.

In summary, both the time complexity and space complexity of the given code are O(n), where n is the number of intervals in the input list intervals.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)

Optimal substructureOverlapping subproblemsNon-overlapping subproblemsConstant time subproblems

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

1272. Remove Interval

Problem Description

Intuition

Solution Approach

Example Walkthrough

Step 1: Initialize Result List

Step 2: Loop Over Each Interval in intervals

Step 3: Check for Intersection with toBeRemoved

Step 3: Check for Intersection with toBeRemoved

Step 5: Handle Slicing the Interval

Step 3: Check for Intersection with toBeRemoved

Step 2: Loop Over Each Interval in `intervals`

Step 3: Check for Intersection with `toBeRemoved`

Step 3: Check for Intersection with `toBeRemoved`

Step 3: Check for Intersection with `toBeRemoved`

Step 7: Return the `ans` List