Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Break down a hard problem into reliable checkpoints, edge-case handling, and complexity trade-offs.
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 <= 109104 calls will be made to addRange, queryRange, and removeRange.Problem summary: 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
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Design · Segment Tree
["RangeModule","addRange","removeRange","queryRange","queryRange","queryRange"] [[],[10,20],[14,16],[10,14],[13,15],[16,17]]
merge-intervals)insert-interval)data-stream-as-disjoint-intervals)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #715: Range Module
class 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) 1e9, 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) 1e9, 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);
*/
// Accepted solution for LeetCode #715: Range Module
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);
*/
# Accepted solution for LeetCode #715: Range Module
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)
// Accepted solution for LeetCode #715: Range Module
/**
* [0715] 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 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^9
* At most 10^4 calls will be made to addRange, queryRange, and removeRange.
*
*/
pub struct Solution {}
// problem: https://leetcode.com/problems/range-module/
// discuss: https://leetcode.com/problems/range-module/discuss/?currentPage=1&orderBy=most_votes&query=
// submission codes start here
// Credit: https://leetcode.com/problems/range-module/discuss/2116943/Rust-TreeMap-(Might-not-be-the-most-idiomatic-rust-solution)
struct RangeModule {
intervals: std::collections::BTreeMap<i32, i32>,
}
/**
* `&self` means the method takes an immutable reference.
* If you need a mutable reference, change it to `&mut self` instead.
*/
impl RangeModule {
fn new() -> Self {
Self {
intervals: std::collections::BTreeMap::new(),
}
}
fn add_range(&mut self, left: i32, right: i32) {
let (mut left, mut right) = (left, right);
if let Some((begin, end)) = self.intervals.range(..=left).next_back() {
if *end >= left {
left = std::cmp::min(left, *begin)
}
}
if let Some((_, end)) = self.intervals.range(..=right).next_back() {
if left < *end {
right = std::cmp::max(right, *end)
}
}
let mut new_intervals: std::collections::BTreeMap<i32, i32> = self
.intervals
.clone()
.into_iter()
.filter(|(begin, _)| *begin < left || *begin > right)
.collect();
new_intervals.insert(left, right);
self.intervals = new_intervals;
}
fn query_range(&self, left: i32, right: i32) -> bool {
match self.intervals.range(..=left).next_back() {
Some((_, end)) => *end >= right,
None => false,
}
}
fn remove_range(&mut self, left: i32, right: i32) {
if let Some((_, end)) = self.intervals.range(..=right).next_back() {
if *end > right {
self.intervals.insert(right, *end);
}
}
if let Some((_, end)) = self.intervals.range_mut(..=left).next_back() {
if *end > left {
*end = left;
}
}
let new_intervals: std::collections::BTreeMap<i32, i32> = self
.intervals
.clone()
.into_iter()
.filter(|(begin, _)| *begin < left || *begin >= right)
.collect();
self.intervals = new_intervals;
}
}
/**
* Your RangeModule object will be instantiated and called as such:
* let obj = RangeModule::new();
* obj.add_range(left, right);
* let ret_2: bool = obj.query_range(left, right);
* obj.remove_range(left, right);
*/
// submission codes end
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_0715_example_1() {
let mut range_module = RangeModule::new();
range_module.add_range(10, 20);
range_module.remove_range(14, 16);
assert_eq!(range_module.query_range(10, 14), true); // return True,(Every number in [10, 14) is being tracked)
assert_eq!(range_module.query_range(13, 15), false); // return False,(Numbers like 14, 14.03, 14.17 in [13, 15) are not being tracked)
assert_eq!(range_module.query_range(16, 17), true); // return True, (The number 16 in [16, 17) is still being tracked, despite the remove operation)
}
}
// Accepted solution for LeetCode #715: Range Module
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)
*/
Use this to step through a reusable interview workflow for this problem.
Use a simple list or array for storage. Each operation (get, put, remove) requires a linear scan to find the target element — O(n) per operation. Space is O(n) to store the data. The linear search makes this impractical for frequent operations.
Design problems target O(1) amortized per operation by combining data structures (hash map + doubly-linked list for LRU, stack + min-tracking for MinStack). Space is always at least O(n) to store the data. The challenge is achieving constant-time operations through clever structure composition.
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.