LeetCode 715 - Range Module

LeetCode Problem 715

Difficulty: 🔴 Hard
Topics: Design, Segment Tree, Ordered Set

Solution

Problem Understanding

This problem asks us to design a data structure that dynamically tracks intervals on the number line. The tracked intervals are represented as half-open intervals, meaning [left, right) includes every value x such that left <= x < right.

The data structure must support three operations:

• addRange(left, right) marks every value in [left, right) as tracked.
• queryRange(left, right) checks whether every value in [left, right) is currently tracked.
• removeRange(left, right) removes tracking for every value in [left, right).

The important detail is that intervals represent continuous ranges of real numbers, not just integers. That means we cannot discretize the range naïvely unless we use coordinate compression or a more advanced structure.

The constraints are significant:

• Values can be as large as 10^9
• Up to 10^4 operations are performed

A direct boolean array is impossible because the coordinate range is enormous. We need a structure that stores only meaningful intervals rather than every individual point.

The core challenge is maintaining overlapping intervals efficiently. Operations may partially overlap existing ranges, fully overlap them, or split them into smaller segments.

For example:

• Adding [10, 20) then adding [15, 25) should merge into [10, 25)

• Removing [14, 16) from [10, 20) should split the interval into:

• [10, 14)

• [16, 20)

Several edge cases are important:

• Adjacent intervals like [1, 5) and [5, 10) should merge cleanly because together they form continuous coverage.
• Removing a middle portion may split one interval into two.
• Querying a partially covered interval must return false.
• Multiple overlapping adds and removes must preserve consistent interval boundaries.

Because the number line is sparse and operations are relatively limited, storing only merged disjoint intervals is the key insight.

Approaches

Brute Force Approach

A brute-force solution would attempt to track every individual point in the range. One possible implementation would use a set containing all tracked integers.

For example:

• addRange(10, 20) inserts integers 10 through 19
• removeRange(14, 16) removes 14 and 15
• queryRange(10, 14) checks whether all integers exist

This approach works for integer-only interpretations, but the problem explicitly defines ranges over real numbers. More importantly, the coordinate range reaches 10^9, making explicit storage impossible.

Even if we ignored the real-number issue and only considered integers, adding a range of length 10^9 would require enormous memory and time.

Therefore, brute force is infeasible.

Optimal Approach

The key observation is that the number of operations is small, but the coordinate range is huge. Instead of storing every point, we store only merged disjoint intervals.

The data structure maintains a sorted list of non-overlapping intervals:

[(1, 5), (10, 20), (30, 40)]

Whenever we add a range:

• Merge overlapping or adjacent intervals
• Preserve sorted order
• Maintain non-overlapping structure

Whenever we remove a range:

• Trim intervals that partially overlap
• Split intervals if necessary
• Remove fully covered intervals

Queries become efficient because we only need to locate whether one interval completely covers the query range.

This interval-merging strategy dramatically reduces storage requirements and keeps operations efficient.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(range size) per operation	O(range size)	Impossible for coordinates up to 10^9
Optimal	O(n) per operation	O(n)	Stores only merged disjoint intervals

Here, n is the number of stored intervals.

Algorithm Walkthrough

We maintain a sorted list called intervals, where each interval is represented as [start, end).

Example:

[(1, 5), (10, 20), (30, 40)]

The intervals are always:

• Sorted by start value
• Non-overlapping
• Maximally merged

addRange(left, right)

1. Create a new result list.
2. Traverse existing intervals from left to right.
3. Copy all intervals that end before left because they do not overlap.
4. For overlapping intervals:

• Expand left to the minimum start
• Expand right to the maximum end
• This merges all intersecting intervals into one larger interval.

5. Insert the merged interval.
6. Append remaining intervals after the merge.

This guarantees that overlapping intervals become a single continuous interval.

queryRange(left, right)

1. Traverse intervals in sorted order.
2. Find the first interval whose end is greater than left.
3. If that interval also satisfies:

• start <= left
• end >= right

then the entire query range is covered. 4. Otherwise return false.

Because intervals are non-overlapping and sorted, only one interval can possibly contain the query range.

removeRange(left, right)

1. Traverse all intervals.
2. For intervals completely outside the removal range:

• Keep them unchanged.

3. For overlapping intervals:

• Keep the left non-overlapping portion if it exists.
• Keep the right non-overlapping portion if it exists.

For example:

Existing: [10, 20)
Remove:   [14, 16)

Result:
[10, 14)
[16, 20)

This may split one interval into two.

Why it works

The invariant is that the interval list always remains:

• Sorted
• Non-overlapping
• Maximally merged

Every operation preserves this invariant.

Because overlapping intervals are merged immediately during insertion, and removal carefully trims overlapping regions, the structure always accurately represents the tracked regions of the number line.

Queries are correct because any covered range must lie entirely within one merged interval.

Python Solution

from typing import List

class RangeModule:

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

    def addRange(self, left: int, right: int) -> None:
        merged = []
        i = 0
        n = len(self.intervals)

        while i < n and self.intervals[i][1] < left:
            merged.append(self.intervals[i])
            i += 1

        while i < n and self.intervals[i][0] <= right:
            left = min(left, self.intervals[i][0])
            right = max(right, self.intervals[i][1])
            i += 1

        merged.append([left, right])

        while i < n:
            merged.append(self.intervals[i])
            i += 1

        self.intervals = merged

    def queryRange(self, left: int, right: int) -> bool:
        for start, end in self.intervals:
            if start <= left and end >= right:
                return True

            if start > left:
                return False

        return False

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

        for start, end in self.intervals:
            if end <= left or start >= right:
                updated.append([start, end])
            else:
                if start < left:
                    updated.append([start, left])

                if end > right:
                    updated.append([right, end])

        self.intervals = updated

The implementation stores intervals in a sorted list.

The addRange method performs interval merging. First it copies intervals completely before the insertion range. Then it merges every overlapping interval into one larger interval. Finally it appends all remaining intervals.

The queryRange method scans intervals in order. Because intervals are sorted and non-overlapping, only one interval could possibly fully contain the query range.

The removeRange method rebuilds the interval list. Overlapping intervals are trimmed appropriately. If removal occurs in the middle of an interval, the interval is split into two smaller intervals.

The implementation keeps the interval list normalized after every operation.

Go Solution

package main

type RangeModule struct {
	intervals [][]int
}

func Constructor() RangeModule {
	return RangeModule{
		intervals: [][]int{},
	}
}

func (this *RangeModule) AddRange(left int, right int) {
	merged := [][]int{}
	i := 0
	n := len(this.intervals)

	for i < n && this.intervals[i][1] < left {
		merged = append(merged, this.intervals[i])
		i++
	}

	for i < n && this.intervals[i][0] <= right {
		if this.intervals[i][0] < left {
			left = this.intervals[i][0]
		}

		if this.intervals[i][1] > right {
			right = this.intervals[i][1]
		}

		i++
	}

	merged = append(merged, []int{left, right})

	for i < n {
		merged = append(merged, this.intervals[i])
		i++
	}

	this.intervals = merged
}

func (this *RangeModule) QueryRange(left int, right int) bool {
	for _, interval := range this.intervals {
		start := interval[0]
		end := interval[1]

		if start <= left && end >= right {
			return true
		}

		if start > left {
			return false
		}
	}

	return false
}

func (this *RangeModule) RemoveRange(left int, right int) {
	updated := [][]int{}

	for _, interval := range this.intervals {
		start := interval[0]
		end := interval[1]

		if end <= left || start >= right {
			updated = append(updated, interval)
		} else {
			if start < left {
				updated = append(updated, []int{start, left})
			}

			if end > right {
				updated = append(updated, []int{right, end})
			}
		}
	}

	this.intervals = updated
}

The Go implementation follows the same logic as the Python version. Slices are used to store intervals dynamically.

Unlike Python lists, Go slices require explicit appending and manual handling of nested slices. Integer overflow is not an issue because the maximum coordinate is only 10^9, which fits comfortably inside Go's int.

The logic for merging, querying, and splitting intervals remains identical.

Worked Examples

Example 1

Input:

addRange(10, 20)
removeRange(14, 16)
queryRange(10, 14)
queryRange(13, 15)
queryRange(16, 17)

Step 1: addRange(10, 20)

Initial intervals:

[]

After insertion:

[(10, 20)]

Operation	Intervals
addRange(10, 20)	[(10, 20)]

Step 2: removeRange(14, 16)

Current intervals:

[(10, 20)]

The removal overlaps the middle.

Split into:

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

Operation	Intervals
removeRange(14, 16)	[(10, 14), (16, 20)]

Step 3: queryRange(10, 14)

