Range Module (Add/Remove/Query Ranges)

📋

Range Module (Add/Remove/Query Ranges)

Edge cases:

</>

IDE

class RangeModule: def __init__(self): pass def addRange(self, left: int, right: int) -> None: pass def queryRange(self, left: int, right: int) -> bool: pass def removeRange(self, left: int, right: int) -> None: passpublic class RangeModule { public RangeModule() {} public void addRange(int left, int right) {} public boolean queryRange(int left, int right) { return false; } public void removeRange(int left, int right) {} }class RangeModule { public: RangeModule() {} void addRange(int left, int right) {} bool queryRange(int left, int right) { return false; } void removeRange(int left, int right) {} };class RangeModule { constructor() {} addRange(left, right) {} queryRange(left, right) { return false; } removeRange(left, right) {} }

class RangeModule:
    def __init__(self):
        # Write your solution here
        pass
    def addRange(self, left: int, right: int) -> None:
        pass
    def queryRange(self, left: int, right: int) -> bool:
        pass
    def removeRange(self, left: int, right: int) -> None:
        pass

class RangeModule {
    public RangeModule() {
        // Write your solution here
    }
    public void addRange(int left, int right) {
    }
    public boolean queryRange(int left, int right) {
        return false;
    }
    public void removeRange(int left, int right) {
    }
}

#include <vector>
using namespace std;

class RangeModule {
public:
    RangeModule() {
        // Write your solution here
    }
    void addRange(int left, int right) {
    }
    bool queryRange(int left, int right) {
        return false;
    }
    void removeRange(int left, int right) {
    }
};

class RangeModule {
    constructor() {
        // Write your solution here
    }
    addRange(left, right) {
    }
    queryRange(left, right) {
        return false;
    }
    removeRange(left, right) {
    }
}

Common Bugs to Avoid

Wrong: queryRange returns false for a range fully covered by merged intervalsIntervals are not merged correctly on addRange, leaving gaps between intervals.✅ Merge intervals by expanding boundaries when overlapping or adjacent: dp[i][w] = max(dp[i-1][w], val[i-1] + dp[i-1][w-wt[i-1]])

Wrong: queryRange returns true for a range partially removedremoveRange does not split intervals properly, leaving removed parts still tracked.✅ Split intervals at removal boundaries and remove only overlapping parts.

Wrong: queryRange returns true when no intervals existEmpty intervals list not handled; queryRange returns true by default or errors.✅ Return false if intervals list is empty or no interval covers the query range.

Wrong: TLE on large inputsLinear scan of intervals for each operation causing O(n) per call.✅ Use balanced tree or binary search to achieve O(log n) per operation.

✓

Test Cases

Focus on handling empty and minimal intervals correctly before moving on.

Ensure your merging and splitting logic is robust for overlapping and adjacent intervals.

Optimize your data structure to avoid linear scans for large inputs.

t1_01basic

Input["addRange(10, 20)","removeRange(14, 16)","queryRange(10, 14)","queryRange(13, 15)","queryRange(16, 17)"]

Expected["null","null","true","false","true"]

⏱ Performance - must finish in 2000ms

After adding [10,20), removing [14,16) splits the range into [10,14) and [16,20). Querying [10,14) returns true, [13,15) returns false because 14-15 is removed, and [16,17) returns true.

💡 Think about how intervals merge or split when adding or removing ranges.

💡 Use binary search or a balanced tree to efficiently find overlapping intervals.

💡 When removing, split existing intervals if partially overlapped; when adding, merge overlapping intervals.

Why it failed: Basic case failed - likely incorrect merging or splitting of intervals during addRange or removeRange. Fix by carefully updating intervals to merge overlapping ones on add and split on remove.

✓ Core interval merging and splitting logic is correct.

t1_02basic

Input["addRange(5, 10)","addRange(15, 20)","removeRange(7, 17)","queryRange(5, 7)","queryRange(10, 15)","queryRange(17, 20)"]

Expected["null","null","null","true","false","true"]

⏱ Performance - must finish in 2000ms

After adding [5,10) and [15,20), removing [7,17) removes [7,10) and [15,17). Querying [5,7) returns true, [10,15) returns false (gap), and [17,20) returns true.

💡 Consider how removeRange affects multiple intervals that partially overlap.

💡 Check that intervals are split correctly when removal overlaps partially.

💡 Ensure queryRange returns false if any part of the queried range is missing.

Why it failed: Failed to split intervals correctly on removeRange causing incorrect query results. Fix by splitting intervals at removal boundaries properly.

✓ Intervals split and queries handled correctly.

t2_01edge

Input["queryRange(0, 1)"]

Expected["false"]

⏱ Performance - must finish in 2000ms

No ranges added; querying any range should return false.

💡 What happens if no ranges are added and queryRange is called?

💡 Check that queryRange returns false if no intervals exist.

💡 Initialize your data structure to handle empty state gracefully.

Why it failed: Empty input test failed - likely queryRange returns true or errors when no intervals exist. Fix by returning false if intervals list is empty.

✓ Handles empty input and queries correctly.

t2_02edge

Input["addRange(5, 6)","queryRange(5, 6)","removeRange(5, 6)","queryRange(5, 6)"]

Expected["null","true","null","false"]

⏱ Performance - must finish in 2000ms

Single element range added and removed; queries reflect correct presence and absence.

💡 Test behavior with smallest possible intervals (single element).

💡 Ensure addRange and removeRange handle intervals of length 1 correctly.

💡 Check that queryRange returns true only if entire interval is tracked.

Why it failed: Single element range test failed - likely off-by-one errors in interval boundaries. Fix by using half-open intervals consistently.

✓ Single element intervals handled correctly.

t2_03edge

Input["addRange(0, 10)","queryRange(0, 10)","removeRange(0, 10)","queryRange(0, 10)"]

Expected["null","true","null","false"]

⏱ Performance - must finish in 2000ms

Querying exact boundary intervals returns true before removal and false after removal.

💡 Test querying intervals that exactly match existing intervals.

💡 Check that addRange merges intervals correctly at boundaries.

💡 Ensure removeRange removes entire intervals when boundaries match.

Why it failed: Exact boundary test failed - intervals not merged or removed correctly at boundaries. Fix by careful boundary checks in addRange and removeRange.

✓ Exact boundary intervals handled correctly.

t2_04edge

Input["addRange(10, 20)","addRange(12, 18)","queryRange(10, 20)"]

Expected["null","null","true"]

⏱ Performance - must finish in 2000ms

Adding a range completely inside an existing range should not change intervals; queryRange returns true.

💡 Check that adding a range inside an existing interval does not create duplicates.

💡 Avoid adding redundant intervals.

💡 Merge intervals properly to maintain minimal representation.

Why it failed: Failed to handle adding range inside existing interval causing duplicates or gaps. Fix by merging intervals and ignoring redundant adds.

✓ Nested addRange handled correctly.

t3_01corner

Input["addRange(1, 5)","addRange(2, 6)","queryRange(1, 6)"]

Expected["null","null","true"]

⏱ Performance - must finish in 2000ms

Overlapping addRange calls should merge intervals correctly so queryRange returns true.

💡 Check how overlapping intervals are merged on addRange.

💡 Avoid just appending intervals without merging.

💡 Merge intervals by expanding boundaries to cover overlaps.

Why it failed: Failed to merge overlapping intervals on addRange causing queryRange to return false. Fix by merging overlapping intervals properly.

✓ Overlapping intervals merged correctly.

t3_02corner

Input["addRange(1, 3)","addRange(5, 7)","removeRange(2, 6)","queryRange(1, 2)","queryRange(3, 5)","queryRange(6, 7)"]

Expected["null","null","null","true","false","true"]

⏱ Performance - must finish in 2000ms

Removing a range that partially overlaps multiple intervals splits them correctly.

💡 Check that removeRange splits intervals when partially overlapping multiple intervals.

💡 Avoid removing entire intervals if only partially overlapped.

💡 Split intervals at removal boundaries and keep unaffected parts.

Why it failed: Incorrect removal splitting causing queryRange to return wrong results. Fix by splitting intervals correctly on partial overlap removal.

✓ Partial overlap removal handled correctly.

t3_03corner

Input["addRange(1, 4)","addRange(4, 7)","queryRange(1, 7)"]

Expected["null","null","true"]

⏱ Performance - must finish in 2000ms

Adjacent intervals should merge so queryRange returns true for combined range.

💡 Check if adjacent intervals are merged or treated separately.

💡 Avoid treating adjacent intervals as disjoint.

💡 Merge intervals if end of one equals start of next.

Why it failed: Failed to merge adjacent intervals causing queryRange to return false. Fix by merging intervals where end == start.

✓ Adjacent intervals merged correctly.

t4_01performance

Input{"calls":[{"method":"addRange","args":[0,1000000000]},{"method":"removeRange","args":[1,999999999]},{"method":"queryRange","args":[0,1]},{"method":"queryRange","args":[999999999,1000000000]},{"method":"queryRange","args":[1,999999999]}]}

Expectednull

⏱ Performance - must finish in 2000ms

Large range add and remove operations with queries test O(log n) complexity; n=5 calls but with large intervals to test performance of interval merging and splitting.

💡 Use balanced tree or binary search to achieve O(log n) per operation.

💡 Avoid scanning all intervals linearly for each operation.

💡 Implement interval merging and splitting efficiently with binary search.

Why it failed: TLE due to O(n) linear scans per operation. Fix by using balanced tree or binary search to achieve O(log n) complexity.

✓ Efficient O(log n) complexity confirmed.

Practice

1. Consider the following code snippet implementing the optimal approach to copy a list with random pointers. Given the input list:
Node1(val=1) -> Node2(val=2) -> Node3(val=3), where Node1.random = Node3, Node2.random = Node1, Node3.random = null.
After Step 2 (assigning random pointers), what is the value of copy_curr.random.val when copy_curr points to the copied node of Node2?

