Leetcode #715: Range Module
In this guide, we solve Leetcode #715 Range Module in Python and focus on the core idea that makes the solution efficient.
You will see the intuition, the step-by-step method, and a clean Python implementation you can use in interviews.
Problem Statement
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.
Quick Facts
- Difficulty: Hard
- Premium: No
- Tags: Design, Segment Tree, Ordered Set
Intuition
We need to support multiple operations efficiently, so the internal design matters most.
Choosing the right combination of structures is the key to meeting the constraints.
Approach
List the required operations and select data structures that optimize them.
Implement each operation with clear invariants.
Steps:
- List the required operations.
- Pick supporting structures.
- Implement methods with clear invariants.
Example
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)
Python Solution
class 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)
Complexity
The time complexity is Varies by operation. The space complexity is .
Edge Cases and Pitfalls
Watch for boundary values, empty inputs, and duplicate values where applicable. If the problem involves ordering or constraints, confirm the invariant is preserved at every step.
Summary
This Python solution focuses on the essential structure of the problem and keeps the implementation interview-friendly while meeting the constraints.