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:

  1. The interval is completely outside the range of toBeRemoved and therefore remains unaffected.
  2. The interval is partially or completely inside the range of toBeRemoved and needs to be trimmed or removed.
  3. 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:

Which of the following is equvalent to O(3*2^n + n^3 + n!+ log n)?

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:

  1. The solution starts by initializing an empty list ans, which will eventually contain the resulting set of intervals after the removal process.

  2. It then enters a loop over each interval [a, b] in the intervals list.

  3. 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.
  4. 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.

  5. 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.
  6. The loops continue for all intervals in intervals, applying the above logic.

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

What is the worst case running time for finding an element in a binary search tree(not necessarily balanced) of size n?

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.

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

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27
1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30
1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

Python Solution

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

Java Solution

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

C++ Solution

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

Typescript Solution

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
Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following array represent a max heap?

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.


Recommended Readings


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