Range Module (Add/Remove/Query Ranges)

🎯

Range Module (Add/Remove/Query Ranges)

hardDESIGNGoogleAmazon

Imagine you are building a system to track reserved time slots or IP address ranges dynamically, where intervals can be added, removed, and queried efficiently.

💡 This problem involves managing intervals dynamically, which is tricky because intervals can overlap, merge, or split. Beginners often struggle with how to efficiently store and update these intervals without scanning all data every time.

📋

Problem Statement

Design a data structure to track ranges of numbers. Implement the following methods: - addRange(left, right): Adds the half-open interval [left, right) to the tracked ranges. - queryRange(left, right): Returns true if every number in the interval [left, right) is currently being tracked. - removeRange(left, right): Removes the interval [left, right) from the tracked ranges. All intervals are half-open: they include left but exclude right.

1 ≤ number of calls ≤ 10^50 ≤ left < right ≤ 10^9Methods may be called in any order

💡

Example

Input"addRange(10, 20)\nremoveRange(14, 16)\nqueryRange(10, 14)\nqueryRange(13, 15)\nqueryRange(16, 17)"

Outputnull null true false true

After adding [10,20), removing [14,16) splits the range into [10,14) and [16,20). Querying [10,14) returns true, [13,15) returns false because 14-15 is removed, and [16,17) returns true.

• Adding a range that is completely inside an existing range → no change
• Removing a range that partially overlaps multiple intervals → intervals split correctly
• Querying a range that exactly matches an existing interval → returns true
• Querying a range outside any tracked intervals → returns false

⚠️

Common Mistakes

Not merging overlapping intervals correctly during addRange

Intervals remain fragmented, causing incorrect query results

✅ Ensure to merge all overlapping intervals before inserting the new merged interval

Incorrectly splitting intervals during removeRange

Intervals may be removed entirely or not split properly, causing false queries

✅ Split intervals into at most two parts around the removal range carefully

Using linear scan for large inputs

Solution times out or is too slow for big test cases

✅ Use binary search or balanced BST to reduce complexity

Off-by-one errors with half-open intervals

Queries or updates include/exclude wrong points

✅ Remember intervals are [left, right) and handle boundaries accordingly

Not updating the sorted list or keys after interval changes

Binary search or BST lookups fail or give incorrect results

✅ Always keep the sorted keys or BST structure consistent after modifications

🧠

Brute Force (Interval List with Full Scan)

💡 Starting with a simple list of intervals helps understand the problem deeply, even though it is inefficient. It shows the core challenges of merging and splitting intervals.

Intuition

Store all intervals in a list. For addRange, merge overlapping intervals by scanning the entire list. For removeRange, split or remove intervals by scanning all intervals. For queryRange, check if the entire query interval is covered by scanning.

Algorithm

1. Maintain a list of disjoint intervals sorted by start.
2. For addRange(left, right): iterate over intervals, merge overlapping ones with [left, right), and update the list.
3. For removeRange(left, right): iterate over intervals, remove or split intervals overlapping with [left, right).
4. For queryRange(left, right): check if any interval fully covers [left, right).

💡 The main difficulty is correctly merging and splitting intervals while maintaining a sorted list without overlaps.

</>

Code

class RangeModule:
    def __init__(self):
        self.intervals = []  # list of [start, end)

    def addRange(self, left: int, right: int) -> None:
        new_intervals = []
        placed = False
        for start, end in self.intervals:
            if end < left:
                new_intervals.append([start, end])
            elif start > right:
                if not placed:
                    new_intervals.append([left, right])
                    placed = True
                new_intervals.append([start, end])
            else:
                left = min(left, start)
                right = max(right, end)
        if not placed:
            new_intervals.append([left, right])
        self.intervals = new_intervals

    def queryRange(self, left: int, right: int) -> bool:
        for start, end in self.intervals:
            if start <= left and end >= right:
                return True
            if start > left:
                break
        return False

    def removeRange(self, left: int, right: int) -> None:
        new_intervals = []
        for start, end in self.intervals:
            if end <= left or start >= right:
                new_intervals.append([start, end])
            else:
                if start < left:
                    new_intervals.append([start, left])
                if end > right:
                    new_intervals.append([right, end])
        self.intervals = new_intervals

# Driver code
rm = RangeModule()
rm.addRange(10, 20)
rm.removeRange(14, 16)
print(rm.queryRange(10, 14))  # True
print(rm.queryRange(13, 15))  # False
print(rm.queryRange(16, 17))  # True

Line Notes

self.intervals = []Initialize empty list to store intervals

for start, end in self.intervals:Iterate over all intervals to merge or split

if end < left:Current interval ends before new range starts, keep as is

if start > right:Current interval starts after new range ends, insert new range if not placed

import java.util.*;

public class RangeModule {
    private List<int[]> intervals;

    public RangeModule() {
        intervals = new ArrayList<>();
    }

