715. Range Module Solution & Explanation

Q: Is Range Module easy or hard?

Range Module is classified as a Hard problem because it combines data structure design with interval merging logic. Implementing add, remove, and query operations correctly while maintaining non-overlapping intervals requires careful edge-case handling.

Q: Range Module Python or Java solution?

Python implementations often maintain a sorted list of intervals and merge overlaps during updates. Java solutions commonly use TreeMap because it provides efficient predecessor and successor lookups, making interval merging and splitting straightforward.

Q: How to solve Range Module in O(log n)?

Store intervals in a balanced ordered map keyed by their starting position. Use floor or ceiling operations to locate the nearest interval that might overlap with the target range. Merge overlapping intervals during addRange and split intervals during removeRange, keeping the structure sorted.

Q: What is the best approach for Range Module?

The balanced tree map approach is generally the best solution. Intervals are stored in a sorted structure such as Java's TreeMap, allowing logarithmic searches for overlapping ranges. Each update merges or splits only the affected intervals, giving O(log n + k) time where k is the number of overlaps.

Q: Is Range Module asked at Google/Amazon/Meta?

Range management and interval design problems frequently appear in interviews at companies like Google, Amazon, and Meta. The problem tests system-style thinking: designing a data structure with efficient updates and queries while handling overlapping intervals.

Q: What data structure is used in Range Module?

Common solutions use an ordered map or balanced binary search tree to store intervals. Alternatives include segment trees with lazy propagation for very large ranges, though interview solutions usually prefer ordered sets or TreeMap-based interval merging.

Q: What is the time complexity of Range Module?

Using a balanced tree map, addRange and removeRange run in O(log n + k) time due to tree lookups and interval merging. queryRange typically runs in O(log n) because it only needs to check the closest interval before the queried start. Space complexity is O(n) for storing intervals.

The problem

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.

Approach overview

Problem Overview: Design a data structure that tracks numeric ranges. You must support three operations: addRange(left, right), removeRange(left, right), and queryRange(left, right). The challenge is efficiently merging, splitting, and checking overlapping intervals while the structure changes dynamically.

Approach 1: Sorted List of Intervals (O(n) time, O(n) space)

Maintain a sorted list of non-overlapping intervals. Each time you call addRange, iterate through the list, merge overlapping intervals, and insert the new merged interval in the correct position. For removeRange, scan the list and split any interval that partially overlaps with the removal range. queryRange simply checks whether a single interval fully covers the requested range. Because updates may require scanning and rebuilding parts of the list, operations take O(n) time in the worst case while storing up to O(n) intervals.

This approach is straightforward and works well when the number of stored intervals is small. It focuses on interval merging logic rather than advanced data structures.

Approach 2: Balanced Tree Map (O(log n) updates, O(n) space)

Store intervals in a balanced tree keyed by their start positions (for example TreeMap in Java). The tree keeps intervals sorted automatically and allows efficient neighbor lookups. For addRange, locate the first interval that might overlap using a floor or ceiling search, then merge all overlapping intervals while updating the map. removeRange works similarly but may split intervals into two smaller segments. queryRange checks the closest interval starting before left and verifies it extends past right.

Because tree operations like insertion, deletion, and predecessor search run in O(log n), the overall complexity for updates becomes O(log n + k), where k is the number of affected intervals. This makes the structure much more scalable for large numbers of updates.

The technique is conceptually related to interval management problems solved with ordered sets or advanced range structures like a segment tree. While a segment tree can also solve the problem, most interview solutions rely on ordered maps because the implementation is shorter and easier to reason about.

Recommended for interviews: The balanced tree map approach is typically expected in senior-level interviews. It demonstrates understanding of interval merging combined with efficient ordered lookups. Implementing the sorted list version first shows you understand the core interval logic; transitioning to the tree-based solution shows you can optimize operations from linear scans to logarithmic lookups.

Approach 1: Approach 1: Sorted List of Intervals

This approach involves maintaining a sorted list of disjoint intervals. Each interval is represented by a tuple of start and end. The trick is to ensure efficient merging of intervals when adding, removal of specific intervals, and checking for fully covered range during queries. The list remains sorted to optimize these operations.

Python

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

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

    def queryRange(self, left: int, right: int) -> bool:
        for start, end in self.intervals:
            if start <= left and right <= end:
                return True
        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

The class maintains a list of tuples representing intervals. The addRange method merges overlapping or adjacent intervals into the list. The queryRange checks if an entire range falls within one of the tracked intervals, and removeRange removes parts of intervals that fall within a given range by splitting intervals as necessary.

