Range Module

Hard
2092.

Range Module

Range Module is a hard coding problem on binary search, ordered set and segment tree, asked in Amazon, Google and Uber interviews.

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) returns true if 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^9
  • At most 10^4 calls are made in total to addRange, queryRange and removeRange
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 */
var RangeModule = function() {
    
};

/**
 * @param {number} left
 * @param {number} right
 * @return {void}
 */
RangeModule.prototype.addRange = function(left, right) {
    
};

/**
 * @param {number} left
 * @param {number} right
 * @return {boolean}
 */
RangeModule.prototype.queryRange = function(left, right) {
    
};

/**
 * @param {number} left
 * @param {number} right
 * @return {void}
 */
RangeModule.prototype.removeRange = function(left, right) {
    
};

Sign in to run your own test cases

Sign in

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.

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) returns true if 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^9
  • At most 10^4 calls are made in total to addRange, queryRange and removeRange

Hints for Range Module

  1. 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.

  2. Hint 2

    queryRange(l, r) is then a single check: the last interval starting at or before l must end at or after r.

  3. Hint 3

    Both updates affect one contiguous block of intervals, which two binary searches find. addRange replaces that block by one merged interval; removeRange replaces 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

  1. addRange(l, r): let i be the first interval whose end is >= l and j the first whose start is > r. Intervals i..j-1 overlap or touch [l, r); replace them with [min(l, start[i]), max(r, end[j-1])) (or just insert [l, r) at i when the block is empty).
  2. removeRange(l, r): let i be the first interval whose end is > l and j the first whose start is >= r. Replace intervals i..j-1 with what survives of them: [start[i], l) if start[i] < l, and [r, end[j-1]) if end[j-1] > r.
  3. 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 at l or starts exactly at r) 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] = ne

Java

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