    public void addRange(int left, int right) {
        List<int[]> newIntervals = new ArrayList<>();
        boolean placed = false;
        for (int[] interval : intervals) {
            if (interval[1] < left) {
                newIntervals.add(interval);
            } else if (interval[0] > right) {
                if (!placed) {
                    newIntervals.add(new int[]{left, right});
                    placed = true;
                }
                newIntervals.add(interval);
            } else {
                left = Math.min(left, interval[0]);
                right = Math.max(right, interval[1]);
            }
        }
        if (!placed) {
            newIntervals.add(new int[]{left, right});
        }
        intervals = newIntervals;
    }

    public boolean queryRange(int left, int right) {
        for (int[] interval : intervals) {
            if (interval[0] <= left && interval[1] >= right) {
                return true;
            }
            if (interval[0] > left) {
                break;
            }
        }
        return false;
    }

    public void removeRange(int left, int right) {
        List<int[]> newIntervals = new ArrayList<>();
        for (int[] interval : intervals) {
            if (interval[1] <= left || interval[0] >= right) {
                newIntervals.add(interval);
            } else {
                if (interval[0] < left) {
                    newIntervals.add(new int[]{interval[0], left});
                }
                if (interval[1] > right) {
                    newIntervals.add(new int[]{right, interval[1]});
                }
            }
        }
        intervals = newIntervals;
    }

    // Main method for testing
    public static void main(String[] args) {
        RangeModule rm = new RangeModule();
        rm.addRange(10, 20);
        rm.removeRange(14, 16);
        System.out.println(rm.queryRange(10, 14)); // true
        System.out.println(rm.queryRange(13, 15)); // false
        System.out.println(rm.queryRange(16, 17)); // true
    }
}

Line Notes

intervals = new ArrayList<>();Initialize list to store intervals

for (int[] interval : intervals)Iterate all intervals to merge or split

if (interval[1] <= left || interval[0] >= right)Keep intervals that do not overlap removal range

if (!placed)Insert merged interval once after processing overlaps

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class RangeModule {
    vector<pair<int,int>> intervals;
public:
    RangeModule() {}

    void addRange(int left, int right) {
        vector<pair<int,int>> newIntervals;
        bool placed = false;
        for (auto &interval : intervals) {
            if (interval.second < left) {
                newIntervals.push_back(interval);
            } else if (interval.first > right) {
                if (!placed) {
                    newIntervals.push_back({left, right});
                    placed = true;
                }
                newIntervals.push_back(interval);
            } else {
                left = min(left, interval.first);
                right = max(right, interval.second);
            }
        }
        if (!placed) {
            newIntervals.push_back({left, right});
        }
        intervals = move(newIntervals);
    }

    bool queryRange(int left, int right) {
        for (auto &interval : intervals) {
            if (interval.first <= left && interval.second >= right) {
                return true;
            }
            if (interval.first > left) {
                break;
            }
        }
        return false;
    }

    void removeRange(int left, int right) {
        vector<pair<int,int>> newIntervals;
        for (auto &interval : intervals) {
            if (interval.second <= left || interval.first >= right) {
                newIntervals.push_back(interval);
            } else {
                if (interval.first < left) {
                    newIntervals.push_back({interval.first, left});
                }
                if (interval.second > right) {
                    newIntervals.push_back({right, interval.second});
                }
            }
        }
        intervals = move(newIntervals);
    }
};

int main() {
    RangeModule rm;
    rm.addRange(10, 20);
    rm.removeRange(14, 16);
    cout << boolalpha << rm.queryRange(10, 14) << "\n"; // true
    cout << boolalpha << rm.queryRange(13, 15) << "\n"; // false
    cout << boolalpha << rm.queryRange(16, 17) << "\n"; // true
    return 0;
}

Line Notes

vector<pair<int,int>> intervals;Store intervals as pairs in a vector

for (auto &interval : intervals)Loop over all intervals to merge or split

if (interval.second <= left || interval.first >= right)Keep intervals outside removal range

if (!placed)Add merged interval once after processing overlaps

class RangeModule {
    constructor() {
        this.intervals = [];
    }

    addRange(left, right) {
        const newIntervals = [];
        let placed = false;
        for (const [start, end] of this.intervals) {
            if (end < left) {
                newIntervals.push([start, end]);
            } else if (start > right) {
                if (!placed) {
                    newIntervals.push([left, right]);
                    placed = true;
                }
                newIntervals.push([start, end]);
            } else {
                left = Math.min(left, start);
                right = Math.max(right, end);
            }
        }
        if (!placed) {
            newIntervals.push([left, right]);
        }
        this.intervals = newIntervals;
    }

    queryRange(left, right) {
        for (const [start, end] of this.intervals) {
            if (start <= left && end >= right) {
                return true;
            }
            if (start > left) {
                break;
            }
        }
        return false;
    }