Complexity

Time complexity for addRange, queryRange, and removeRange is O(n), where n is the number of tracked intervals. Space complexity is O(n) due to storage of intervals.

Try this approach in the editor

Approach 2: Approach 2: Balanced Tree (BST)

A more advanced approach involves using a balanced binary search tree to maintain the intervals, allowing logarithmic time complexity for add, query, and remove operations.

Java

import java.util.TreeMap;

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

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

    public void addRange(int left, int right) {
        Integer start = intervals.floorKey(left);
        Integer end = intervals.floorKey(right);
        if (start != null && intervals.get(start) >= left) {
            left = start;
        }
        if (end != null && intervals.get(end) > right) {
            right = intervals.get(end);
        }
        intervals.subMap(left, right).clear();
        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);
        Integer end = intervals.floorKey(right);
        if (end != null && intervals.get(end) > right) {
            intervals.put(right, intervals.get(end));
        }
        if (start != null && intervals.get(start) > left) {
            intervals.put(start, left);
        }
        intervals.subMap(left, right).clear();
    }
}

This implementation uses Java's TreeMap, which is a balanced binary search tree. The keys in the tree represent the start of intervals, and the values represent the ends. This structure allows for efficient merging and querying of intervals using logarithmic time operations.

Complexity

Time complexity for addRange, queryRange, and removeRange is O(log n), where n is the number of distinct intervals. Space complexity is O(n) due to storage requirements of the tree map.

Try this approach in the editor

Approach 3: Approach 1: Using a Sorted List of Intervals

This approach utilizes a sorted list of intervals to represent the tracked ranges. The key operations involve merging intervals upon addition, checking containment for queries, and properly splitting and removing intervals as needed. The merging operation helps to keep the list of intervals minimal and efficiently queryable.

The basic idea is to maintain a list with no overlapping intervals, merge overlapping intervals on addition, and adjust intervals on remove operations accordingly.

Python

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

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

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

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

This Python implementation uses a sorted list of intervals to keep track of the range. The addRange function merges overlapping intervals. The queryRange function checks if the given range is fully covered by any existing interval, and removeRange updates the intervals by effectively splitting any overlapping intervals to remove the specified range. The list remains sorted, ensuring efficient updates and queries.

Complexity

Time Complexity: O(N) per operation, where N is the number of tracked ranges. This is because merging intervals during addition and updating during removal requires traversing the list.
Space Complexity: O(N), where N is the amount of memory required to store the intervals.

Try this approach in the editor

Approach 4: Approach 2: Using a Balanced Tree Map

In this approach, a balanced binary search tree (or map) is used to keep track of the intervals. The idea is to leverage the ordering properties of a tree structure to efficiently find, add, and remove intervals.
Each node in the tree represents an interval, and operations on intervals involve traversals and updates of the tree nodes. This ensures logarithmic time complexity for most operations.

Java

import java.util.TreeMap;

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

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

    public void addRange(int left, int right) {
        Integer start = intervals.floorKey(left);
        Integer end = intervals.floorKey(right);
        if (start != null && intervals.get(start) >= left) {
            left = start;
        }
        if (end != null && intervals.get(end) > right) {
            right = intervals.get(end);
        }
        intervals.subMap(left, right).clear();
        intervals.put(left, right);
    }

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

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

This Java implementation leverages a TreeMap to automatically sort and manage the intervals. The addRange method finds existing overlapping ranges and merges them. The queryRange method checks if the range falls completely within any existing tracked range. The removeRange method carefully adjusts intervals by potentially splitting existing ones. The use of a TreeMap ensures that lookups and modifications remain efficient.

Complexity

Time Complexity: O(log N) per operation due to operations on the tree structure for lookups and updates.
Space Complexity: O(N), as we need to store the intervals in the tree map.

Try this approach in the editor

Approach 5: Segment Tree

According to the problem description, we need to maintain a set of intervals, supporting operations of interval addition, deletion, and query. For the addition and deletion of intervals, we can use a segment tree to maintain the set of intervals.

The segment tree divides the entire interval into multiple non-continuous sub-intervals, the number of which does not exceed log(width). To update the value of an element, only log(width) intervals need to be updated, and these intervals are all included in a large interval containing the element. When modifying the interval, we need to use lazy propagation to ensure efficiency.

Each node of the segment tree represents an interval;
The segment tree has a unique root node, representing the entire statistical range, such as [1,N];
Each leaf node of the segment tree represents an elementary interval of length 1, [x,x];
For each internal node [l,r], its left child is [l,mid], and the right child is [mid+1,r], where mid=⌊(l+r)/2⌋ (rounded down).

Due to the large data range of the problem, we can implement it with a dynamically allocated segment tree. A dynamically allocated segment tree means that we only allocate nodes when needed, instead of allocating all nodes at the beginning. This can save space, but it requires lazy propagation to maintain interval modification.

In terms of time complexity, the time complexity of each operation is O(log n). The space complexity is O(m times log n). Here, m is the number of operations, and n is the data range.

C++

template <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);
 */

TypeScript

class Node {
    left: Node | null;
    right: Node | null;
    add: number;
    v: boolean;

    constructor() {
        this.left = null;
        this.right = null;
        this.add = 0;
        this.v = false;
    }
}

class SegmentTree {
    private root: Node;

    constructor() {
        this.root = new Node();
    }

    modify(
        left: number,
        right: number,
        v: number,
        l: number = 1,
        r: number = 1e9,
        node: Node | null = null,
    ): void {
        if (node === null) {
            node = this.root;
        }

        if (l >= left && r <= right) {
            node.v = v === 1;
            node.add = v;
            return;
        }

        this.pushdown(node);

        const mid = (l + r) >> 1;

        if (left <= mid) {
            this.modify(left, right, v, l, mid, node.left);
        }

        if (right > mid) {
            this.modify(left, right, v, mid + 1, r, node.right);
        }

        this.pushup(node);
    }

    query(
        left: number,
        right: number,
        l: number = 1,
        r: number = 1e9,
        node: Node | null = null,
    ): boolean {
        if (node === null) {
            node = this.root;
        }

        if (l >= left && r <= right) {
            return node.v;
        }

        this.pushdown(node);

        const mid = (l + r) >> 1;
        let result = true;

        if (left <= mid) {
            result = result && this.query(left, right, l, mid, node.left);
        }

        if (right > mid) {
            result = result && this.query(left, right, mid + 1, r, node.right);
        }

        return result;
    }

    pushup(node: Node): void {
        node.v = !!(node.left && node.left.v && node.right && node.right.v);
    }

    pushdown(node: Node): void {
        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 tree: SegmentTree;

    constructor() {
        this.tree = new SegmentTree();
    }

    addRange(left: number, right: number): void {
        this.tree.modify(left, right - 1, 1);
    }

    queryRange(left: number, right: number): boolean {
        return this.tree.query(left, right - 1);
    }

    removeRange(left: number, right: number): void {
        this.tree.modify(left, right - 1, -1);
    }
}

/**
 * Your RangeModule object will be instantiated and called as such:
 * var obj = new RangeModule()
 * obj.addRange(left,right)
 * var param_2 = obj.queryRange(left,right)
 * obj.removeRange(left,right)
 */

const N int = 1e9

type node struct {
	lch   *node
	rch   *node
	added bool
	lazy  int
}

type segmentTree struct {
	root *node
}

func newSegmentTree() *segmentTree {
	return &segmentTree{
		root: new(node),
	}
}

func (t *segmentTree) update(n *node, l, r, i, j, x int) {
	if l >= i && r <= j {
		n.added = x == 1
		n.lazy = x
		return
	}
	t.pushdown(n)
	m := int(uint(l+r) >> 1)
	if i <= m {
		t.update(n.lch, l, m, i, j, x)
	}
	if j > m {
		t.update(n.rch, m+1, r, i, j, x)
	}
	t.pushup(n)
}

func (t *segmentTree) query(n *node, l, r, i, j int) bool {
	if l >= i && r <= j {
		return n.added
	}
	t.pushdown(n)
	v := true
	m := int(uint(l+r) >> 1)
	if i <= m {
		v = v && t.query(n.lch, l, m, i, j)
	}
	if j > m {
		v = v && t.query(n.rch, m+1, r, i, j)
	}
	return v
}

func (t *segmentTree) pushup(n *node) {
	n.added = n.lch.added && n.rch.added
}

func (t *segmentTree) pushdown(n *node) {
	if n.lch == nil {
		n.lch = new(node)
	}
	if n.rch == nil {
		n.rch = new(node)
	}
	if n.lazy != 0 {
		n.lch.added = n.lazy == 1
		n.rch.added = n.lazy == 1
		n.lch.lazy = n.lazy
		n.rch.lazy = n.lazy
		n.lazy = 0
	}
}

type RangeModule struct {
	t *segmentTree
}

func Constructor() RangeModule {
	return RangeModule{
		t: newSegmentTree(),
	}
}

func (this *RangeModule) AddRange(left int, right int) {
	this.t.update(this.t.root, 1, N, left, right-1, 1)
}

func (this *RangeModule) QueryRange(left int, right int) bool {
	return this.t.query(this.t.root, 1, N, left, right-1)
}

func (this *RangeModule) RemoveRange(left int, right int) {
	this.t.update(this.t.root, 1, N, left, right-1, -1)
}

/**
 * Your RangeModule object will be instantiated and called as such:
 * obj := Constructor();
 * obj.AddRange(left,right);
 * param_2 := obj.QueryRange(left,right);
 * obj.RemoveRange(left,right);
 */

Try this approach in the editor

Complexity comparison

Approach	Complexity
Approach 1: Sorted List of Intervals	Time complexity for addRange, queryRange, and removeRange is O(n), where n is the number of tracked intervals. Space complexity is O(n) due to storage of intervals.
Approach 2: Balanced Tree (BST)	Time complexity for addRange, queryRange, and removeRange is O(log n), where n is the number of distinct intervals. Space complexity is O(n) due to storage requirements of the tree map.
Approach 1: Using a Sorted List of Intervals	Time Complexity: `O(N)` per operation, where `N` is the number of tracked ranges. This is because merging intervals during addition and updating during removal requires traversing the list. Space Complexity: `O(N)`, where `N` is the amount of memory required to store the intervals.
Approach 2: Using a Balanced Tree Map	Time Complexity: `O(log N)` per operation due to operations on the tree structure for lookups and updates. Space Complexity: `O(N)`, as we need to store the intervals in the tree map.
Segment Tree	–

Complexity analysis

Approach	Time	Space	When to Use
Sorted List of Intervals	O(n) per operation	O(n)	Simple implementation when the number of intervals is small and updates are infrequent
Balanced Tree Map (BST)	O(log n + k)	O(n)	Best general solution for frequent add/remove operations and large datasets

Frequently asked questions

Is Range Module easy or hard?

Range Module is classified as a Hard problem because it combines data structure design with interval merging logic. Implementing add, remove, and query operations correctly while maintaining non-overlapping intervals requires careful edge-case handling.

Range Module Python or Java solution?

Python implementations often maintain a sorted list of intervals and merge overlaps during updates. Java solutions commonly use TreeMap because it provides efficient predecessor and successor lookups, making interval merging and splitting straightforward.

How to solve Range Module in O(log n)?

Store intervals in a balanced ordered map keyed by their starting position. Use floor or ceiling operations to locate the nearest interval that might overlap with the target range. Merge overlapping intervals during addRange and split intervals during removeRange, keeping the structure sorted.

What is the best approach for Range Module?

The balanced tree map approach is generally the best solution. Intervals are stored in a sorted structure such as Java's TreeMap, allowing logarithmic searches for overlapping ranges. Each update merges or splits only the affected intervals, giving O(log n + k) time where k is the number of overlaps.

Is Range Module asked at Google/Amazon/Meta?

Range management and interval design problems frequently appear in interviews at companies like Google, Amazon, and Meta. The problem tests system-style thinking: designing a data structure with efficient updates and queries while handling overlapping intervals.

What data structure is used in Range Module?

Common solutions use an ordered map or balanced binary search tree to store intervals. Alternatives include segment trees with lazy propagation for very large ranges, though interview solutions usually prefer ordered sets or TreeMap-based interval merging.

What is the time complexity of Range Module?

Using a balanced tree map, addRange and removeRange run in O(log n + k) time due to tree lookups and interval merging. queryRange typically runs in O(log n) because it only needs to check the closest interval before the queried start. Space complexity is O(n) for storing intervals.

Range Module solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Sorted List of Intervals

Approach 2: Approach 2: Balanced Tree (BST)

Approach 3: Approach 1: Using a Sorted List of Intervals

Approach 4: Approach 2: Using a Balanced Tree Map

Approach 5: Segment Tree

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Range Module solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Sorted List of Intervals

Approach 2: Approach 2: Balanced Tree (BST)

Approach 3: Approach 1: Using a Sorted List of Intervals

Approach 4: Approach 2: Using a Balanced Tree Map

Approach 5: Segment Tree

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems