Range Module — Solution in Python, Java & C++
Range Module solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem, asked at Amazon and Google.
Range Module is a hard coding problem on binary search, ordered set and segment tree, asked in Amazon, Google and Uber interviews.
- Difficulty: Hard
- Topics: Binary Search, Ordered Set, Segment Tree
- Asked at: Amazon, Google, Uber
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A range module tracks which real numbers are currently covered. Every range is half-open: [left, right) contains every x with left <= x < right.
Write the class RangeModule:
RangeModule()starts with nothing tracked.void addRange(int left, int right)starts tracking every number in[left, right). Parts that are already tracked stay tracked.boolean queryRange(int left, int right)returnstrueif every number in[left, right)is currently tracked.void removeRange(int left, int right)stops tracking every number in[left, right)that is currently tracked.
The judge calls the methods in the order listed in the first input line, with the arguments in the second; the expected output holds each call's result, null for the constructor and for every method that returns nothing.
Example 1
Input: ["RangeModule","addRange","removeRange","queryRange","queryRange","queryRange"]
[[],[5,15],[8,10],[5,8],[6,11],[10,15]]
Output: [null,null,null,true,false,true]
Explanation: After removing [8, 10) from [5, 15), the tracked numbers are [5, 8) and [10, 15). [5, 8) is covered, [6, 11) has a gap at [8, 10), and [10, 15) is covered.
Example 2
Input: ["RangeModule","addRange","addRange","queryRange","removeRange","queryRange","queryRange"]
[[],[1,3],[3,1000000000],[2,999999999],[1,1000000000],[1,2],[5,6]]
Output: [null,null,null,true,null,false,false]
Explanation: [1, 3) and [3, 10^9) touch, so together they cover [1, 10^9). Removing [1, 10^9) clears everything.
Constraints
1 <= left < right <= 10^9At most 10^4 calls are made in total to addRange, queryRange and removeRange
Hints for Range Module
Hint 1
Store the tracked numbers as a sorted list of disjoint intervals; merge intervals that overlap or touch so that every maximal tracked stretch is one interval.
Hint 2
queryRange(l, r)is then a single check: the last interval starting at or beforelmust end at or afterr.Hint 3
Both updates affect one contiguous block of intervals, which two binary searches find.
addRangereplaces that block by one merged interval;removeRangereplaces it by at most two leftover pieces.
How to solve Range Module
Keep the tracked set as sorted, disjoint, non-touching half-open intervals. Every operation locates the block of intervals it concerns with binary search and rewrites only that block.
Approach
addRange(l, r): letibe the first interval whose end is>= landjthe first whose start is> r. Intervalsi..j-1overlap or touch[l, r); replace them with[min(l, start[i]), max(r, end[j-1]))(or just insert[l, r)atiwhen the block is empty).removeRange(l, r): letibe the first interval whose end is> landjthe first whose start is>= r. Replace intervalsi..j-1with what survives of them:[start[i], l)ifstart[i] < l, and[r, end[j-1])ifend[j-1] > r.queryRange(l, r): take the last interval whose start is<= l; the answer is whether it exists and its end is>= r.
Why it works
Because intervals are disjoint and sorted, both their starts and their ends are increasing, so "the intervals meeting [l, r]" is one contiguous index range found by binary search. Merging touching intervals means a covered stretch is always a single interval, which is why one interval must contain [l, r) for a query to succeed — no union of two stored intervals can cover more than either does alone.
Complexity
- Time —
O(log n) to locate plus O(n) to splice an array (O(log n) amortised with a balanced tree), where n is the number of stored intervals - Space —
O(n)
Pitfalls
- The ranges are half-open:
[1, 3)and[3, 5)together cover[1, 5), but[1, 3)does not contain 3. - In
removeRange, an interval that only touches the removed range (ends exactly atlor starts exactly atr) must be left untouched — use strict comparisons there.
Reference solution
Python
from bisect import bisect_left, bisect_right
class RangeModule:
def __init__(self):
self.starts = [] # disjoint, non-touching half-open intervals, sorted
self.ends = []
def addRange(self, left: int, right: int) -> None:
i = bisect_left(self.ends, left) # first interval ending at or after left
j = bisect_right(self.starts, right) # first interval starting after right
if i < j:
left = min(left, self.starts[i])
right = max(right, self.ends[j - 1])
self.starts[i:j] = [left]
self.ends[i:j] = [right]
def queryRange(self, left: int, right: int) -> bool:
k = bisect_right(self.starts, left) - 1 # last interval starting at or before left
return k >= 0 and self.ends[k] >= right
def removeRange(self, left: int, right: int) -> None:
i = bisect_right(self.ends, left) # first interval ending after left
j = bisect_left(self.starts, right) # first interval starting at or after right
if i >= j:
return
ns, ne = [], []
if self.starts[i] < left:
ns.append(self.starts[i])
ne.append(left)
if self.ends[j - 1] > right:
ns.append(right)
ne.append(self.ends[j - 1])
self.starts[i:j] = ns
self.ends[i:j] = neJava
class RangeModule {
private ArrayList<Integer> starts = new ArrayList<>(), ends = new ArrayList<>(); // disjoint, non-touching, sorted
public RangeModule() {
}
private static int bound(ArrayList<Integer> a, int x, boolean strict) { // first index >= x (strict: > x)
int lo = 0, hi = a.size();
while (lo < hi) {
int mid = (lo + hi) >>> 1;
int v = a.get(mid);
if (strict ? v <= x : v < x) lo = mid + 1; else hi = mid;
}
return lo;
}
public void addRange(int left, int right) {
int i = bound(ends, left, false), j = bound(starts, right, true);
if (i < j) {
left = Math.min(left, starts.get(i));
right = Math.max(right, ends.get(j - 1));
}
starts.subList(i, j).clear();
ends.subList(i, j).clear();
starts.add(i, left);
ends.add(i, right);
}
public boolean queryRange(int left, int right) {
int k = bound(starts, left, true) - 1;
return k >= 0 && ends.get(k) >= right;
}
public void removeRange(int left, int right) {
int i = bound(ends, left, true), j = bound(starts, right, false);
if (i >= j) return;
int s0 = starts.get(i), e1 = ends.get(j - 1);
starts.subList(i, j).clear();
ends.subList(i, j).clear();
if (e1 > right) { starts.add(i, right); ends.add(i, e1); }
if (s0 < left) { starts.add(i, s0); ends.add(i, left); }
}
}C++
class RangeModule {
map<int, int> iv; // start -> end: disjoint, non-touching half-open intervals
public:
RangeModule() {}
void addRange(int left, int right) {
auto it = iv.upper_bound(left);
if (it != iv.begin() && prev(it)->second >= left) --it; // the interval before touches [left, right)
while (it != iv.end() && it->first <= right) {
left = min(left, it->first);
right = max(right, it->second);
it = iv.erase(it);
}
iv[left] = right;
}
bool queryRange(int left, int right) {
auto it = iv.upper_bound(left);
if (it == iv.begin()) return false;
return prev(it)->second >= right;
}
void removeRange(int left, int right) {
auto it = iv.upper_bound(left);
if (it != iv.begin() && prev(it)->second > left) --it; // the interval before overlaps
int s0 = -1, e1 = -1;
while (it != iv.end() && it->first < right) {
if (it->first < left) s0 = it->first;
if (it->second > right) e1 = it->second;
it = iv.erase(it);
}
if (s0 >= 0) iv[s0] = left;
if (e1 >= 0) iv[right] = e1;
}
};JavaScript
// first index whose value is >= x (strict: > x) in a sorted array
function rmBound(a, x, strict) {
var lo = 0, hi = a.length;
while (lo < hi) {
var mid = (lo + hi) >> 1;
if (strict ? a[mid] <= x : a[mid] < x) lo = mid + 1; else hi = mid;
}
return lo;
}
var RangeModule = function() {
this.starts = []; // disjoint, non-touching half-open intervals, sorted
this.ends = [];
};
RangeModule.prototype.addRange = function(left, right) {
var i = rmBound(this.ends, left, false), j = rmBound(this.starts, right, true);
if (i < j) {
left = Math.min(left, this.starts[i]);
right = Math.max(right, this.ends[j - 1]);
}
this.starts.splice(i, j - i, left);
this.ends.splice(i, j - i, right);
};
RangeModule.prototype.queryRange = function(left, right) {
var k = rmBound(this.starts, left, true) - 1;
return k >= 0 && this.ends[k] >= right;
};
RangeModule.prototype.removeRange = function(left, right) {
var i = rmBound(this.ends, left, true), j = rmBound(this.starts, right, false);
if (i >= j) return;
var ns = [], ne = [];
if (this.starts[i] < left) { ns.push(this.starts[i]); ne.push(left); }
if (this.ends[j - 1] > right) { ns.push(right); ne.push(this.ends[j - 1]); }
Array.prototype.splice.apply(this.starts, [i, j - i].concat(ns));
Array.prototype.splice.apply(this.ends, [i, j - i].concat(ne));
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 189 binary search problems · the whole catalogue
Learn the technique: Binary Search