    removeRange(left, right) {
        const newIntervals = [];
        for (const [start, end] of this.intervals) {
            if (end <= left || start >= right) {
                newIntervals.push([start, end]);
            } else {
                if (start < left) {
                    newIntervals.push([start, left]);
                }
                if (end > right) {
                    newIntervals.push([right, end]);
                }
            }
        }
        this.intervals = newIntervals;
    }
}

// Test
const rm = new RangeModule();
rm.addRange(10, 20);
rm.removeRange(14, 16);
console.log(rm.queryRange(10, 14)); // true
console.log(rm.queryRange(13, 15)); // false
console.log(rm.queryRange(16, 17)); // true

Line Notes

this.intervals = []Initialize empty array to hold intervals

for (const [start, end] of this.intervals)Iterate all intervals to merge or split

if (end <= left || start >= right)Keep intervals outside removal range

if (!placed)Insert merged interval once after processing overlaps

⏱

Complexity

TimeO(n) per operation in worst case due to scanning all intervals

SpaceO(n) to store intervals

Each add/remove/query scans the entire list of intervals, which can grow linearly with number of operations.

💡 For n=1000 operations, this means up to 1000 scans each, totaling up to 1,000,000 operations, which is slow for large inputs.

Interview Verdict: TLE for large inputs, but useful to understand problem basics

This approach is too slow for large inputs but helps grasp interval merging and splitting before optimizing.

🧠

Balanced Tree / Sorted Containers with Binary Search

💡 Using a balanced tree or a sorted container with binary search improves efficiency by quickly locating intervals to merge or split, avoiding full scans.

Intuition

Store intervals in a balanced tree or sorted list. Use binary search to find where new intervals fit or overlap. Merge or split only affected intervals, keeping the rest untouched.

Algorithm

1. Maintain a sorted list of disjoint intervals.
2. Use binary search to find the position to insert or remove intervals.
3. For addRange, merge overlapping intervals around the insertion point.
4. For removeRange, split or remove intervals overlapping the removal range.
5. For queryRange, binary search to find if an interval covers the query.

💡 Binary search reduces the number of intervals to check, but merging and splitting logic remains similar to brute force.

</>

Code

import bisect

class RangeModule:
    def __init__(self):
        self.intervals = []  # list of [start, end)

    def addRange(self, left: int, right: int) -> None:
        i = bisect.bisect_left(self.intervals, [left, left])
        j = bisect.bisect_right(self.intervals, [right, right])

        if i != 0 and self.intervals[i-1][1] >= left:
            i -= 1
            left = min(left, self.intervals[i][0])
        if j != 0:
            right = max(right, self.intervals[j-1][1])

        self.intervals[i:j] = [[left, right]]

    def queryRange(self, left: int, right: int) -> bool:
        i = bisect.bisect_right(self.intervals, [left, float('inf')]) - 1
        if i < 0:
            return False
        return self.intervals[i][0] <= left and self.intervals[i][1] >= right

    def removeRange(self, left: int, right: int) -> None:
        i = bisect.bisect_left(self.intervals, [left, left])
        j = bisect.bisect_right(self.intervals, [right, right])

        newIntervals = []
        if i != 0 and self.intervals[i-1][1] > left:
            newIntervals.append([self.intervals[i-1][0], left])
            i -= 1
        if j != 0 and self.intervals[j-1][1] > right:
            newIntervals.append([right, self.intervals[j-1][1]])

        self.intervals[i:j] = newIntervals

# Driver code
rm = RangeModule()
rm.addRange(10, 20)
rm.removeRange(14, 16)
print(rm.queryRange(10, 14))  # True
print(rm.queryRange(13, 15))  # False
print(rm.queryRange(16, 17))  # True

Line Notes

i = bisect.bisect_left(self.intervals, [left, left])Find insertion index for left boundary

j = bisect.bisect_right(self.intervals, [right, right])Find insertion index for right boundary

if i != 0 and self.intervals[i-1][1] >= left:Check if previous interval overlaps left boundary

self.intervals[i:j] = [[left, right]]Replace overlapping intervals with merged interval

import java.util.*;

public class RangeModule {
    private List<int[]> intervals;

    public RangeModule() {
        intervals = new ArrayList<>();
    }

    private int bisectLeft(int target) {
        int low = 0, high = intervals.size();
        while (low < high) {
            int mid = (low + high) / 2;
            if (intervals.get(mid)[0] < target) low = mid + 1;
            else high = mid;
        }
        return low;
    }

    private int bisectRight(int target) {
        int low = 0, high = intervals.size();
        while (low < high) {
            int mid = (low + high) / 2;
            if (intervals.get(mid)[0] <= target) low = mid + 1;
            else high = mid;
        }
        return low;
    }

