Data Stream as Disjoint Intervals

▶

Steps

setup

Initialize SummaryRanges with empty intervals

Create an empty list to store intervals. No intervals exist yet.

💡 Starting with an empty structure is essential to build intervals incrementally.

Line:

self.intervals = []

💡 Intervals start empty and will grow as numbers are added.

insert

Add number 1 to empty intervals

Since intervals are empty, add [1,1] as the first interval.

💡 Adding the first number creates the first interval.

Line:

if not intervals:
    intervals.append([val, val])
    return

💡 The first number always creates a new interval.

compare

Add number 3, find insertion index

Use binary search to find where to insert [3,3]. The insertion index is 1 (after [1,1]).

💡 Binary search finds the correct position to keep intervals sorted.

Line:

i = bisect_left(intervals, [val, val])

💡 Intervals remain sorted by start value after insertion.

compare

Check coverage and merge conditions for val=3

Check if 3 is covered by intervals[i-1] or intervals[i]. It is not covered. Check if adjacent to left or right intervals.

💡 Avoid duplicates and find if merging is needed.

Line:

if i != 0 and intervals[i-1][0] <= val <= intervals[i-1][1]:
    return
if i != len(intervals) and intervals[i][0] <= val <= intervals[i][1]:
    return
left_merge = (i > 0 and intervals[i-1][1] + 1 == val)
right_merge = (i < len(intervals) and intervals[i][0] - 1 == val)

💡 3 is a new isolated interval.

insert

Insert new interval [3,3]

Insert [3,3] at index 1 since no merges apply.

💡 New isolated interval is added to keep intervals disjoint and sorted.

Line:

intervals.insert(i, [val, val])

💡 Intervals now contain two disjoint intervals.

compare

Add number 7, find insertion index

Binary search finds insertion index 2 for [7,7] after existing intervals.

💡 Locate correct position to maintain sorted intervals.

Line:

i = bisect_left(intervals, [val, val])

💡 7 is beyond all current intervals.

compare

Check coverage and merge conditions for val=7

7 is not covered by any interval and not adjacent to any interval.

💡 Confirm no merges or coverage before insertion.

Line:

if i != 0 and intervals[i-1][0] <= val <= intervals[i-1][1]:
    return
if i != len(intervals) and intervals[i][0] <= val <= intervals[i][1]:
    return
left_merge = (i > 0 and intervals[i-1][1] + 1 == val)
right_merge = (i < len(intervals) and intervals[i][0] - 1 == val)

💡 7 is a new isolated interval.

insert

Insert new interval [7,7]

Insert [7,7] at index 2 as a new isolated interval.

💡 Add new interval to maintain sorted disjoint intervals.

Line:

intervals.insert(i, [val, val])

💡 Intervals now have three disjoint intervals.

compare

Add number 2, find insertion index

Binary search finds insertion index 1 for [2,2] between [1,1] and [3,3].

💡 Locate position to insert or merge 2.

Line:

i = bisect_left(intervals, [val, val])

💡 2 lies between two existing intervals.

compare

Check coverage and merge conditions for val=2

2 is not covered but is adjacent to both left [1,1] and right [3,3] intervals.

💡 Detect that 2 bridges two intervals and should merge them.

Line:

left_merge = (i > 0 and intervals[i-1][1] + 1 == val)
right_merge = (i < len(intervals) and intervals[i][0] - 1 == val)

💡 2 connects intervals [1,1] and [3,3], so merge is needed.

insert

Merge intervals [1,1] and [3,3] into [1,3]

Extend left interval's end to right interval's end and remove right interval.

💡 Merging reduces intervals and keeps them disjoint.

Line:

intervals[i-1][1] = intervals[i][1]
intervals.pop(i)

💡 Intervals now reflect the merged range covering 1 to 3.

compare

Add number 6, find insertion index

Binary search finds insertion index 1 for [6,6] between [1,3] and [7,7].

💡 Locate position to insert or merge 6.

Line:

i = bisect_left(intervals, [val, val])

💡 6 lies just before the last interval.

compare

Check coverage and merge conditions for val=6

6 is not covered but adjacent to right interval [7,7].

💡 Detect that 6 should merge with the right interval.

Line:

left_merge = (i > 0 and intervals[i-1][1] + 1 == val)
right_merge = (i < len(intervals) and intervals[i][0] - 1 == val)

