Range Module (Add/Remove/Query Ranges)

▶

Steps

setup

Initialize empty RangeModule

Create an empty RangeModule with no intervals and an empty starts list.

💡 Starting with an empty structure is essential to see how intervals are added and managed.

Line:

self.intervals = dict()
self.starts = []

💡 Intervals and starts are empty, so no coverage exists yet.

fill_row

Add range [10, 20) - Find insertion points

Find insertion indices i and j for left=10 and right=20 using bisect on starts list.

💡 Finding where to insert or merge intervals is the first step in addRange.

Line:

i = bisect_left(self.starts, left)
j = bisect_right(self.starts, right)

💡 No existing intervals overlap, so insertion will be at position 0.

fill_cells

Add range [10, 20) - No overlap adjustment

Since i=0, no previous interval overlaps left=10; right remains 20.

💡 Check if previous interval overlaps to adjust left boundary.

Line:

if i != 0 and self.intervals[self.starts[i-1]] >= left:
    i -= 1
    left = min(left, self.starts[i])

💡 No previous interval to merge with, so left boundary stays 10.

fill_cells

Add range [10, 20) - Adjust right boundary

Since j=0, no intervals end after right=20, so right remains 20.

💡 Adjust right boundary if overlapping intervals extend beyond right.

Line:

if j != 0:
    right = max(right, self.intervals[self.starts[j-1]])

💡 Right boundary remains unchanged as no overlapping intervals on right.

insert

Add range [10, 20) - Remove overlapping intervals and insert merged

Remove intervals in starts[i:j] (empty here), insert new interval [10,20) at position i=0.

💡 This step merges overlapping intervals and inserts the new merged interval.

Line:

for k in self.starts[i:j]:
    del self.intervals[k]
self.starts[i:j] = [left]
self.intervals[left] = right

💡 The intervals list now contains one interval [10,20).

fill_row

Remove range [14, 16) - Find removal indices

Find indices i and j for left=14 and right=16 in starts list [10].

💡 Locate intervals overlapping the removal range.

Line:

i = bisect_left(self.starts, left)
j = bisect_right(self.starts, right)

💡 Removal range overlaps with interval starting at 10.

prune

Remove range [14, 16) - Check left overlap for split

Check if interval before i overlaps left=14 to split it.

💡 Splitting intervals is necessary to remove a middle portion.

Line:

if i != 0 and self.intervals[self.starts[i-1]] > left:
    start = self.starts[i-1]
    end = self.intervals[start]
    if start < left:
        newIntervals.append((start, left))
    i -= 1

💡 Left part [10,14) remains after removal starts at 14.

prune

Remove range [14, 16) - Check right overlap for split

Check if interval before j overlaps right=16 to split it.

💡 Right split preserves interval after removal end.

Line:

if j != 0 and self.intervals[self.starts[j-1]] > right:
    start = right
    end = self.intervals[self.starts[j-1]]
    newIntervals.append((start, end))

💡 Right part [16,20) remains after removal ends at 16.

delete

Remove range [14, 16) - Remove overlapping intervals

Delete intervals in starts[i:j] which is [10], removing [10,20).

💡 Removing intervals overlapping removal range is necessary before reinserting splits.

Line:

for k in self.starts[i:j]:
    del self.intervals[k]
self.starts[i:j] = []

💡 The original interval is removed to be replaced by split intervals.

insert

Remove range [14, 16) - Insert split intervals

Insert new intervals [10,14) and [16,20) into starts and intervals.

💡 Reinserting split intervals preserves coverage outside removal range.

Line:

for start, end in newIntervals:
    self.starts.insert(i, start)
    self.intervals[start] = end
    i += 1

💡 Intervals now represent coverage excluding [14,16).

compare

Query range [10, 14) - Find floor interval

Find index i for left=10 using bisect_right and check interval coverage.

💡 Query checks if an interval fully covers the query range.

Line:

i = bisect_right(self.starts, left) - 1

💡 Floor interval found starting at 10.

compare

Query range [10, 14) - Check coverage

Check if interval [10,14) covers right=14 by comparing interval end.

💡 Coverage means interval end >= query right.

Line:

return self.intervals[self.starts[i]] >= right

💡 Query range is fully covered by interval [10,14).

compare

Query range [13, 15) - Find floor interval

Find index i for left=13 using bisect_right and check interval coverage.

💡 Find candidate interval that might cover query range.

Line:

i = bisect_right(self.starts, left) - 1

💡 Floor interval found starting at 10.

compare

Query range [13, 15) - Check coverage

Check if interval [10,14) covers right=15 by comparing interval end.

💡 Coverage means interval end >= query right.

Line:

return self.intervals[self.starts[i]] >= right

💡 Query range is not fully covered because [14,15) is missing.

compare

Query range [16, 17) - Find floor interval

Find index i for left=16 using bisect_right and check interval coverage.

💡 Find candidate interval that might cover query range.

Line:

i = bisect_right(self.starts, left) - 1

💡 Floor interval found starting at 16.

compare

Query range [16, 17) - Check coverage

Check if interval [16,20) covers right=17 by comparing interval end.

💡 Coverage means interval end >= query right.

Line:

return self.intervals[self.starts[i]] >= right

💡 Query range is fully covered by interval [16,20).

from bisect import bisect_left, bisect_right

class RangeModule:
    def __init__(self):
        self.intervals = dict()  # STEP 1
        self.starts = []        # STEP 1

    def addRange(self, left: int, right: int) -> None:
        i = bisect_left(self.starts, left)  # STEP 2
        j = bisect_right(self.starts, right)  # STEP 2

        if i != 0 and self.intervals[self.starts[i-1]] >= left:  # STEP 3
            i -= 1
            left = min(left, self.starts[i])
        if j != 0:  # STEP 4
            right = max(right, self.intervals[self.starts[j-1]])

        for k in self.starts[i:j]:  # STEP 5
            del self.intervals[k]
        self.starts[i:j] = [left]
        self.intervals[left] = right

    def queryRange(self, left: int, right: int) -> bool:
        i = bisect_right(self.starts, left) - 1  # STEP 11,13,15
        if i < 0:
            return False
        return self.intervals[self.starts[i]] >= right  # STEP 12,14,16

    def removeRange(self, left: int, right: int) -> None:
        i = bisect_left(self.starts, left)  # STEP 6
        j = bisect_right(self.starts, right)  # STEP 6

        newIntervals = []
        if i != 0 and self.intervals[self.starts[i-1]] > left:  # STEP 7
            start = self.starts[i-1]
            end = self.intervals[start]
            if start < left:
                newIntervals.append((start, left))
            i -= 1
        if j != 0 and self.intervals[self.starts[j-1]] > right:  # STEP 8
            start = right
            end = self.intervals[self.starts[j-1]]
            newIntervals.append((start, end))

        for k in self.starts[i:j]:  # STEP 9
            del self.intervals[k]
        self.starts[i:j] = []

        for start, end in newIntervals:  # STEP 10
            self.starts.insert(i, start)
            self.intervals[start] = end
            i += 1

📊

Range Module (Add/Remove/Query Ranges) - Watch the Algorithm Execute, Step by Step

Watching each pointer movement and interval update helps you understand how overlapping intervals are merged or split, which is hard to grasp from code alone.

setup

advance

compare

compare

insert

10

advance

10

prune

10

prune

10

detach

insert

10

→

16

compare

10

→

16

compare

10

→

16

Result: true

compare

10

→

16

compare

10

→

16

Result: false

compare

10

→

16

compare

10

→

16

Result: true

Key Takeaways

✓ Intervals are stored as a sorted list of start points with corresponding ends, enabling efficient merging and splitting.

This structure is hard to visualize from code alone but becomes clear when watching intervals merge and split step-by-step.

✓ Adding a range merges all overlapping intervals into one, simplifying coverage representation.

Seeing how bisect finds indices and how intervals are removed and replaced clarifies the merging process.

✓ Removing a range can split existing intervals into two, preserving coverage outside the removed range.

The split and reinsert steps are subtle in code but become obvious when watching the intervals being pruned and reinserted.

Practice

1. Consider the following Python code snippet for the MedianFinder class using two heaps. After adding the numbers 1, 5, and 3 in that order, what is the value of the median returned by findMedian()?

easy

A. 1.0

B. 3.0

C. 5.0

D. 2.0

Solution

1. Step 1: Insert 1

   Low heap empty, push -1 to low; low_size=1, high_size=0.

2. Step 2: Insert 5

   5 > -low[0] (which is 1), push 5 to high; low_size=1, high_size=1; heaps balanced.

3. Step 3: Insert 3

   3 <= 5 but > 1, push 3 to high; high_size=2, low_size=1; balance heaps by moving smallest from high (3) to low (-3); low_size=2, high_size=1.

4. Step 4: Find median

   low_size > high_size, median is -low[0] = 3.0.

5. Step 5: Re-examine median calculation

   After balancing, low heap has [-3, -1], high heap has [5]. Median is top of low heap = 3.0, but the question asks for median after adding 1,5,3 in order, so median is 3.0.

6. Final Answer:

   Option B -> Option B

7. Quick Check:

   Median after [1,5,3] is 3.0 [OK]

Hint: Median is top of larger heap after balancing [OK]

Common Mistakes:

• Forgetting to balance heaps after insertion
• Returning wrong heap top for median

2. What is the time complexity of the get and put operations in an optimal LRU Cache implementation using a hash map and a doubly linked list with capacity n?

medium

A. O(n) for get and put due to list traversal

B. O(1) amortized for get and put using hash map and doubly linked list

C. O(log n) due to balancing the linked list

D. O(1) for get but O(n) for put due to eviction

Solution

1. Step 1: Analyze get operation

   Hash map provides O(1) access to node; doubly linked list allows O(1) removal and insertion to update usage order.

2. Step 2: Analyze put operation

   Insertion involves hash map update and linked list insertion/removal, all O(1). Eviction removes tail node in O(1).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Both get and put run in constant time using combined data structures [OK]

Hint: Hash map + doubly linked list -> O(1) get and put [OK]

Common Mistakes:

• Assuming list removal is O(n)
• Confusing amortized with worst-case
• Thinking linked list needs balancing

3. Suppose the linked list with random pointers can contain cycles formed by random pointers (i.e., random pointers may create cycles independent of next pointers). Which approach correctly copies such a list without infinite loops or duplicate nodes?

hard

A. Use the optimal weaving approach as is, since it handles all cases in O(1) space.

B. Use a recursive approach with memoization to track already copied nodes and avoid infinite recursion.

C. Use the brute force approach but skip assigning random pointers to avoid cycles.

D. Modify the optimal approach to break cycles by removing random pointers before copying.

Solution

1. Step 1: Understand cycle implications

   Random pointer cycles cause infinite loops if naive traversal is used without tracking visited nodes.

2. Step 2: Identify safe approach

   Recursive copying with memoization tracks visited nodes, preventing infinite recursion and duplicate copies.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Memoization ensures each node is copied once even with cycles [OK]

Hint: Memoization prevents infinite recursion in cyclic graphs [OK]

Common Mistakes:

• Assuming weaving approach handles cycles safely
• Ignoring cycles and causing infinite loops
• Removing random pointers loses information

4. Suppose the stack is modified to allow reusing popped elements by pushing them back later, and the increment operation must still work correctly. Which modification to the optimal lazy increment approach is necessary to maintain correctness?

hard

A. Store increments per element rather than per index, requiring a more complex data structure.

B. Reset the entire increments array to zero on each push to avoid stale increments.

C. Track increments with a stack of (index, increment) pairs and apply them on pop accordingly.

D. No change needed; the existing lazy increment array works correctly with reused elements.

Solution

1. Step 1: Understand reuse impact

   Reusing popped elements means the same stack positions may hold different elements over time, so increments per index become invalid.

2. Step 2: Modify increment tracking

   To maintain correctness, increments must be tracked per element, not per index, requiring a data structure that associates increments with elements themselves.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Per-element increments prevent stale increment application on reused positions [OK]

Hint: Reusing elements breaks index-based increments; track per element [OK]

Common Mistakes:

• Assuming no change needed
• Resetting increments array loses valid increments

5. Suppose the Twitter design is extended so that users can post the same tweet multiple times (tweet reuse allowed). Which modification to the optimal approach is necessary to correctly handle this scenario?

hard

A. Allow multiple TweetNode instances with the same tweetId but different timestamps in the linked list and heap.

B. Use a hash set to track unique tweetIds per user to avoid duplicates in the feed.

C. Modify the heap to store tweetIds only once, ignoring repeated posts of the same tweetId.

D. Disallow posting duplicate tweetIds by rejecting posts with existing tweetIds.

Solution

1. Step 1: Understand tweet reuse impact

   Allowing duplicate tweetIds means multiple posts with same id but different times must be treated as distinct tweets.

2. Step 2: Adjust data structures

   Each post creates a new TweetNode with unique timestamp; heap and linked lists handle duplicates naturally by time ordering.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Multiple nodes with same tweetId but different times must be stored separately [OK]

Hint: Treat each post as unique by timestamp, even if tweetId repeats [OK]

Common Mistakes:

• Trying to deduplicate tweets in feed incorrectly
• Rejecting duplicate posts unnecessarily