easy

A. None (null)

B. 3

C. 1

D. 2

Solution

1. Step 1: Trace Step 1 (interleaving nodes)

   Original list: 1 -> 2 -> 3 becomes 1 -> 1' -> 2 -> 2' -> 3 -> 3'.

2. Step 2: Trace Step 2 (assign random pointers)

   Node2.random = Node1, so copied Node2 (2') random = Node1.next = 1'. Thus, copy_curr.random.val = 1.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   copy_curr.random points to copied Node1 with val=1 [OK]

Hint: Copied node's random points to original.random.next [OK]

Common Mistakes:

• Confusing original and copied nodes when assigning random pointers
• Off-by-one errors in stepping through interleaved list
• Assuming random pointer points to original node's val

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

3. Examine the following buggy code snippet from the AllOne data structure. Which line contains the subtle bug that causes keys to remain in multiple buckets after incrementing, leading to incorrect max/min results?

def inc(self, key: str) -> None:
    if key not in self.key_to_bucket:
        if 1 not in self.count_to_bucket:
            new_bucket = Bucket(1)
            self._insert_bucket_after(new_bucket, self.head)
        self.count_to_bucket[1].keys.add(key)
        self.key_to_bucket[key] = self.count_to_bucket[1]
    else:
        curr_bucket = self.key_to_bucket[key]
        next_count = curr_bucket.count + 1
        if next_count not in self.count_to_bucket:
            new_bucket = Bucket(next_count)
            self._insert_bucket_after(new_bucket, curr_bucket)
        self.count_to_bucket[next_count].keys.add(key)
        self.key_to_bucket[key] = self.count_to_bucket[next_count]
        # BUG: Missing removal of key from old bucket
        # curr_bucket.keys.remove(key)
        if len(curr_bucket.keys) == 0:
            self._remove_bucket(curr_bucket)

medium

A. Line removing key from old bucket's keys set (commented out)

B. Line updating key_to_bucket mapping

C. Line removing empty bucket if keys set is empty

D. Line adding key to new bucket's keys set

Solution

1. Step 1: Identify key movement between buckets

   When incrementing, key must be removed from old bucket's keys set.

2. Step 2: Locate missing removal

   The commented out line that removes the key from old bucket is missing, causing key to appear in multiple buckets.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Without removal, max/min queries become incorrect due to duplicate keys [OK]

Hint: Key must be removed from old bucket after increment [OK]

Common Mistakes:

• Forgetting to remove key from old bucket after increment/decrement

4. Consider the following buggy code snippet for flattening a multilevel doubly linked list. Which line contains the subtle bug that can cause infinite loops or incorrect list structure?

medium

A. Missing line that sets curr.child to None after splicing

B. Line where tail is found by while tail.next:

C. Line where curr.next is set to child

D. Line where tail.next is connected to curr.next

Solution

1. Step 1: Identify the role of curr.child

   After splicing the child list, curr.child must be set to None to avoid revisiting the child.

2. Step 2: Recognize missing pointer update

   The code does not set curr.child = None, causing infinite loops or incorrect traversal.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Not clearing child pointer leads to repeated processing [OK]

Hint: Always clear child pointer after splicing [OK]

Common Mistakes:

• Forgetting to clear child pointer after splicing
• Incorrectly updating prev pointers instead

5. Examine the following buggy remove method from the optimized Insert Delete GetRandom O(1) with duplicates data structure. Which line contains the subtle bug that can cause incorrect behavior or runtime errors?

def remove(self, val: int) -> bool:
    if val not in self.idx_map or not self.idx_map[val]:
        return false
    remove_idx = self.idx_map[val].pop()
    last_val = self.nums[-1]
    self.nums[remove_idx] = last_val
    self.idx_map[last_val].add(remove_idx)
    # BUG: missing discard of old index for last_val
    self.nums.pop()
    if not self.idx_map[val]:
        del self.idx_map[val]
    return true

medium

A. Missing line to discard old index of last_val from idx_map[last_val]

B. Line adding remove_idx to idx_map[last_val] (self.idx_map[last_val].add(remove_idx))

C. Line popping remove_idx from idx_map[val] (remove_idx = self.idx_map[val].pop())

D. Line removing the last element from nums (self.nums.pop())

Solution

1. Step 1: Understand index updates during removal

   When swapping last_val into remove_idx, we must update idx_map[last_val] by adding remove_idx and discarding the old index (len(nums)-1).

2. Step 2: Identify missing discard

   The code adds remove_idx to idx_map[last_val] but does not discard the old index, causing stale indices and incorrect removals later.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing discard leads to incorrect index tracking [OK]

Hint: Always discard old indices after swapping during removal [OK]

Common Mistakes:

• Forgetting to discard old index after swap
• Removing wrong element from idx_map
• Incorrect pop from idx_map[val]