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. Consider the following Python code snippet for the MedianFinder class using two heaps. After adding the numbers 1, 5, and 3 in that order, what is the value of the median returned by findMedian()?

easy

A. 1.0

B. 3.0

C. 5.0

D. 2.0

Solution

1. Step 1: Insert 1

   Low heap empty, push -1 to low; low_size=1, high_size=0.

2. Step 2: Insert 5

   5 > -low[0] (which is 1), push 5 to high; low_size=1, high_size=1; heaps balanced.

3. Step 3: Insert 3

   3 <= 5 but > 1, push 3 to high; high_size=2, low_size=1; balance heaps by moving smallest from high (3) to low (-3); low_size=2, high_size=1.

4. Step 4: Find median

   low_size > high_size, median is -low[0] = 3.0.

5. Step 5: Re-examine median calculation

   After balancing, low heap has [-3, -1], high heap has [5]. Median is top of low heap = 3.0, but the question asks for median after adding 1,5,3 in order, so median is 3.0.

6. Final Answer:

   Option B -> Option B

7. Quick Check:

   Median after [1,5,3] is 3.0 [OK]

Hint: Median is top of larger heap after balancing [OK]

Common Mistakes:

• Forgetting to balance heaps after insertion
• Returning wrong heap top for median

2. The following code attempts to copy a linked list with random pointers using the optimal weaving approach. Identify the line that contains a subtle bug that can cause incorrect random pointer assignment or list corruption.

def copyRandomList(head):
    if not head:
        return None
    curr = head
    # Step 1: Insert copied nodes
    while curr:
        new_node = Node(curr.val, curr.next)
        curr.next = new_node
        curr = new_node.next
    # Step 2: Assign random pointers
    curr = head
    while curr:
        if curr.random:
            curr.next.random = curr.random  # Bug here
        curr = curr.next.next
    # Step 3: Separate lists
    curr = head
    copy_head = head.next
    copy_curr = copy_head
    while curr:
        curr.next = curr.next.next
        if copy_curr.next:
            copy_curr.next = copy_curr.next.next
        curr = curr.next
        copy_curr = copy_curr.next
    return copy_head

medium

A. Line assigning curr.next.random = curr.random

B. Line inserting copied nodes: curr.next = new_node

C. Line advancing curr in Step 1: curr = new_node.next

D. Line separating original and copied lists: curr.next = curr.next.next

Solution

1. Step 1: Analyze random pointer assignment

   The line assigns curr.next.random = curr.random, but curr.random points to original nodes, not copied nodes.

2. Step 2: Correct assignment

   It should be curr.next.random = curr.random.next to point to the copied node corresponding to curr.random.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Incorrect random pointer assignment breaks copied list correctness [OK]

Hint: Random pointer must point to copied node, not original [OK]

Common Mistakes:

• Assigning random pointer directly to original node
• Mixing original and copied nodes after weaving
• Forgetting to advance curr by two nodes

3. What is the time complexity of the get and put operations in an optimal LRU Cache implementation using a hash map and a doubly linked list with capacity n?

medium

A. O(n) for get and put due to list traversal

B. O(1) amortized for get and put using hash map and doubly linked list

C. O(log n) due to balancing the linked list

D. O(1) for get but O(n) for put due to eviction

Solution

1. Step 1: Analyze get operation

   Hash map provides O(1) access to node; doubly linked list allows O(1) removal and insertion to update usage order.

2. Step 2: Analyze put operation

   Insertion involves hash map update and linked list insertion/removal, all O(1). Eviction removes tail node in O(1).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Both get and put run in constant time using combined data structures [OK]

Hint: Hash map + doubly linked list -> O(1) get and put [OK]

Common Mistakes:

• Assuming list removal is O(n)
• Confusing amortized with worst-case
• Thinking linked list needs balancing

4. Suppose the AllOne data structure is extended to allow keys to be reused after removal (i.e., keys can be reinserted after their count reaches zero). Which modification is necessary to maintain O(1) operations and correctness?

hard

A. Do nothing special; existing code handles reuse correctly

B. Maintain a separate reuse queue to track keys that can be reinserted

C. Reset key's count to zero and keep it in the data structure to track reuse

D. Ensure keys are fully removed from all buckets and mappings upon count zero, then treat reuse as new insertion

Solution

1. Step 1: Understand reuse implications

   Keys removed at count zero must be fully deleted to avoid stale references.

2. Step 2: Ensure reuse is treated as new insertion

   On reuse, key is inserted fresh with count 1, requiring clean removal previously.

3. Step 3: Confirm O(1) operations

   Full removal and fresh insertion maintain O(1) updates and correctness.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Proper removal prevents duplicates and stale buckets [OK]

Hint: Full removal before reuse ensures correctness and O(1) ops [OK]

Common Mistakes:

• Keeping keys with zero count in data structure causes bugs

5. Suppose you want to modify the skiplist to support duplicate values and allow searching for the k-th occurrence of a target. Which modification is the most appropriate to maintain efficient search and insertion?

hard

A. Insert duplicate nodes at the lowest level only, ignoring higher levels

B. Store a count of duplicates in each node and update counts on insert/erase

C. Use a hash map to track occurrences separately from the skiplist

D. Disallow duplicates and reject insertions of existing values

Solution

1. Step 1: Understand duplicate handling

   To support duplicates and k-th occurrence search, nodes must track counts or occurrences.

2. Step 2: Evaluate options

   Storing counts in nodes and updating them maintains skiplist structure and efficient operations.

3. Step 3: Reject other options

   Inserting duplicates only at lowest level breaks skiplist invariants; hash map adds overhead; disallowing duplicates contradicts requirement.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Counting duplicates in nodes preserves skiplist efficiency and supports k-th occurrence [OK]

Hint: Count duplicates in nodes to handle multiple occurrences efficiently [OK]

Common Mistakes:

• Ignoring duplicates in higher levels
• Using external structures breaking skiplist properties
• Disallowing duplicates despite requirement