    public void addRange(int left, int right) {
        int i = bisectLeft(left);
        int j = bisectRight(right);

        if (i > 0 && intervals.get(i - 1)[1] >= left) {
            i--;
            left = Math.min(left, intervals.get(i)[0]);
        }
        if (j > 0) {
            right = Math.max(right, intervals.get(j - 1)[1]);
        }

        List<int[]> newIntervals = new ArrayList<>();
        for (int k = 0; k < i; k++) newIntervals.add(intervals.get(k));
        newIntervals.add(new int[]{left, right});
        for (int k = j; k < intervals.size(); k++) newIntervals.add(intervals.get(k));
        intervals = newIntervals;
    }

    public boolean queryRange(int left, int right) {
        int i = bisectRight(left) - 1;
        if (i < 0) return false;
        return intervals.get(i)[0] <= left && intervals.get(i)[1] >= right;
    }

    public void removeRange(int left, int right) {
        int i = bisectLeft(left);
        int j = bisectRight(right);

        List<int[]> newIntervals = new ArrayList<>();
        for (int k = 0; k < i; k++) newIntervals.add(intervals.get(k));

        if (i > 0 && intervals.get(i - 1)[1] > left) {
            newIntervals.add(new int[]{intervals.get(i - 1)[0], left});
            i--;
        }
        if (j > 0 && intervals.get(j - 1)[1] > right) {
            newIntervals.add(new int[]{right, intervals.get(j - 1)[1]});
        }

        for (int k = j; k < intervals.size(); k++) newIntervals.add(intervals.get(k));
        intervals = newIntervals;
    }

    public static void main(String[] args) {
        RangeModule rm = new RangeModule();
        rm.addRange(10, 20);
        rm.removeRange(14, 16);
        System.out.println(rm.queryRange(10, 14)); // true
        System.out.println(rm.queryRange(13, 15)); // false
        System.out.println(rm.queryRange(16, 17)); // true
    }
}

Line Notes

private List<int[]> intervals;Store intervals in a list sorted by start

bisectLeft(int target)Binary search to find left insertion index

if (i > 0 && intervals.get(i - 1)[1] >= left)Check if previous interval overlaps left boundary

intervals = newIntervals;Replace old intervals with updated merged list

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class RangeModule {
    vector<pair<int,int>> intervals;

    int bisectLeft(int target) {
        int low = 0, high = intervals.size();
        while (low < high) {
            int mid = (low + high) / 2;
            if (intervals[mid].first < target) low = mid + 1;
            else high = mid;
        }
        return low;
    }

    int bisectRight(int target) {
        int low = 0, high = intervals.size();
        while (low < high) {
            int mid = (low + high) / 2;
            if (intervals[mid].first <= target) low = mid + 1;
            else high = mid;
        }
        return low;
    }

public:
    RangeModule() {}

    void addRange(int left, int right) {
        int i = bisectLeft(left);
        int j = bisectRight(right);

        if (i > 0 && intervals[i-1].second >= left) {
            i--;
            left = min(left, intervals[i].first);
        }
        if (j > 0) {
            right = max(right, intervals[j-1].second);
        }

        vector<pair<int,int>> newIntervals;
        for (int k = 0; k < i; k++) newIntervals.push_back(intervals[k]);
        newIntervals.push_back({left, right});
        for (int k = j; k < (int)intervals.size(); k++) newIntervals.push_back(intervals[k]);
        intervals = move(newIntervals);
    }

    bool queryRange(int left, int right) {
        int i = bisectRight(left) - 1;
        if (i < 0) return false;
        return intervals[i].first <= left && intervals[i].second >= right;
    }

    void removeRange(int left, int right) {
        int i = bisectLeft(left);
        int j = bisectRight(right);

        vector<pair<int,int>> newIntervals;
        for (int k = 0; k < i; k++) newIntervals.push_back(intervals[k]);

        if (i > 0 && intervals[i-1].second > left) {
            newIntervals.push_back({intervals[i-1].first, left});
            i--;
        }
        if (j > 0 && intervals[j-1].second > right) {
            newIntervals.push_back({right, intervals[j-1].second});
        }

        for (int k = j; k < (int)intervals.size(); k++) newIntervals.push_back(intervals[k]);
        intervals = move(newIntervals);
    }
};

int main() {
    RangeModule rm;
    rm.addRange(10, 20);
    rm.removeRange(14, 16);
    cout << boolalpha << rm.queryRange(10, 14) << "\n"; // true
    cout << boolalpha << rm.queryRange(13, 15) << "\n"; // false
    cout << boolalpha << rm.queryRange(16, 17) << "\n"; // true
    return 0;
}

Line Notes

int bisectLeft(int target)Binary search for left insertion index

if (i > 0 && intervals[i-1].second >= left)Check overlap with previous interval

intervals = move(newIntervals);Replace intervals with updated merged list

int i = bisectRight(left) - 1;Find interval that may cover query start

class RangeModule {
    constructor() {
        this.intervals = [];
    }

    bisectLeft(target) {
        let low = 0, high = this.intervals.length;
        while (low < high) {
            let mid = (low + high) >> 1;
            if (this.intervals[mid][0] < target) low = mid + 1;
            else high = mid;
        }
        return low;
    }

