Approach #1: Maintain Sorted Disjoint Intervals [Accepted]

Intuition

Because left, right < 10^9, we need to deal with the coordinates abstractly. Let\'s maintain some sorted structure of disjoint intervals. These intervals will be closed (eg. we don\'t store [[1, 2], [2, 3]]; we would store [[1, 3]] instead.)

In this article, we will go over Python and Java versions separately, as the data structures available to us that are relevant to the problem are substantially different.

Algorithm (Python)

We will maintain the structure as a list self.ranges = [].

Adding a Range

When we want to add a range, we first find the indices i, j = self._bounds(left, right) for which self.ranges[i: j+1] touches (in a closed sense - not halfopen) the given interval [left, right]. We can find this in log time by making steps of size 100, 10, then 1 in our linear search from both sides.

Every interval touched by [left, right] will be replaced by the single interval [min(left, self.ranges[i][0]), max(right, self.ranges[j][1])].

Removing a Range

Again, we use i, j = self._bounds(...) to only work in the relevant subset of self.ranges that is in the neighborhood of our given range [left, right). For each interval [x, y) from self.ranges[i:j+1], we may have some subset of that interval to the left and/or right of [left, right). We replace our current interval [x, y) with those (up to 2) new intervals.

Querying a Range

As the intervals are sorted, we use binary search to find the single interval that could intersect [left, right), then verify that it does.

Python

class RangeModule(object):\n    def __init__(self):\n        self.ranges = []\n\n    def _bounds(self, left, right):\n        i, j = 0, len(self.ranges) - 1\n        for d in (100, 10, 1):\n            while i + d - 1 < len(self.ranges) and self.ranges[i+d-1][1] < left:\n                i += d\n            while j >= d - 1 and self.ranges[j-d+1][0] > right:\n                j -= d\n        return i, j\n\n    def addRange(self, left, right):\n        i, j = self._bounds(left, right)\n        if i <= j:\n            left = min(left, self.ranges[i][0])\n            right = max(right, self.ranges[j][1])\n        self.ranges[i:j+1] = [(left, right)]\n\n    def queryRange(self, left, right):\n        i = bisect.bisect_left(self.ranges, (left, float(\'inf\')))\n        if i: i -= 1\n        return (bool(self.ranges) and\n                self.ranges[i][0] <= left and\n                right <= self.ranges[i][1])\n\n    def removeRange(self, left, right):\n        i, j = self._bounds(left, right)\n        merge = []\n        for k in xrange(i, j+1):\n            if self.ranges[k][0] < left:\n                merge.append((self.ranges[k][0], left))\n            if right < self.ranges[k][1]:\n                merge.append((right, self.ranges[k][1]))\n        self.ranges[i:j+1] = merge\n

Algorithm (Java)

We will maintain the structure as a TreeSet ranges = new TreeSet<Interval>();. We introduce a new Comparable class Interval to represent our half-open intervals. They compare by right-most coordinate as later we will see that it simplifies our work. Also note that this ordering is consistent with equals, which is important when dealing with Sets.

Adding and Removing a Range

The basic structure of adding and removing a range is the same. First, we must iterate over the relevant subset of ranges. This is done using iterators so that we can itr.remove on the fly, and breaking when the intervals go too far to the right.

The critical logic of addRange is simply to make left, right the smallest and largest seen coordinates. After, we add one giant interval representing the union of all intervals seen that touched [left, right].

The logic of removeRange is to remember in todo the intervals we wanted to replace the removed interval with. After, we can add them all back in.

Querying a Range

As the intervals are sorted, we search to find the single interval that could intersect [left, right), then verify that it does. As the TreeSet uses a balanced (red-black) tree, this has logarithmic complexity.

Java

class RangeModule {\n    TreeSet<Interval> ranges;\n    public RangeModule() {\n        ranges = new TreeSet();\n    }\n\n    public void addRange(int left, int right) {\n        Iterator<Interval> itr = ranges.tailSet(new Interval(0, left - 1)).iterator();\n        while (itr.hasNext()) {\n            Interval iv = itr.next();\n            if (right < iv.left) break;\n            left = Math.min(left, iv.left);\n            right = Math.max(right, iv.right);\n            itr.remove();\n        }\n        ranges.add(new Interval(left, right));\n    }\n\n    public boolean queryRange(int left, int right) {\n        Interval iv = ranges.higher(new Interval(0, left));\n        return (iv != null && iv.left <= left && right <= iv.right);\n    }\n\n    public void removeRange(int left, int right) {\n        Iterator<Interval> itr = ranges.tailSet(new Interval(0, left)).iterator();\n        ArrayList<Interval> todo = new ArrayList();\n        while (itr.hasNext()) {\n            Interval iv = itr.next();\n            if (right < iv.left) break;\n            if (iv.left < left) todo.add(new Interval(iv.left, left));\n            if (right < iv.right) todo.add(new Interval(right, iv.right));\n            itr.remove();\n        }\n        for (Interval iv: todo) ranges.add(iv);\n    }\n}\n\nclass Interval implements Comparable<Interval>{\n    int left;\n    int right;\n\n    public Interval(int left, int right){\n        this.left = left;\n        this.right = right;\n    }\n\n    public int compareTo(Interval that){\n        if (this.right == that.right) return this.left - that.left;\n        return this.right - that.right;\n    }\n}\n

Complexity Analysis

\n
• \n

  Time Complexity: Let $$K$$ be the number of elements in ranges. addRange and removeRange operations have $$O(K)$$ complexity. queryRange has $$O(\\log K)$$ complexity. Because addRange, removeRange adds at most 1 interval at a time, you can bound these further. For example, if there are $$A$$ \naddRange, $$R$$ \nremoveRange, and $$Q$$ \nqueryRange number of operations respectively, we can express our complexity as $$O((A+R)^2 Q \\log(A+R))$$ .

  \n
\n
• \n

  Space Complexity: $$O(A+R)$$ , the space used by ranges.

  \n
\n

Analysis written by: @awice.