💡 6 extends the start of the right interval.

insert

Merge val=6 with right interval [7,7]

Update right interval start from 7 to 6, merging 6 and 7.

💡 Extending interval start merges the new number.

Line:

intervals[i][0] = val

💡 Intervals now reflect merged interval [6,7].

reconstruct

Get intervals after all insertions

Return the current list of intervals as the answer.

💡 The intervals represent the disjoint ranges covering all added numbers.

Line:

return self.intervals

💡 Final intervals reflect all merges and insertions.

from bisect import bisect_left

class SummaryRanges:
    def __init__(self):
        self.intervals = []  # STEP 1

    def addNum(self, val: int) -> None:
        intervals = self.intervals
        if not intervals:
            intervals.append([val, val])  # STEP 2
            return
        i = bisect_left(intervals, [val, val])  # STEP 3,6,9,12

        # Check if val is already covered
        if i != 0 and intervals[i-1][0] <= val <= intervals[i-1][1]:  # STEP 4,7,10,13
            return
        if i != len(intervals) and intervals[i][0] <= val <= intervals[i][1]:
            return

        left_merge = (i > 0 and intervals[i-1][1] + 1 == val)  # STEP 4,7,10,13
        right_merge = (i < len(intervals) and intervals[i][0] - 1 == val)

        if left_merge and right_merge:
            intervals[i-1][1] = intervals[i][1]  # STEP 11
            intervals.pop(i)
        elif left_merge:
            intervals[i-1][1] = val  # Not used in this trace
        elif right_merge:
            intervals[i][0] = val  # STEP 14
        else:
            intervals.insert(i, [val, val])  # STEP 5,8

    def getIntervals(self) -> list:
        return self.intervals  # STEP 15

📊

Data Stream as Disjoint Intervals - Watch the Algorithm Execute, Step by Step

Watching each insertion and merge step-by-step reveals how the algorithm maintains disjoint intervals efficiently.

setup

Result: []

insert

0

Result: [[1,1]]

compare

0

Result: [[1,1]]

compare

left

0

Result: [[1,1]]

insert

0

i

1

Result: [[1,1],[3,3]]

compare

0

1

Result: [[1,1],[3,3]]

compare

0

left

1

Result: [[1,1],[3,3]]

insert

0

1

i

2

Result: [[1,1],[3,3],[7,7]]

compare

0

i

1

2

Result: [[1,1],[3,3],[7,7]]

compare

left

0

right

1

2

Result: [[1,1],[3,3],[7,7]]

insert

0

i

1

Result: [[1,3],[7,7]]

compare

0

i

1

Result: [[1,3],[7,7]]

compare

left

0

right

1

Result: [[1,3],[7,7]]

insert

0

i

1

Result: [[1,3],[6,7]]

record

0

1

Result: [[1,3],[6,7]]

Key Takeaways

✓ The algorithm maintains a sorted list of disjoint intervals and uses binary search to efficiently find insertion points.

This is hard to see from code alone because the binary search and interval checks are subtle and intertwined.

✓ Merging happens only when the new number bridges two intervals or is adjacent to one, reducing the number of intervals.

Visualizing merges clarifies how intervals grow and shrink dynamically.

✓ Coverage checks prevent duplicate intervals and unnecessary insertions, ensuring correctness.

Without seeing these checks step-by-step, it's easy to miss why some insertions are skipped.

Practice

1. You are given a list of meeting time intervals consisting of start and end times. Your task is to find the minimum number of conference rooms required so that all meetings can be held without overlap. Which of the following approaches guarantees an optimal solution with efficient time complexity?

easy

A. Sort intervals by start time and use a min-heap to track the earliest ending meeting to reuse rooms efficiently.

B. Use a brute force approach checking every pair of intervals for overlap and counting maximum overlaps.

C. Use dynamic programming to find the maximum number of non-overlapping intervals and subtract from total intervals.

D. Sort intervals by end time and greedily assign rooms without tracking ongoing meetings.

Solution

1. Step 1: Understand the problem requires tracking overlapping intervals to find minimum rooms.

   Brute force checks all pairs but is inefficient; greedy by end time alone doesn't track concurrent overlaps.

2. Step 2: Recognize that sorting by start time and using a min-heap to track earliest ending meeting allows reusing rooms optimally.

   This approach efficiently manages room allocation by freeing rooms as meetings end.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Min-heap approach is standard optimal solution for this problem [OK]

Hint: Min-heap tracks earliest end to reuse rooms efficiently [OK]

Common Mistakes:

• Assuming greedy by end time alone suffices
• Thinking brute force is efficient enough
• Confusing DP for interval scheduling with room allocation

2. What is the time complexity of the optimal approach that inserts a new interval into a list of n intervals and merges overlapping intervals, where the approach is to append the new interval, sort all intervals by start time, then merge in one pass?

medium

A. O(n)

B. O(n^2)

C. O(n log n)

D. O(log n)

Solution

1. Step 1: Identify sorting cost

   Appending is O(1), but sorting n+1 intervals takes O(n log n) time.

2. Step 2: Identify merging cost

   Merging intervals in one pass is O(n) since each interval is processed once.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Sorting dominates overall time complexity [OK]

Hint: Sorting dominates time complexity -> O(n log n) [OK]

Common Mistakes:

• Assuming linear time because merging is O(n)
• Confusing sorting cost with merging cost
• Thinking recursion stack adds extra complexity

3. Consider the following buggy code for inserting an interval. Which line contains the subtle bug that can cause incorrect output when the input list is empty?

from typing import List

def insert(intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
    intervals.append(newInterval)
    intervals.sort(key=lambda x: x[0])
    merged = [intervals[0]]
    for i in range(1, len(intervals)):
        if intervals[i][0] <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], intervals[i][1])
        else:
            merged.append(intervals[i])
    return merged

medium

A. Line 5: merged = [intervals[0]]

B. Line 3: intervals.append(newInterval)

C. Line 7: if intervals[i][0] <= merged[-1][1]:

D. Line 9: merged.append(intervals[i])

Solution

1. Step 1: Consider empty intervals input

   If intervals is empty, after appending newInterval, intervals has length 1.

2. Step 2: Check initialization of merged

   Line 5 accesses intervals[0] without checking if intervals is empty before append, which is safe here but if input was empty, intervals[0] is newInterval, so no crash.

3. Step 3: Identify subtle bug

   Actually, no crash here, but if input intervals was empty, sorting and merging still works. The subtle bug is that if intervals was empty and newInterval is appended, the code works, but if the initial intervals list is empty and the code did not append newInterval first, line 5 would crash. So the bug is that the code assumes intervals is non-empty before append, which is not always true.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Accessing intervals[0] without empty check is risky [OK]

Hint: Accessing intervals[0] without empty check causes bug [OK]

Common Mistakes:

• Not handling empty input intervals list
• Assuming intervals always non-empty before append
• Incorrect merging when intervals just touch

4. Examine the following buggy code for the Meeting Rooms II problem. Which line contains the subtle bug that can cause incorrect room count?

medium

A. Line 3: Missing check for empty intervals list.

B. Line 9: Incorrect condition using >= instead of > for overlap.

C. Line 11: Using heappush without popping first.

D. Line 6: Intervals are not sorted before processing.

Solution

1. Step 1: Identify missing sorting.

   Intervals must be sorted by start time before heap processing; missing this breaks heap logic.

2. Step 2: Confirm other lines.

   Empty check is present; condition >= is correct for allowing room reuse; pushing after popping is correct.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Without sorting, heap logic fails to track earliest ending meeting [OK]

Hint: Heap logic requires sorted intervals by start time [OK]

Common Mistakes:

• Confusing overlap condition with <=
• Forgetting to sort intervals
• Misordering heap push/pop

5. The following code attempts to find the minimum number of arrows to burst balloons. Identify the bug that causes incorrect arrow count in some cases.

medium

A. Line 6: Shooting arrow at start coordinate instead of end coordinate

B. Line 4: Sorting by end coordinate is incorrect

C. Line 2: Missing check for empty input

D. Line 8: Using start > arrow_pos instead of start >= arrow_pos

Solution

1. Step 1: Analyze arrow shooting position

   Arrow should be shot at the end coordinate of the first balloon to cover maximum overlaps.

2. Step 2: Identify impact of shooting at start

   Shooting at start may miss balloons overlapping at the end, causing extra arrows.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Correct arrow position is critical for minimal arrow count [OK]

Hint: Arrow must be at end coordinate, not start [OK]

Common Mistakes:

• Confusing start and end coordinates for arrow position
• Using >= instead of > causing overcount
• Ignoring empty input edge case