    bisectRight(target) {
        let low = 0, high = this.intervals.length;
        while (low < high) {
            let mid = (low + high) >> 1;
            if (this.intervals[mid][0] <= target) low = mid + 1;
            else high = mid;
        }
        return low;
    }

    addRange(left, right) {
        let i = this.bisectLeft(left);
        let j = this.bisectRight(right);

        if (i > 0 && this.intervals[i - 1][1] >= left) {
            i--;
            left = Math.min(left, this.intervals[i][0]);
        }
        if (j > 0) {
            right = Math.max(right, this.intervals[j - 1][1]);
        }

        const newIntervals = [];
        for (let k = 0; k < i; k++) newIntervals.push(this.intervals[k]);
        newIntervals.push([left, right]);
        for (let k = j; k < this.intervals.length; k++) newIntervals.push(this.intervals[k]);
        this.intervals = newIntervals;
    }

    queryRange(left, right) {
        let i = this.bisectRight(left) - 1;
        if (i < 0) return false;
        return this.intervals[i][0] <= left && this.intervals[i][1] >= right;
    }

    removeRange(left, right) {
        let i = this.bisectLeft(left);
        let j = this.bisectRight(right);

        const newIntervals = [];
        for (let k = 0; k < i; k++) newIntervals.push(this.intervals[k]);

        if (i > 0 && this.intervals[i - 1][1] > left) {
            newIntervals.push([this.intervals[i - 1][0], left]);
            i--;
        }
        if (j > 0 && this.intervals[j - 1][1] > right) {
            newIntervals.push([right, this.intervals[j - 1][1]]);
        }

        for (let k = j; k < this.intervals.length; k++) newIntervals.push(this.intervals[k]);
        this.intervals = newIntervals;
    }
}

// Test
const rm = new RangeModule();
rm.addRange(10, 20);
rm.removeRange(14, 16);
console.log(rm.queryRange(10, 14)); // true
console.log(rm.queryRange(13, 15)); // false
console.log(rm.queryRange(16, 17)); // true

Line Notes

this.intervals = []Initialize empty array for intervals

bisectLeft(target)Binary search for left insertion index

if (i > 0 && this.intervals[i - 1][1] >= left)Check overlap with previous interval

this.intervals = newIntervals;Replace intervals with updated merged list

⏱

Complexity

TimeO(log n) per operation on average due to binary search and limited merges

SpaceO(n) to store intervals

Binary search reduces scanning to logarithmic time, and only intervals overlapping the update range are merged or split.

💡 For n=100000 operations, this approach can handle them efficiently, unlike brute force.

Interview Verdict: Accepted and efficient for large inputs

This approach balances simplicity and efficiency, suitable for interviews and real-world use.

🧠

TreeMap / Balanced BST with Interval Merging (Optimal)

💡 Using a balanced BST keyed by interval start with careful merging and splitting yields optimal performance and clean code.

Intuition

Store intervals in a balanced BST keyed by start. For add/remove, find affected intervals using floor/ceiling operations, merge or split as needed. For query, find floor interval and check coverage.

Algorithm

1. Use a balanced BST (e.g., TreeMap) keyed by interval start.
2. For addRange, find intervals overlapping [left, right), merge them, and update the BST.
3. For removeRange, find overlapping intervals, remove or split them, and update the BST.
4. For queryRange, find the floor interval for left and check if it covers [left, right).

💡 This approach leverages BST operations to minimize work and maintain intervals efficiently.

</>

Code

from bisect import bisect_left, bisect_right

class RangeModule:
    def __init__(self):
        self.intervals = dict()
        self.starts = []

    def addRange(self, left: int, right: int) -> None:
        i = bisect_left(self.starts, left)
        j = bisect_right(self.starts, right)

        if i != 0 and self.intervals[self.starts[i-1]] >= left:
            i -= 1
            left = min(left, self.starts[i])
        if j != 0:
            right = max(right, self.intervals[self.starts[j-1]])

        # Remove overlapping intervals
        for k in self.starts[i:j]:
            del self.intervals[k]
        self.starts[i:j] = [left]
        self.intervals[left] = right

    def queryRange(self, left: int, right: int) -> bool:
        i = bisect_right(self.starts, left) - 1
        if i < 0:
            return False
        return self.intervals[self.starts[i]] >= right

    def removeRange(self, left: int, right: int) -> None:
        i = bisect_left(self.starts, left)
        j = bisect_right(self.starts, right)

        newIntervals = []
        if i != 0 and self.intervals[self.starts[i-1]] > left:
            start = self.starts[i-1]
            end = self.intervals[start]
            if start < left:
                newIntervals.append((start, left))
            i -= 1
        if j != 0 and self.intervals[self.starts[j-1]] > right:
            start = right
            end = self.intervals[self.starts[j-1]]
            newIntervals.append((start, end))

        # Remove overlapping intervals
        for k in self.starts[i:j]:
            del self.intervals[k]
        self.starts[i:j] = []

        # Insert new intervals
        for s, e in newIntervals:
            idx = bisect_left(self.starts, s)
            self.starts.insert(idx, s)
            self.intervals[s] = e

# Driver code
rm = RangeModule()
rm.addRange(10, 20)
rm.removeRange(14, 16)
print(rm.queryRange(10, 14))  # True
print(rm.queryRange(13, 15))  # False
print(rm.queryRange(16, 17))  # True

Line Notes

self.intervals = dict()Dictionary to map start to end of intervals for O(1) access

self.starts = []Sorted list of interval start points for binary search

i = bisect_left(self.starts, left)Find insertion index for left boundary using binary search

del self.intervals[k]Remove intervals overlapping the update range to maintain correctness

import java.util.*;

public class RangeModule {
    private TreeMap<Integer, Integer> intervals;

    public RangeModule() {
        intervals = new TreeMap<>();
    }

    public void addRange(int left, int right) {
        Integer start = intervals.floorKey(left);
        if (start != null && intervals.get(start) >= left) {
            left = Math.min(left, start);
            right = Math.max(right, intervals.get(start));
            intervals.remove(start);
        }

        Integer next = intervals.ceilingKey(left);
        while (next != null && next <= right) {
            right = Math.max(right, intervals.get(next));
            intervals.remove(next);
            next = intervals.ceilingKey(left);
        }

        intervals.put(left, right);
    }

    public boolean queryRange(int left, int right) {
        Integer start = intervals.floorKey(left);
        if (start == null) return false;
        return intervals.get(start) >= right;
    }

    public void removeRange(int left, int right) {
        Integer start = intervals.floorKey(left);
        if (start != null && intervals.get(start) > left) {
            int end = intervals.get(start);
            if (start < left) intervals.put(start, left);
            if (end > right) intervals.put(right, end);
            else intervals.remove(start);
        }

        Integer next = intervals.ceilingKey(left);
        while (next != null && next < right) {
            int end = intervals.get(next);
            intervals.remove(next);
            if (end > right) intervals.put(right, end);
            next = intervals.ceilingKey(left);
        }
    }

    public static void main(String[] args) {
        RangeModule rm = new RangeModule();
        rm.addRange(10, 20);
        rm.removeRange(14, 16);
        System.out.println(rm.queryRange(10, 14)); // true
        System.out.println(rm.queryRange(13, 15)); // false
        System.out.println(rm.queryRange(16, 17)); // true
    }
}

Line Notes

private TreeMap<Integer, Integer> intervals;TreeMap stores intervals keyed by start for efficient floor/ceiling queries

Integer start = intervals.floorKey(left);Find interval with start <= left to check overlap

while (next != null && next <= right)Remove all intervals overlapping [left, right) to merge

intervals.put(left, right);Insert merged interval after removing overlaps

#include <iostream>
#include <map>
#include <vector>

using namespace std;

class RangeModule {
    map<int,int> intervals;
public:
    RangeModule() {}

    void addRange(int left, int right) {
        auto it = intervals.upper_bound(left);
        if (it != intervals.begin()) {
            --it;
            if (it->second < left) ++it;
        }

        while (it != intervals.end() && it->first <= right) {
            left = min(left, it->first);
            right = max(right, it->second);
            it = intervals.erase(it);
        }
        intervals[left] = right;
    }

    bool queryRange(int left, int right) {
        auto it = intervals.upper_bound(left);
        if (it == intervals.begin()) return false;
        --it;
        return it->second >= right;
    }

    void removeRange(int left, int right) {
        auto it = intervals.upper_bound(left);
        if (it != intervals.begin()) {
            --it;
            if (it->second <= left) ++it;
        }

        vector<pair<int,int>> toAdd;
        while (it != intervals.end() && it->first < right) {
            if (it->first < left) toAdd.push_back({it->first, left});
            if (it->second > right) toAdd.push_back({right, it->second});
            it = intervals.erase(it);
        }
        for (auto &p : toAdd) intervals[p.first] = p.second;
    }
};

int main() {
    RangeModule rm;
    rm.addRange(10, 20);
    rm.removeRange(14, 16);
    cout << boolalpha << rm.queryRange(10, 14) << "\n"; // true
    cout << boolalpha << rm.queryRange(13, 15) << "\n"; // false
    cout << boolalpha << rm.queryRange(16, 17) << "\n"; // true
    return 0;
}

Line Notes

map<int,int> intervals;Use map to store intervals keyed by start for ordered access

auto it = intervals.upper_bound(left);Find first interval with start > left to locate overlaps

while (it != intervals.end() && it->first <= right)Remove and merge overlapping intervals

intervals[left] = right;Insert merged interval after removing overlaps

class RangeModule {
    constructor() {
        this.intervals = new Map();
        this.starts = [];
    }

    bisectLeft(target) {
        let low = 0, high = this.starts.length;
        while (low < high) {
            let mid = (low + high) >> 1;
            if (this.starts[mid] < target) low = mid + 1;
            else high = mid;
        }
        return low;
    }

