[Hard] 715. Range Module

A Range Module is a module that tracks ranges of numbers. Design a data structure to track the ranges represented as half-open intervals [left, 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.
bool 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).

Examples

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);  // Track [10, 20)
rangeModule.removeRange(14, 16); // Stop tracking [14, 16)
rangeModule.queryRange(10, 14); // Returns true (every number in [10, 14) is being tracked)
rangeModule.queryRange(13, 15); // Returns false (numbers like 13.5, 14, 14.5, 15 in [13, 15) are not being tracked)
rangeModule.queryRange(16, 17); // Returns true (the number 16 in [16, 17) is still being tracked, despite the removeRange operation)

Constraints

1 <= left < right <= 10^9
At most 10^4 calls will be made to addRange, queryRange, and removeRange.

Solution Structure Breakdown

Evolution from Naive to Optimized

Naive Approach (List-based):

Structure: Store intervals in unsorted list, linear scan
Complexity: O(n) per operation, O(n^2) worst case
Limitation: No efficient way to find/merge intervals

Semi-Optimized Approach (Sorted Vector):

Structure: Maintain sorted vector, binary search for position
Complexity: O(log n) search + O(n) insertion/deletion
Improvement: Faster search, but still O(n) for modifications

Optimized Approach (Sorted Map):

Structure: std::map for automatic sorting and O(log n) operations
Complexity: O(k log n) where k = intervals affected
Enhancement: Efficient merge/split operations

Code Structure Comparison

Approach	Data Structure	Search	Insert/Delete	Merge Logic
Naive	Unsorted list	O(n)	O(1)	O(n^2)
Semi-Opt	Sorted vector	O(log n)	O(n)	O(n)
Optimized	Sorted map	O(log n)	O(log n)	O(k log n)

Thinking Process

A Range Module is a module that tracks ranges of numbers. Design a data structure to track the ranges represented as half-open intervals [left, right).

Implement the RangeModule class:

Identify required operations and their frequency (get/put/insert).
Combine data structures: hash map + list, heap + map, trie + DFS.
Amortized O(1) often needs lazy cleanup or doubly-linked lists.

Common Approaches

Typical techniques for this pattern:

Approach	Time	Space	Notes
Hash map + list (this problem)	O(1) avg	O(n)	LRU cache pattern
Heap + hash map	O(log n)	O(n)	LFU, time-based store
Trie (prefix tree)	O(m)	O(nm)	Word search, autocomplete
Deque / circular buffer	O(1)	O(n)	Queue with fixed capacity

Solution

Solution 1: Brute-Force List-Based Approach

Time Complexity: O(n) per operation, O(n^2) worst case for merging
Space Complexity: O(n)

Store all intervals in an unsorted list and linearly scan for operations.

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

    def mergeIntervals(self):
        if not self.intervals:
            return

        self.intervals.sort()
        merged = [self.intervals[0]]

        for i in range(1, len(self.intervals)):
            l, r = self.intervals[i]
            last_l, last_r = merged[-1]

            if merged[-1][1] >= l:
                merged[-1] = (last_l, max(last_r, r))
            else:
                merged.append((l, r))

        self.intervals = merged

    def addRange(self, left, right):
        self.intervals.append((left, right))
        self.mergeIntervals()

    def queryRange(self, left, right):
        for l, r in self.intervals:
            if l <= left and right <= r:
                return True
        return False

    def removeRange(self, left, right):
        newIntervals = []

        for l, r in self.intervals:
            if r <= left or l >= right:
                newIntervals.append((l, r))
            else:
                if l < left:
                    newIntervals.append((l, left))
                if r > right:
                    newIntervals.append((right, r))

        self.intervals = newIntervals

Note: This approach is inefficient due to O(n) operations and O(n^2) worst case merging.

Solution 2: Sorted Vector with Binary Search

Time Complexity: O(log n) search + O(n) insertion/deletion per operation
Space Complexity: O(n)

Maintain sorted intervals using a vector with binary search for finding positions.

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

    def findInsertPos(self, left):
        low, high = 0, len(self.intervals)

        while low < high:
            mid = (low + high) // 2

            if self.intervals[mid][0] <= left:
                low = mid + 1
            else:
                high = mid

        return low

    def addRange(self, left, right):
        pos = self.findInsertPos(left)
        self.intervals.insert(pos, (left, right))
        self.mergeIntervals()

    def queryRange(self, left, right):
        pos = self.findInsertPos(left)

        if pos > 0:
            l, r = self.intervals[pos - 1]
            if l <= left and right <= r:
                return True

        return False

    def removeRange(self, left, right):
        newIntervals = []

        for l, r in self.intervals:
            if r <= left or l >= right:
                newIntervals.append((l, r))
            else:
                if l < left:
                    newIntervals.append((l, left))
                if r > right:
                    newIntervals.append((right, r))

        self.intervals = newIntervals

    def mergeIntervals(self):
        if not self.intervals:
            return

        self.intervals.sort()
        merged = [self.intervals[0]]

        for i in range(1, len(self.intervals)):
            l, r = self.intervals[i]
            last_l, last_r = merged[-1]

            if last_r >= l:
                merged[-1] = (last_l, max(last_r, r))
            else:
                merged.append((l, r))

        self.intervals = merged

Note: Better than brute-force with O(log n) search, but still O(n) for insertions/deletions.

Solution 3: Map-Based Interval Management (Recommended)

import bisect

class RangeModule:
    def __init__(self):
        # store disjoint intervals [l, r)
        self.intervals = []

    def _find_left(self, x):
        # first interval with start > x
        return bisect.bisect_left(self.intervals, (x,))

    def addRange(self, left, right):
        i = bisect.bisect_left(self.intervals, (left, 0))
        new_left, new_right = left, right

        # merge overlapping on the left side
        if i > 0 and self.intervals[i - 1][1] >= left:
            i -= 1
            new_left = min(new_left, self.intervals[i][0])
            new_right = max(new_right, self.intervals[i][1])
            self.intervals.pop(i)

        # merge overlapping intervals to the right
        while i < len(self.intervals) and self.intervals[i][0] <= right:
            new_right = max(new_right, self.intervals[i][1])
            self.intervals.pop(i)

        self.intervals.insert(i, (new_left, new_right))

    def queryRange(self, left, right):
        i = bisect.bisect_right(self.intervals, (left, float('inf')))

        if i == 0:
            return False

        l, r = self.intervals[i - 1]
        return l <= left and right <= r

    def removeRange(self, left, right):
        res = []
        for l, r in self.intervals:
            # no overlap
            if r <= left or l >= right:
                res.append((l, r))
            else:
                # left split
                if l < left:
                    res.append((l, left))
                # right split
                if r > right:
                    res.append((right, r))

        self.intervals = res

Algorithm Explanation:

1. addRange (Lines 10-24)

Purpose: Add interval [left, right), merging with overlapping intervals.

Steps:

Find insertion point (Line 11): upper_bound(left) finds first interval starting after left
Check previous interval (Lines 12-19):
- If previous interval ends at or after right: already covered, return
- If previous interval ends at or after left: merge by extending left to previous start
Merge overlapping intervals (Lines 20-23):
- While current interval starts before or at right: merge by extending right
- Remove merged intervals
Insert merged interval (Line 24): Add final merged interval

Example:

Initial: intervals = {[10, 20]}
addRange(15, 25):
  it = upper_bound(15) → points to [10, 20]
  prev(it) = [10, 20]
  start->second (20) >= left (15) → merge
  left = 10
  it->first (10) <= right (25) → merge
  right = max(25, 20) = 25
  Result: {[10, 25]}

2. queryRange (Lines 26-31)

Purpose: Check if entire range [left, right) is tracked.

Steps:

Find candidate interval (Line 27): upper_bound(left) finds first interval after left
Check previous interval (Line 28): Move to previous interval (might contain left)
Verify coverage (Line 30): Check if previous interval completely covers [left, right)

Example:

intervals = {[10, 20]}
queryRange(12, 18):
  it = upper_bound(12) → points to [10, 20]
  prev(it) = [10, 20]
  Check: right (18) <= it->second (20) → true

3. removeRange (Lines 33-56)

Purpose: Remove interval [left, right) from tracked ranges.

Steps:

Find starting point (Line 34): upper_bound(left) finds first interval after left
Handle previous interval (Lines 35-50):
- If previous interval completely contains [left, right):
  - Split into [start, left) and [right, end) if needed
- If previous interval partially overlaps:
  - Truncate to [start, left)
Remove/truncate following intervals (Lines 51-56):
- Remove intervals completely within [left, right)
- Truncate interval that extends beyond right

Example:

intervals = {[10, 20]}
removeRange(14, 16):
  it = upper_bound(14) → points to [10, 20]
  prev(it) = [10, 20]
  start->second (20) >= right (16) → split needed
  start->first (10) != left (14) → truncate to [10, 14)
  right (16) != ri (20) → add [16, 20)
  Result: {[10, 14), [16, 20)}

Detailed Example Walkthrough:

Operations:

1. addRange(10, 20)
   intervals = {[10, 20)}

2. addRange(15, 25)
   - Check [10, 20): overlaps, merge
   intervals = {[10, 25)}

3. removeRange(14, 16)
   - [10, 25) overlaps with [14, 16)
   - Split: [10, 14) and [16, 25)
   intervals = {[10, 14), [16, 25)}

4. queryRange(10, 14)
   - Find interval containing 10: [10, 14)
   - Check: 14 <= 14? Yes → true

5. queryRange(13, 15)
   - Find interval containing 13: [10, 14)
   - Check: 15 <= 14? No → false

6. queryRange(16, 17)
   - Find interval containing 16: [16, 25)
   - Check: 17 <= 25? Yes → true

Algorithm Breakdown

Key Insight: Sorted Map for Intervals

Using map<int, int> provides:

Sorted keys: Intervals stored by start point
O(log n) operations: Insert, delete, search
Efficient merging: Easy to find overlapping intervals

Interval Merging Logic

addRange merges intervals by:

Finding intervals that overlap or are adjacent
Extending left to earliest start
Extending right to latest end
Removing all subsumed intervals

Interval Splitting Logic

removeRange splits intervals by:

Truncating intervals that start before left
Removing intervals completely within [left, right)
Creating new interval for part extending beyond right

Complexity

Time Complexity:

addRange: O(k log n) where k = number of intervals to merge
queryRange: O(log n) - binary search in map
removeRange: O(k log n) where k = number of intervals to remove/split
n = number of intervals stored

Space Complexity: O(n)

Map storage: O(n) intervals stored
Each operation: O(1) extra space

Key Points

Half-Open Intervals: [left, right) means left included, right excluded
Sorted Map: Maintains intervals in sorted order for efficient operations
Merging: Automatically merges overlapping/adjacent intervals
Splitting: Handles partial overlaps by splitting intervals
Efficient Queries: O(log n) lookup using binary search

Edge Cases

Empty intervals: left >= right should be handled (though constraints say left < right)
No overlapping: Adding non-overlapping interval creates new entry
Complete overlap: Adding interval already covered does nothing
Remove entire interval: Removing completely removes interval
Query outside range: Returns false if no interval covers query

Common Mistakes

Skipping edge cases (empty input, single element, boundaries).
Off-by-one errors in loops and index ranges.
Forgetting to handle the case when no valid answer exists.

715. Range Module - Current problem
56. Merge Intervals - Merge overlapping intervals
57. Insert Interval - Insert and merge
352. Data Stream as Disjoint Intervals - Similar interval management

Key Takeaways

Identify required operations and their frequency (get/put/insert).
Combine data structures: hash map + list, heap + map, trie + DFS.
Amortized O(1) often needs lazy cleanup or doubly-linked lists.

References

LC 715: Range Module on LeetCode
LeetCode Discuss — LC 715: Range Module
LeetCode Editorial (may require premium)

Template Reference

Data Structure Design

Robina Li

[Hard] 715. Range Module

Examples

Constraints

Solution Structure Breakdown

Evolution from Naive to Optimized

Code Structure Comparison

Thinking Process

Common Approaches

Solution

Solution 1: Brute-Force List-Based Approach

Solution 2: Sorted Vector with Binary Search

Solution 3: Map-Based Interval Management (Recommended)

Algorithm Explanation:

1. addRange (Lines 10-24)

2. queryRange (Lines 26-31)

3. removeRange (Lines 33-56)

Detailed Example Walkthrough:

Algorithm Breakdown

Key Insight: Sorted Map for Intervals

Interval Merging Logic

Interval Splitting Logic

Complexity

Time Complexity:

Space Complexity: O(n)

Key Points

Edge Cases

Common Mistakes

Tags

Key Takeaways

References

Template Reference

Related Posts

Recent Posts

Examples

Constraints

Solution Structure Breakdown

Evolution from Naive to Optimized

Code Structure Comparison

Thinking Process

Common Approaches

Solution

Solution 1: Brute-Force List-Based Approach

Solution 2: Sorted Vector with Binary Search

Solution 3: Map-Based Interval Management (Recommended)

Algorithm Explanation:

1. addRange (Lines 10-24)

2. queryRange (Lines 26-31)

3. removeRange (Lines 33-56)

Detailed Example Walkthrough:

Algorithm Breakdown

Key Insight: Sorted Map for Intervals

Interval Merging Logic

Interval Splitting Logic

Complexity

Time Complexity:

Space Complexity: O(n)

Key Points

Edge Cases

Common Mistakes

Related Problems

Tags

Key Takeaways

References

Template Reference

Related Posts

Recent Posts