Range Module

Hard

#0669Time: `addRange`: O(N) `removeRange`: O(N) `queryRange`: O(log N) Where N is the number of disjoint intervals. `addRange` and `removeRange` must scan the entire list.Space: O(N), where N is the number of disjoint intervals. In the worst case, N can be up to the number of calls.2 companies

Patterns

Design

Data structures

Segment Tree Ordered Set

Companies

Coupang Machine Zone

Prompt

A Range Module is a module that tracks ranges of numbers. Design a data structure to track the ranges represented as half-open intervals and query about them.

A half-open interval [left, right) denotes all the real numbers x where left <= x < right.

Implement the RangeModule class:

RangeModule() Initializes the object of the data structure.
void addRange(int left, int right) Adds the half-open interval [left, right), tracking every real number in that interval. Adding an interval that partially overlaps with currently tracked numbers should add any numbers in the interval [left, right) that are not already tracked.
boolean queryRange(int left, int right) Returns true if every real number in the interval [left, right) is currently being tracked, and false otherwise.
void removeRange(int left, int right) Stops tracking every real number currently being tracked in the half-open interval [left, right).

Example 1:

Input
["RangeModule", "addRange", "removeRange", "queryRange", "queryRange", "queryRange"]
[[], [10, 20], [14, 16], [10, 14], [13, 15], [16, 17]]
Output
[null, null, null, true, false, true]

Explanation
RangeModule rangeModule = new RangeModule();
rangeModule.addRange(10, 20);
rangeModule.removeRange(14, 16);
rangeModule.queryRange(10, 14); // return True,(Every number in [10, 14) is being tracked)
rangeModule.queryRange(13, 15); // return False,(Numbers like 14, 14.03, 14.17 in [13, 15) are not being tracked)
rangeModule.queryRange(16, 17); // return True, (The number 16 in [16, 17) is still being tracked, despite the remove operation)

Constraints:

1 <= left < right <= 10⁹
At most 10⁴ calls will be made to addRange, queryRange, and removeRange.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach maintains a sorted list of disjoint intervals. Operations like adding or removing a range require iterating through the list to find affected intervals, merging or splitting them, and then creating a new list with the updated intervals. While modifications are slow, querying can be made efficient using binary search.

Algorithm

Data Structure: Use a java.util.ArrayList<int[]> to store the intervals, kept sorted by their start times.
addRange(left, right):
1. Initialize an empty newIntervals list.
2. Iterate through the current intervals list.
3. For each existing interval, check for overlap with the new interval [left, right).
4. If there is no overlap and the existing interval is before the new one, add it to newIntervals.
5. If there is no overlap and the existing interval is after the new one, first add the (potentially merged) new interval [left, right) if it hasn't been added yet, then add the existing interval.
6. If there is an overlap, merge the existing interval into the new one by updating left = Math.min(left, interval[0]) and right = Math.max(right, interval[1]). Do not add anything to newIntervals yet.
7. After iterating through all intervals, add the final merged [left, right) interval to newIntervals.
8. Replace the original intervals list with newIntervals.
removeRange(left, right):
1. Initialize an empty newIntervals list.
2. Iterate through the current intervals list.
3. For each existing interval, check for overlap with the removal interval [left, right).
4. If there is no overlap, add the existing interval to newIntervals.
5. If there is an overlap, calculate the parts of the interval that remain. If interval[0] < left, add [interval[0], left) to newIntervals. If interval[1] > right, add [right, interval[1]) to newIntervals.
6. Replace the original intervals list with newIntervals.
queryRange(left, right):
1. Since the list is sorted, perform a binary search to find the interval with the largest start time that is less than or equal to left.
2. If such an interval [start, end] is found, check if its end end is greater than or equal to right.
3. Return true if the condition is met, otherwise false.

Walkthrough

We use a java.util.ArrayList<int[]> to store the intervals, kept sorted by their start times.

addRange(left, right): We build a new list by iterating through the old one. We copy over intervals that come before the new range. Then, we merge the new range [left, right) with all overlapping intervals from the old list into a single new interval. Finally, we add this merged interval and any remaining intervals from the old list to our new list. The old list is then replaced by the new one. This process takes linear time with respect to the number of intervals.

removeRange(left, right): Similar to addRange, we create a new list. We iterate through the old list. For each interval, if it doesn't overlap with [left, right), we add it to the new list. If it does overlap, we calculate the parts of the interval that remain after the removal and add them as new, smaller intervals to the new list. This also takes linear time.

queryRange(left, right): Since the list is sorted by the start time, we can use binary search to efficiently find an interval that could potentially cover the query range [left, right). We search for the interval with the largest start time that is less than or equal to left. If such an interval exists and its end time is greater than or equal to right, the query is satisfied. This is a logarithmic time operation.