    addRange(left, right) {
        let i = this.bisectLeft(left);
        let j = this.bisectLeft(right);

        if (i > 0 && this.intervals.get(this.starts[i - 1]) >= left) {
            i--;
            left = Math.min(left, this.starts[i]);
        }
        if (j > 0) {
            right = Math.max(right, this.intervals.get(this.starts[j - 1]));
        }

        for (let k = i; k < j; k++) {
            this.intervals.delete(this.starts[k]);
        }
        this.starts.splice(i, j - i, left);
        this.intervals.set(left, right);
    }

    queryRange(left, right) {
        let i = this.bisectLeft(left) - 1;
        if (i < 0) return false;
        return this.intervals.get(this.starts[i]) >= right;
    }

    removeRange(left, right) {
        let i = this.bisectLeft(left);
        let j = this.bisectLeft(right);

        let newIntervals = [];
        if (i > 0 && this.intervals.get(this.starts[i - 1]) > left) {
            newIntervals.push([this.starts[i - 1], left]);
            i--;
        }
        if (j > 0 && this.intervals.get(this.starts[j - 1]) > right) {
            newIntervals.push([right, this.intervals.get(this.starts[j - 1])]);
        }

        for (let k = i; k < j; k++) {
            this.intervals.delete(this.starts[k]);
        }
        this.starts.splice(i, j - i);

        for (let [s, e] of newIntervals) {
            let idx = this.bisectLeft(s);
            this.starts.splice(idx, 0, s);
            this.intervals.set(s, e);
        }
    }
}

// Test
const rm = new RangeModule();
rm.addRange(10, 20);
rm.removeRange(14, 16);
console.log(rm.queryRange(10, 14)); // true
console.log(rm.queryRange(13, 15)); // false
console.log(rm.queryRange(16, 17)); // true

Line Notes

this.intervals = new Map();Map stores intervals keyed by start for quick access

this.starts = [];Sorted array of interval starts for binary search

bisectLeft(target)Binary search to find insertion index for efficient updates

this.intervals.delete(this.starts[k]);Remove intervals overlapping update range to maintain correctness

⏱

Complexity

TimeO(log n) per operation due to balanced BST operations

SpaceO(n) to store intervals

BST operations like floorKey and ceilingKey allow efficient interval lookups and updates.

💡 This approach is the most efficient and clean for large scale interval management.

Interview Verdict: Accepted and optimal for large inputs

This is the recommended approach for production and interviews due to its efficiency and clarity.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, coding the balanced BST or binary search approach is best for efficiency and clarity.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n) per operation	O(n)	No	N/A	Mention only - never code due to inefficiency
2. Binary Search on Sorted List	O(log n) per operation	O(n)	No	N/A	Good to code if balanced BST not allowed
3. Balanced BST (TreeMap)	O(log n) per operation	O(n)	No	N/A	Optimal approach to code in interviews

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Clarify problem constraints and interval definitions.Explain brute force approach to show understanding of interval merging and splitting.Introduce binary search optimization to improve efficiency.Present balanced BST approach as optimal solution.Discuss time and space complexities and tradeoffs.

Time Allocation

Clarify: 3min → Approach: 5min → Code: 10min → Test: 5min. Total ~23min

What the Interviewer Tests

Interviewer tests your understanding of interval merging, ability to optimize naive solutions, and knowledge of data structures like balanced BSTs or sorted containers.

Common Follow-ups

• How would you handle very large ranges efficiently? → Use segment trees or interval trees.
• Can you support counting how many times a number is covered? → Use augmented data structures with counts.

💡 Follow-ups often test your ability to extend the data structure for more complex queries or scale.

🔍

Pattern Recognition

When to Use

1) Problem involves dynamic intervals or ranges, 2) Requires add/remove/query operations, 3) Intervals can overlap and must be merged/split, 4) Efficient queries needed

Signature Phrases

addRange(left, right)removeRange(left, right)queryRange(left, right)

NOT This Pattern When

Problems that only query static intervals or do not require dynamic updates

Similar Problems

My Calendar I/II/III - similar interval insertion and overlap checksInsert Interval - merging intervals after insertionData Stream as Disjoint Intervals - dynamic interval tracking

Practice

1. You need to design a data structure that supports inserting elements (including duplicates), removing one occurrence of an element, and retrieving a random element--all in average O(1) time. Which approach best guarantees these time complexities?

easy

A. Use a simple list and perform linear search for removals.

B. Use a balanced binary search tree to maintain elements and their counts.

C. Use a hash map to store element to indices mapping, combined with a list to store elements, updating indices on insert and remove.

D. Use a queue to track insertion order and a hash set for membership checks.

Solution

1. Step 1: Understand the operations required

   Insert, remove (one occurrence), and getRandom must all be average O(1), even with duplicates.

2. Step 2: Evaluate approaches

   A simple list with linear search (A) leads to O(n) removals. Balanced BST (C) has O(log n) operations. Queue and hash set (D) do not support random access efficiently. Hash map + list with index tracking (B) supports O(1) insert, remove, and getRandom by maintaining indices of duplicates.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Hash map + list with index tracking enables O(1) average operations [OK]

Hint: Hash map + list with index tracking enables O(1) ops [OK]

Common Mistakes:

• Assuming balanced BST can do O(1) getRandom
• Using linear search for removal
• Ignoring duplicates in data structure

2. What is the amortized time complexity of the put operation in the optimal LFU Cache implementation using a frequency map of doubly linked lists and hash maps?

medium

A. O(n), where n is the number of keys in the cache

B. O(f), where f is the number of distinct frequencies

C. O(log n), due to maintaining frequency order

D. O(1), amortized constant time

Solution

1. Step 1: Analyze data structures used

   Hash maps provide O(1) access to keys and frequencies. Doubly linked lists allow O(1) insertion and deletion of keys within frequency groups.

2. Step 2: Consider operations in put

   Eviction and frequency updates involve O(1) operations on hash maps and linked lists. Frequency increments and min frequency updates are also O(1).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Optimal LFU cache achieves O(1) amortized put [OK]

Hint: Hash maps + linked lists enable O(1) put [OK]

Common Mistakes:

• Assuming O(n) due to scanning keys
• Thinking frequency updates cost O(log n)
• Confusing distinct frequencies with n

3. Suppose the UndergroundSystem is extended to allow multiple check-ins by the same passenger without requiring a check-out first (i.e., passengers can start multiple trips before finishing any). Which modification to the data structure or algorithm is necessary to handle this correctly?

hard

A. Keep a stack of check-in nodes per passenger id to track multiple active trips.

B. Use a hash map from passenger id to a single check-in node, overwriting previous check-ins.

C. Store all check-ins in a linked list and traverse fully on each checkOut to find the earliest unmatched check-in.

D. Disallow multiple check-ins by the same passenger to avoid complexity.

Solution

1. Step 1: Understand the problem extension

   Passengers can have multiple active trips simultaneously, so a single check-in per id is insufficient.

2. Step 2: Choose data structure to track multiple check-ins

   A stack per passenger id allows tracking multiple check-ins in order, enabling correct matching on checkOut.

3. Step 3: Why other options fail

   Overwriting check-ins loses data (A). Traversing full list each time (C) is inefficient. Disallowing multiple check-ins (D) is not a solution.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Stack per id supports multiple active trips correctly [OK]

Hint: Stack per id tracks multiple active check-ins [OK]

Common Mistakes:

• Overwriting check-in info loses data

4. Suppose the data stream allows duplicate numbers to be removed after insertion, requiring support for removeNum(num). Which modification to the balanced two heaps approach is necessary to maintain correct median retrieval?

hard

A. Use a balanced binary search tree instead of heaps to allow efficient removals.

B. Ignore removals and only add numbers, as removals break the heap structure.

C. Rebuild both heaps from scratch after every removal to maintain heap properties.

D. Add a delayed deletion map to mark elements for lazy removal and prune heaps during addNum and findMedian.

Solution

1. Step 1: Understand removal challenges

   Heaps do not support efficient arbitrary removals, so direct removal breaks heap properties.

2. Step 2: Use lazy deletion

   Maintain a delayed deletion map to mark elements for removal and prune them lazily during heap operations, preserving heap structure and efficiency.

3. Step 3: Avoid costly rebuilds

   Rebuilding heaps on every removal is inefficient; ignoring removals is incorrect.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Lazy deletion with pruning maintains correctness and efficiency [OK]

Hint: Lazy deletion map enables efficient removals in heaps [OK]

Common Mistakes:

• Rebuilding heaps on every removal
• Ignoring removals breaks correctness

5. Suppose the LFU cache must support a new operation: reuse(key) which resets the frequency of key to 1 without changing its value. Which modification to the optimal LFU cache design correctly supports this operation without breaking O(1) complexity?

hard

A. Simply set the frequency of the key to 1 in the key_val_freq map without moving it between frequency lists

B. Clear the entire cache and reinsert the key with frequency 1

C. Remove the key from its current frequency list and add it to freq=1 list, update min_freq to 1

D. Increment the frequency of the key by 1 and then reset min_freq to 1

Solution

1. Step 1: Understand reuse operation

   Reuse resets frequency to 1, so the key must move from its current frequency list to the freq=1 list.

2. Step 2: Update data structures accordingly

   Remove key from old freq list, add to freq=1 list, and update min_freq to 1 to reflect the new minimum frequency.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Moving key between freq lists and updating min_freq preserves O(1) operations [OK]

Hint: Move key to freq=1 list and update min_freq [OK]

Common Mistakes:

• Not moving key between frequency lists
• Resetting frequency without updating min_freq
• Clearing cache is inefficient and breaks O(1)