We check whether one interval fully contains [10, 14).

Interval (10, 14) satisfies:

10 <= 10
14 >= 14

Result:

True

Step 4: queryRange(13, 15)

Current intervals:

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

No interval fully contains [13, 15) because coverage stops at 14.

Result:

False

Step 5: queryRange(16, 17)

Interval (16, 20) fully contains [16, 17).

Result:

True

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n) per operation	Each operation may scan all intervals
Space	O(n)	Stores disjoint intervals only

The number of intervals remains relatively small because overlapping intervals are merged aggressively. Even though each operation may scan the entire interval list, the constraint of at most 10^4 operations makes this approach efficient enough in practice.

Test Cases

# Provided example
rm = RangeModule()
rm.addRange(10, 20)
rm.removeRange(14, 16)

assert rm.queryRange(10, 14) is True   # left section remains
assert rm.queryRange(13, 15) is False  # removed middle section
assert rm.queryRange(16, 17) is True   # right section remains

# Simple add and query
rm = RangeModule()
rm.addRange(1, 5)

assert rm.queryRange(1, 5) is True     # exact match
assert rm.queryRange(2, 4) is True     # subrange
assert rm.queryRange(0, 5) is False    # partially uncovered

# Adjacent intervals should merge
rm = RangeModule()
rm.addRange(1, 5)
rm.addRange(5, 10)

assert rm.queryRange(1, 10) is True    # merged adjacency

# Overlapping intervals
rm = RangeModule()
rm.addRange(1, 5)
rm.addRange(3, 8)

assert rm.queryRange(1, 8) is True     # overlap merged

# Remove middle portion
rm = RangeModule()
rm.addRange(1, 10)
rm.removeRange(4, 6)

assert rm.queryRange(1, 4) is True     # left remains
assert rm.queryRange(6, 10) is True    # right remains
assert rm.queryRange(4, 6) is False    # removed section

# Remove entire interval
rm = RangeModule()
rm.addRange(1, 10)
rm.removeRange(1, 10)

assert rm.queryRange(1, 10) is False   # everything removed

# Multiple merges
rm = RangeModule()
rm.addRange(1, 3)
rm.addRange(6, 9)
rm.addRange(2, 7)

assert rm.queryRange(1, 9) is True     # all merged together

# Large coordinates
rm = RangeModule()
rm.addRange(1, 10**9)

assert rm.queryRange(500, 999999999) is True  # huge interval

# Remove from edge
rm = RangeModule()
rm.addRange(10, 20)
rm.removeRange(10, 15)

assert rm.queryRange(10, 15) is False  # left edge removed
assert rm.queryRange(15, 20) is True   # right remains

# Non-overlapping remove
rm = RangeModule()
rm.addRange(10, 20)
rm.removeRange(30, 40)

assert rm.queryRange(10, 20) is True   # unchanged

Test	Why
Provided example	Validates core functionality
Exact range query	Confirms direct containment
Partial uncovered query	Ensures incomplete coverage fails
Adjacent merge	Tests half-open interval merging
Overlapping add	Verifies interval union logic
Middle removal	Tests interval splitting
Full removal	Ensures intervals disappear correctly
Multiple merges	Validates repeated overlap handling
Large coordinates	Confirms sparse storage works
Edge removal	Tests trimming logic
Non-overlapping remove	Ensures unrelated ranges stay intact

Edge Cases

Removing a Range That Splits an Interval

A particularly tricky case occurs when a removal range lies completely inside an existing interval.

Example:

Tracked: [1, 10)
Remove:  [4, 6)

A buggy implementation may accidentally delete the entire interval or keep overlapping portions. The correct result is:

[1, 4)
[6, 10)

The implementation handles this by separately preserving the left and right non-overlapping segments.

Adjacent Intervals

Because intervals are half-open, [1, 5) and [5, 10) together represent continuous coverage.

A common mistake is failing to merge adjacent intervals. That can break queries like:

queryRange(1, 10)

even though the entire region is covered.

The implementation merges intervals whenever:

interval_start <= right

which correctly combines touching intervals.

Queries Across Gaps

Suppose we have:

[1, 5)
[7, 10)

Then:

queryRange(1, 10)

must return false.

A buggy implementation might incorrectly combine multiple intervals conceptually. However, the query must verify continuous coverage by a single merged interval.

Because the structure always maintains maximally merged intervals, any gap automatically causes the query to fail.