1class RangeModule {2    List<int[]> intervals;3 4    public RangeModule() {5        intervals = new ArrayList<>();6    }7 8    public void addRange(int left, int right) {9        List<int[]> newIntervals = new ArrayList<>();10        boolean inserted = false;11        for (int[] interval : intervals) {12            if (interval[1] < left) {13                newIntervals.add(interval);14            } else if (interval[0] > right) {15                if (!inserted) {16                    newIntervals.add(new int[]{left, right});17                    inserted = true;18                }19                newIntervals.add(interval);20            } else {21                left = Math.min(left, interval[0]);22                right = Math.max(right, interval[1]);23            }24        }25        if (!inserted) {26            newIntervals.add(new int[]{left, right});27        }28        intervals = newIntervals;29    }30 31    public boolean queryRange(int left, int right) {32        int low = 0, high = intervals.size() - 1;33        int idx = -1;34        // Binary search to find an interval that might contain [left, right)35        while(low <= high){36            int mid = low + (high - low) / 2;37            if(intervals.get(mid)[0] <= left){38                idx = mid;39                low = mid + 1;40            } else {41                high = mid - 1;42            }43        }44        45        return idx != -1 && intervals.get(idx)[1] >= right;46    }47 48    public void removeRange(int left, int right) {49        List<int[]> newIntervals = new ArrayList<>();50        for (int[] interval : intervals) {51            // No overlap52            if (interval[1] <= left || interval[0] >= right) {53                newIntervals.add(interval);54            } else {55                // Overlap56                if (interval[0] < left) {57                    newIntervals.add(new int[]{interval[0], left});58                }59                if (interval[1] > right) {60                    newIntervals.add(new int[]{right, interval[1]});61                }62            }63        }64        intervals = newIntervals;65    }66}

Complexity

Time

`addRange`: O(N) `removeRange`: O(N) `queryRange`: O(log N) Where N is the number of disjoint intervals. `addRange` and `removeRange` must scan the entire list.

Space

O(N), where N is the number of disjoint intervals. In the worst case, N can be up to the number of calls.

Trade-offs

Pros

Relatively simple to understand and implement.
The queryRange operation is efficient (O(log N)) due to binary search.

Cons

The addRange and removeRange operations are inefficient, requiring a full scan and recreation of the list, leading to O(N) time complexity.
Rebuilding the list in modification operations can lead to higher memory usage and garbage collection overhead.

This approach uses a TreeMap to store the disjoint intervals, mapping the start of each interval to its end. The TreeMap automatically keeps the intervals sorted by their start times and provides efficient methods (floorEntry, subMap, etc.) to find and manipulate intervals, leading to better performance than a simple list.

Algorithm

Data Structure: Use a java.util.TreeMap<Integer, Integer> where keys are interval start points and values are interval end points.
addRange(left, right):
1. Find any existing intervals that overlap or are adjacent to [left, right). This can be done by checking intervals whose start is near left or right.
2. Merge [left, right) with all such overlapping/adjacent intervals by taking the minimum of all start points and the maximum of all end points.
3. Remove all the old intervals that were merged.
4. Insert the new, combined interval into the TreeMap.
5. This can be implemented cleanly by finding the new boundaries [newLeft, newRight], removing all intervals within that range using map.subMap(newLeft, newRight).clear(), and then inserting the new interval map.put(newLeft, newRight).
removeRange(left, right):
1. Find an interval [l, r) that is partially overlapped by the start of the removal range (i.e., l < left < r). If found, trim it by updating its end to left (map.put(l, left)).
2. Find an interval [l, r) that is partially overlapped by the end of the removal range (i.e., l < right < r). If found, this may create a new interval [right, r). The original interval might have already been trimmed in step 1.
3. A key insight is that a removal can split one interval into two. For an interval [l, r) that contains [left, right), it becomes [l, left) and [right, r).
4. Remove all intervals that are fully contained within [left, right) using map.subMap(left, true, right, false).clear().
queryRange(left, right):
1. Use map.floorEntry(left) to find the interval [l, r) with the largest start l such that l <= left.
2. If such an entry exists, check if its value r is greater than or equal to right.
3. Return true if entry != null && entry.getValue() >= right, otherwise false.

Walkthrough

We use a java.util.TreeMap<Integer, Integer> where the key is the interval's start and the value is its end. This structure is a balanced binary search tree, ensuring logarithmic time complexity for basic operations.

addRange(left, right): We leverage TreeMap methods to find all existing intervals that overlap with or are adjacent to [left, right). These intervals are then merged into a single large interval by taking the minimum of all start points and the maximum of all end points. We then remove all the old, now-merged intervals and insert the new, single, larger interval. TreeMap's subMap view is very effective for removing a range of intervals at once.

removeRange(left, right): This operation can be complex as it might split an existing interval. We handle this by first identifying any intervals that are partially overlapped by [left, right) at the boundaries. For an interval [l, r) that is partially overlapped, we trim it by adjusting its start or end, and if it's split in two, we add a new interval for the second part. For example, removing [14, 16) from [10, 20) results in [10, 14) and [16, 20). After handling the boundaries, we remove all intervals that are fully contained within [left, right).

queryRange(left, right): This is the most efficient operation. We just need to find if there's a single tracked interval [l, r) that completely contains [left, right). We use map.floorEntry(left) to find the interval that starts at or before left. If this interval exists and its end is at or after right, the range is covered. This is a single O(log N) lookup.

1class RangeModule {2    TreeMap<Integer, Integer> map;3 4    public RangeModule() {5        map = new TreeMap<>();6    }7 8    public void addRange(int left, int right) {9        Map.Entry<Integer, Integer> start = map.floorEntry(left);10        if (start != null && start.getValue() >= left) {11            left = start.getKey();12        }13        Map.Entry<Integer, Integer> end = map.floorEntry(right);14        if (end != null && end.getValue() > right) {15            right = end.getValue();16        }17        map.subMap(left, true, right, false).clear();18        map.put(left, right);19    }20 21    public boolean queryRange(int left, int right) {22        Map.Entry<Integer, Integer> entry = map.floorEntry(left);23        return entry != null && entry.getValue() >= right;24    }25 26    public void removeRange(int left, int right) {27        Map.Entry<Integer, Integer> start = map.floorEntry(left);28        if (start != null && start.getValue() > left) {29            map.put(start.getKey(), left);30        }31        Map.Entry<Integer, Integer> end = map.floorEntry(right);32        if (end != null && end.getValue() > right) {33            map.put(right, end.getValue());34        }35        map.subMap(left, true, right, false).clear();36    }37}

Complexity

Time

`addRange`: O(k log N) `removeRange`: O(k log N) `queryRange`: O(log N) Where N is the number of disjoint intervals and k is the number of intervals affected by the operation. This is significantly faster than the list-based approach for modifications.

Space

O(N), where N is the number of disjoint intervals.

Trade-offs

Pros

Highly efficient operations. queryRange is O(log N), and addRange/removeRange are also efficient with O(k log N) complexity, where k is small on average.
Scales well with a large number of intervals.
The use of TreeMap methods can lead to concise and elegant code for complex interval manipulations.

Cons

The implementation logic, especially for addRange and removeRange, is more complex than the list-based approach and requires careful handling of edge cases to ensure correctness.

Solutions

Solution

1class Node { Node left ; Node right ; int add ; boolean v ; } class SegmentTree { private Node root = new Node (); public SegmentTree () { } public void modify ( int left , int right , int v ) { modify ( left , right , v , 1 , ( int ) 1 e9 , root ); } public void modify ( int left , int right , int v , int l , int r , Node node ) { if ( l >= left && r <= right ) { node . v = v == 1 ; node . add = v ; return ; } pushdown ( node ); int mid = ( l + r ) >> 1 ; if ( left <= mid ) { modify ( left , right , v , l , mid , node . left ); } if ( right > mid ) { modify ( left , right , v , mid + 1 , r , node . right ); } pushup ( node ); } public boolean query ( int left , int right ) { return query ( left , right , 1 , ( int ) 1 e9 , root ); } public boolean query ( int left , int right , int l , int r , Node node ) { if ( l >= left && r <= right ) { return node . v ; } pushdown ( node ); int mid = ( l + r ) >> 1 ; boolean v = true ; if ( left <= mid ) { v = v && query ( left , right , l , mid , node . left ); } if ( right > mid ) { v = v && query ( left , right , mid + 1 , r , node . right ); } return v ; } public void pushup ( Node node ) { node . v = node . left != null && node . left . v && node . right != null && node . right . v ; } public void pushdown ( Node node ) { if ( node . left == null ) { node . left = new Node (); } if ( node . right == null ) { node . right = new Node (); } if ( node . add != 0 ) { node . left . add = node . add ; node . right . add = node . add ; node . left . v = node . add == 1 ; node . right . v = node . add == 1 ; node . add = 0 ; } } } class RangeModule { private SegmentTree tree = new SegmentTree (); public RangeModule () { } public void addRange ( int left , int right ) { tree . modify ( left , right - 1 , 1 ); } public boolean queryRange ( int left , int right ) { return tree . query ( left , right - 1 ); } public void removeRange ( int left , int right ) { tree . modify ( left , right - 1 , - 1 ); } } /** * Your RangeModule object will be instantiated and called as such: * RangeModule obj = new RangeModule(); * obj.addRange(left,right); * boolean param_2 = obj.queryRange(left,right); * obj.removeRange(left,right); */

1template < class T > class CachedObj { public: void * operator new ( size_t s ) { if ( ! head ) { T * a = new T [ SIZE ]; for ( size_t i = 0 ; i < SIZE ; ++ i ) add ( a + i ); } T * p = head ; head = head -> CachedObj < T >:: next ; return p ; } void operator delete ( void * p , size_t ) { if ( p ) add ( static_cast < T *> ( p )); } virtual ~ CachedObj () {} protected: T * next ; private: static T * head ; static const size_t SIZE ; static void add ( T * p ) { p -> CachedObj < T >:: next = head ; head = p ; } }; template < class T > T * CachedObj < T >:: head = 0 ; template < class T > const size_t CachedObj < T >:: SIZE = 10000 ; class Node : public CachedObj < Node > { public: Node * left ; Node * right ; int add ; bool v ; }; class SegmentTree { private: Node * root ; public: SegmentTree () { root = new Node (); } void modify ( int left , int right , int v ) { modify ( left , right , v , 1 , 1e9 , root ); } void modify ( int left , int right , int v , int l , int r , Node * node ) { if ( l >= left && r <= right ) { node -> v = v == 1 ; node -> add = v ; return ; } pushdown ( node ); int mid = ( l + r ) >> 1 ; if ( left <= mid ) modify ( left , right , v , l , mid , node -> left ); if ( right > mid ) modify ( left , right , v , mid + 1 , r , node -> right ); pushup ( node ); } bool query ( int left , int right ) { return query ( left , right , 1 , 1e9 , root ); } bool query ( int left , int right , int l , int r , Node * node ) { if ( l >= left && r <= right ) return node -> v ; pushdown ( node ); int mid = ( l + r ) >> 1 ; bool v = true ; if ( left <= mid ) v = v && query ( left , right , l , mid , node -> left ); if ( right > mid ) v = v && query ( left , right , mid + 1 , r , node -> right ); return v ; } void pushup ( Node * node ) { node -> v = node -> left && node -> left -> v && node -> right && node -> right -> v ; } void pushdown ( Node * node ) { if ( ! node -> left ) node -> left = new Node (); if ( ! node -> right ) node -> right = new Node (); if ( node -> add ) { node -> left -> add = node -> right -> add = node -> add ; node -> left -> v = node -> right -> v = node -> add == 1 ; node -> add = 0 ; } } }; class RangeModule { public: SegmentTree * tree ; RangeModule () { tree = new SegmentTree (); } void addRange ( int left , int right ) { tree -> modify ( left , right - 1 , 1 ); } bool queryRange ( int left , int right ) { return tree -> query ( left , right - 1 ); } void removeRange ( int left , int right ) { tree -> modify ( left , right - 1 , - 1 ); } }; /** * Your RangeModule object will be instantiated and called as such: * RangeModule* obj = new RangeModule(); * obj->addRange(left,right); * bool param_2 = obj->queryRange(left,right); * obj->removeRange(left,right); */

1class Node : __slots__ = [ 'left' , 'right' , 'add' , 'v' ] def __init__ ( self ): self . left = None self . right = None self . add = 0 self . v = False class SegmentTree : __slots__ = [ 'root' ] def __init__ ( self ): self . root = Node () def modify ( self , left , right , v , l = 1 , r = int ( 1e9 ), node = None ): if node is None : node = self . root if l >= left and r <= right : if v == 1 : node . add = 1 node . v = True else : node . add = - 1 node . v = False return self . pushdown ( node ) mid = ( l + r ) >> 1 if left <= mid : self . modify ( left , right , v , l , mid , node . left ) if right > mid : self . modify ( left , right , v , mid + 1 , r , node . right ) self . pushup ( node ) def query ( self , left , right , l = 1 , r = int ( 1e9 ), node = None ): if node is None : node = self . root if l >= left and r <= right : return node . v self . pushdown ( node ) mid = ( l + r ) >> 1 v = True if left <= mid : v = v and self . query ( left , right , l , mid , node . left ) if right > mid : v = v and self . query ( left , right , mid + 1 , r , node . right ) return v def pushup ( self , node ): node . v = bool ( node . left and node . left . v and node . right and node . right . v ) def pushdown ( self , node ): if node . left is None : node . left = Node () if node . right is None : node . right = Node () if node . add : node . left . add = node . right . add = node . add node . left . v = node . add == 1 node . right . v = node . add == 1 node . add = 0 class RangeModule : def __init__ ( self ): self . tree = SegmentTree () def addRange ( self , left : int , right : int ) -> None : self . tree . modify ( left , right - 1 , 1 ) def queryRange ( self , left : int , right : int ) -> bool : return self . tree . query ( left , right - 1 ) def removeRange ( self , left : int , right : int ) -> None : self . tree . modify ( left , right - 1 , - 1 ) # Your RangeModule object will be instantiated and called as such: # obj = RangeModule() # obj.addRange(left,right) # param_2 = obj.queryRange(left,right) # obj.removeRange(left,right)

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem