LeetCode 715: Range Module

Problem Restatement

We need to design a data structure called RangeModule.

It tracks ranges of numbers.

Each range is represented as a half-open interval:

[left, right)

This means the interval includes left, but does not include right.

The data structure must support three operations:

The intervals may overlap, merge, or split.

Input and Output

Important constraints:

The class shape is:

class RangeModule:

    def __init__(self):
        ...

    def addRange(self, left: int, right: int) -> None:
        ...

    def queryRange(self, left: int, right: int) -> bool:
        ...

    def removeRange(self, left: int, right: int) -> None:
        ...

Examples

Example:

rangeModule = RangeModule()
rangeModule.addRange(10, 20)
rangeModule.removeRange(14, 16)
rangeModule.queryRange(10, 14)
rangeModule.queryRange(13, 15)
rangeModule.queryRange(16, 17)

After adding [10, 20), the tracked interval is:

[10, 20)

After removing [14, 16), the tracked intervals become:

[10, 14)
[16, 20)

Now:

First Thought: Track Every Number

A simple idea is to store every tracked number in a set.

For addRange(left, right), insert every integer from left to right - 1.

For removeRange(left, right), remove every integer from left to right - 1.

For queryRange(left, right), check every integer from left to right - 1.

This fails for two reasons.

First, the range can go up to 10^9.

Second, the problem describes real numbers in the interval, not only integers. We should track intervals, not individual points.

Key Insight

Store a sorted list of disjoint tracked intervals.

For example, after some operations, we may store:

[(10, 14), (16, 20), (30, 40)]

The invariant is:

1. Intervals are sorted by start.
2. Intervals do not overlap.
3. Adjacent or overlapping intervals are merged.

With this representation:

• addRange merges overlapping intervals.
• removeRange cuts overlapping intervals.
• queryRange checks whether one stored interval fully covers the query.

Because there are at most 10^4 operations, a sorted list is simple and accepted in Python.

Algorithm: Add Range

To add [left, right):

1. Create an empty list new_intervals.
2. Scan every existing interval (start, end).
3. If the interval ends before left, keep it.
4. If the interval starts after right, insert the merged new interval once, then keep the rest.
5. If the interval overlaps [left, right), merge it by updating:
   • left = min(left, start)
   • right = max(right, end)
6. At the end, insert the merged interval if it has not been inserted yet.

Overlapping intervals become one larger tracked interval.

Algorithm: Query Range

To query [left, right):

1. Find the interval whose start is the greatest start less than or equal to left.
2. Check whether that interval ends at or after right.

If such an interval exists, then the whole query range is tracked.

Otherwise, some part is missing.

Algorithm: Remove Range

To remove [left, right):

1. Create an empty list new_intervals.
2. Scan every existing interval (start, end).
3. If it does not overlap [left, right), keep it unchanged.
4. If it overlaps:
   • Keep the left leftover [start, left) if start < left.
   • Keep the right leftover [right, end) if right < end.
5. Replace the interval list.

Removing a range may split one interval into two.

Correctness

The data structure stores exactly the tracked set as a sorted list of disjoint half-open intervals.

For addRange, every interval that does not overlap the added range remains unchanged. Every interval that overlaps the added range is merged into one interval whose boundaries are the minimum left endpoint and maximum right endpoint of all overlapping parts. Therefore the new interval covers exactly the old tracked values plus every value in [left, right), with no gaps inside the merged region.

For queryRange, the query can be fully tracked only if one stored disjoint interval contains it. Since the stored intervals are sorted and non-overlapping, it is sufficient to check the interval immediately before or at left. If that interval ends at or after right, every number in [left, right) is tracked. Otherwise, no other interval can cover the missing part beginning at left.

For removeRange, every non-overlapping interval remains tracked. For each overlapping interval, the algorithm removes the intersection with [left, right) and keeps only the portions before left and after right. These leftovers are exactly the parts that should remain tracked.

After each operation, the list remains sorted and disjoint. Therefore all operations preserve the correct representation of the tracked ranges.

Complexity

Let n be the number of stored intervals.

The coordinate range is large, but the number of stored intervals is bounded by the number of operations.

Implementation

from bisect import bisect_right

class RangeModule:

    def __init__(self):
        self.intervals = []

    def addRange(self, left: int, right: int) -> None:
        new_intervals = []
        placed = False

        for start, end in self.intervals:
            if end < left:
                new_intervals.append((start, end))
            elif right < start:
                if not placed:
                    new_intervals.append((left, right))
                    placed = True

                new_intervals.append((start, end))
            else:
                left = min(left, start)
                right = max(right, end)

        if not placed:
            new_intervals.append((left, right))

        self.intervals = new_intervals

    def queryRange(self, left: int, right: int) -> bool:
        starts = [start for start, _ in self.intervals]
        index = bisect_right(starts, left) - 1

        if index < 0:
            return False

        start, end = self.intervals[index]
        return start <= left and right <= end

    def removeRange(self, left: int, right: int) -> None:
        new_intervals = []

        for start, end in self.intervals:
            if end <= left or right <= start:
                new_intervals.append((start, end))
            else:
                if start < left:
                    new_intervals.append((start, left))

                if right < end:
                    new_intervals.append((right, end))

        self.intervals = new_intervals

Code Explanation

The module stores disjoint intervals:

self.intervals = []

In addRange, we rebuild the interval list.

If an old interval is completely before the new range, keep it:

if end < left:
    new_intervals.append((start, end))

If an old interval is completely after the new range, place the new merged range before it:

elif right < start:
    if not placed:
        new_intervals.append((left, right))
        placed = True

Otherwise, the two intervals overlap or touch, so merge them:

else:
    left = min(left, start)
    right = max(right, end)

For queryRange, we find the interval with the largest start not greater than left:

index = bisect_right(starts, left) - 1

Then we check whether it covers the full query:

return start <= left and right <= end

For removeRange, if an interval does not overlap the removed range, keep it:

if end <= left or right <= start:
    new_intervals.append((start, end))

If it overlaps, keep only the leftovers:

if start < left:
    new_intervals.append((start, left))

if right < end:
    new_intervals.append((right, end))

Half-Open Interval Details

The interval [left, right) includes left and excludes right.

This affects boundary checks.

These two intervals touch but do not overlap in real-number coverage:

[10, 14)
[14, 20)

For tracking ranges, we may merge them into:

[10, 20)

because their union has no gap.

For removal, if we remove:

[14, 16)

from:

[10, 20)

we keep:

[10, 14)
[16, 20)

The point 14 is removed because it belongs to [14, 16).

The point 16 remains because the removed interval excludes 16.

Testing

def test_range_module():
    rm = RangeModule()

    rm.addRange(10, 20)
    rm.removeRange(14, 16)

    assert rm.queryRange(10, 14) is True
    assert rm.queryRange(13, 15) is False
    assert rm.queryRange(16, 17) is True

    rm = RangeModule()
    rm.addRange(10, 20)
    rm.addRange(15, 25)

    assert rm.queryRange(10, 25) is True
    assert rm.queryRange(20, 24) is True
    assert rm.queryRange(25, 26) is False

    rm.removeRange(12, 22)

    assert rm.queryRange(10, 12) is True
    assert rm.queryRange(12, 13) is False
    assert rm.queryRange(22, 25) is True

    rm = RangeModule()
    rm.addRange(1, 5)
    rm.addRange(5, 10)

    assert rm.queryRange(1, 10) is True

    print("all tests passed")

test_range_module()

Test coverage: