Data Stream as Disjoint Intervals

📋

Data Stream as Disjoint Intervals

Edge cases:

</>

IDE

def addNum(self, val: int) -> None: def getIntervals(self) -> list:public void addNum(int val) public int[][] getIntervals()void addNum(int val) vector<vector<int>> getIntervals()function addNum(val) function getIntervals()

class SummaryRanges:
    def __init__(self):
        # Write your solution here
        pass
    def addNum(self, val: int) -> None:
        pass
    def getIntervals(self) -> list:
        pass

class SummaryRanges {
    public SummaryRanges() {
        // Write your solution here
    }
    public void addNum(int val) {
        // Write your solution here
    }
    public int[][] getIntervals() {
        // Write your solution here
        return new int[0][0];
    }
}

#include <vector>
using namespace std;

class SummaryRanges {
public:
    SummaryRanges() {
        // Write your solution here
    }
    void addNum(int val) {
        // Write your solution here
    }
    vector<vector<int>> getIntervals() {
        // Write your solution here
        return {};
    }
};

class SummaryRanges {
    constructor() {
        // Write your solution here
    }
    addNum(val) {
        // Write your solution here
    }
    getIntervals() {
        // Write your solution here
        return [];
    }
}

Common Bugs to Avoid

Wrong: [[1,3],[7,7]] instead of [[1,7]]Failed to merge intervals connected by multiple adjacent numbers.✅ Merge all intervals overlapping or adjacent to val, not just one side.

Wrong: [[1,1],[3,3],[7,7]] after adding 2Missing merge of intervals when new val bridges two intervals.✅ Check intervals before and after val and merge if val connects them.

Wrong: Intervals change after adding duplicatesNot checking for duplicates before adding val.✅ Skip adding val if it already exists in intervals.

Wrong: Intervals merged incorrectly including non-adjacent intervalsGreedy merging all intervals instead of only adjacent ones.✅ Merge only intervals adjacent to val, not all intervals.

Wrong: TLE on large inputUsing brute force or sorting all numbers on each getIntervals call.✅ Use balanced tree or sorted container with incremental merging on insert.

✓

Test Cases

Focus on base cases like empty input and single element intervals.

Test your code against tricky merges and duplicate insertions.

Optimize your data structure for large input sizes and fast queries.

t1_01basic

Input{"calls":[{"method":"addNum","args":[1]},{"method":"getIntervals","args":[]},{"method":"addNum","args":[3]},{"method":"getIntervals","args":[]},{"method":"addNum","args":[7]},{"method":"getIntervals","args":[]},{"method":"addNum","args":[2]},{"method":"getIntervals","args":[]},{"method":"addNum","args":[6]},{"method":"getIntervals","args":[]}]}

Expected[[[1,1]],[[1,1],[3,3]],[[1,1],[3,3],[7,7]],[[1,3],[7,7]],[[1,3],[6,7]]]

⏱ Performance - must finish in 2000ms

After adding 1, intervals are [[1,1]]. Adding 3 adds a new interval [[3,3]]. Adding 7 adds [[7,7]]. Adding 2 merges [1,1] and [3,3] into [1,3]. Adding 6 merges [6,6] and [7,7] into [6,7].

💡 Think about how to merge intervals when a new number connects or extends existing intervals.

💡 Use a sorted data structure to quickly find intervals adjacent to the new number.

💡 Check neighbors and merge intervals if the new number bridges gaps or extends intervals.

Why it failed: Basic case failed - likely missing merging logic when new number connects two intervals. Fix by checking intervals before and after val and merging accordingly.

✓ Core merging and interval maintenance logic is correct.

t1_02basic

Input{"calls":[{"method":"addNum","args":[5]},{"method":"getIntervals","args":[]},{"method":"addNum","args":[10]},{"method":"getIntervals","args":[]},{"method":"addNum","args":[6]},{"method":"getIntervals","args":[]},{"method":"addNum","args":[8]},{"method":"getIntervals","args":[]},{"method":"addNum","args":[7]},{"method":"getIntervals","args":[]}]}

Expected[[[5,5]],[[5,5],[10,10]],[[5,6],[10,10]],[[5,6],[8,8],[10,10]],[[5,10]]]

⏱ Performance - must finish in 2000ms

Add 5 → [[5,5]]. Add 10 → [[5,5],[10,10]]. Add 6 merges with 5 → [[5,6],[10,10]]. Add 8 → [[5,6],[8,8],[10,10]]. Add 7 merges [5,6],[8,8],[10,10] into [[5,10]].

💡 Consider how adding numbers that fill gaps between intervals causes merges.

💡 Check if new val is adjacent to one or more intervals and merge all connected intervals.

💡 Update intervals by merging all overlapping or adjacent intervals into one.

Why it failed: Failed to merge multiple intervals connected by new val. Fix by merging all intervals overlapping or adjacent to val, not just one side.

✓ Correctly merges multiple intervals connected by new number.

t2_01edge

Input{"calls":[{"method":"getIntervals","args":[]}]}

Expected[]

⏱ Performance - must finish in 2000ms

No numbers added, so intervals list is empty.

💡 What should getIntervals return if no numbers have been added?

💡 Check for empty internal data structures before processing intervals.

💡 Return an empty list if no numbers exist.

Why it failed: Returned non-empty intervals when no numbers added. Fix by returning empty list if no data present. This is the empty input test.

✓ Correctly returns empty intervals when no numbers added.

t2_02edge

Input{"calls":[{"method":"addNum","args":[100]},{"method":"getIntervals","args":[]}]}

Expected[[[100,100]]]

⏱ Performance - must finish in 2000ms

Single element added forms one interval [100,100].

💡 How does your code handle a single number insertion?

💡 Ensure intervals are created correctly for one element.

💡 Return [[val,val]] when only one number is added.

Why it failed: Failed to create interval for single element. Fix by initializing interval as [val,val] when adding first number. This is the single element test.

✓ Correctly handles single element interval creation.

t2_03edge

Input{"calls":[{"method":"addNum","args":[0]},{"method":"addNum","args":[1]},{"method":"addNum","args":[2]},{"method":"getIntervals","args":[]}]}

Expected[[[0,2]]]

⏱ Performance - must finish in 2000ms

Adding numbers 0,1,2 creates a continuous interval [0,2].

💡 Check if your code merges intervals when new val is exactly one more than interval end.

💡 Verify boundary conditions for merging intervals at exact boundaries.

💡 Merge intervals if val == end+1 or val == start-1 of existing intervals.

Why it failed: Missed merging intervals at exact boundary values. Fix by including equality in adjacency checks. This is the exact boundary test.

✓ Correctly merges intervals at exact boundary values.

t2_04edge

Input{"calls":[{"method":"addNum","args":[5]},{"method":"addNum","args":[5]},{"method":"addNum","args":[5]},{"method":"getIntervals","args":[]}]}

Expected[[[5,5]]]

⏱ Performance - must finish in 2000ms

Adding the same number multiple times does not change intervals after first addition.

💡 Check if duplicates cause intervals to be recreated or merged incorrectly.

💡 Use a data structure to track existing numbers to avoid duplicate inserts.

💡 Skip adding val if it already exists in intervals.

Why it failed: Intervals changed or duplicated after adding duplicates. Fix by checking if val already exists before adding. This is the duplicate insertion test.

✓ Correctly ignores duplicate numbers without changing intervals.

t3_01corner

Input{"calls":[{"method":"addNum","args":[1]},{"method":"addNum","args":[3]},{"method":"addNum","args":[5]},{"method":"addNum","args":[7]},{"method":"addNum","args":[9]},{"method":"addNum","args":[4]},{"method":"getIntervals","args":[]}]}

Expected[[[1,1],[3,5],[7,7],[9,9]]]

⏱ Performance - must finish in 2000ms

Adding 4 merges [3,3] and [5,5] into [3,5], but does not merge with 1 or 7.

💡 Beware of greedy merges that merge intervals incorrectly.

💡 Check only intervals adjacent to val, not all intervals.

💡 Merge intervals only if val bridges them directly, not skipping gaps.

Why it failed: Incorrectly merged non-adjacent intervals (greedy merge). Fix by merging only intervals adjacent to val, not all intervals. This is the greedy trap test.

✓ Correctly merges only adjacent intervals, avoiding greedy over-merging.

t3_02corner

Input{"calls":[{"method":"addNum","args":[2]},{"method":"addNum","args":[2]},{"method":"addNum","args":[2]},{"method":"getIntervals","args":[]}]}

Expected[[[2,2]]]

⏱ Performance - must finish in 2000ms

Adding the same number multiple times does not change intervals after first addition.

💡 Check if duplicates cause intervals to be recreated or merged incorrectly.

💡 Use a data structure to track existing numbers to avoid duplicate inserts.

💡 Skip adding val if it already exists in intervals.

Why it failed: Intervals changed or duplicated after adding duplicates. Fix by checking if val already exists before adding. This is the duplicate insertion test.

✓ Correctly ignores duplicate numbers without changing intervals.

t3_03corner

Input{"calls":[{"method":"addNum","args":[0]},{"method":"addNum","args":[10000]},{"method":"getIntervals","args":[]}]}

Expected[[[0,0],[10000,10000]]]

⏱ Performance - must finish in 2000ms

Adding numbers at minimum and maximum allowed values creates two separate intervals.

💡 Check boundary handling for smallest and largest possible values.

💡 Ensure intervals are sorted and no incorrect merges occur.

💡 Maintain intervals sorted by start value regardless of val range.

Why it failed: Failed to handle min/max values correctly or merged incorrectly. Fix by handling boundary values explicitly and sorting intervals. This is the min/max boundary test.

✓ Correctly handles minimum and maximum value insertions.

t4_01performance

Input{"calls":[{"method":"addNum","args":[0]},{"method":"addNum","args":[1]},{"method":"addNum","args":[2]},{"method":"addNum","args":[3]},{"method":"addNum","args":[4]},{"method":"addNum","args":[5]},{"method":"addNum","args":[6]},{"method":"addNum","args":[7]},{"method":"addNum","args":[8]},{"method":"addNum","args":[9]},{"method":"addNum","args":[10]},{"method":"addNum","args":[11]},{"method":"addNum","args":[12]},{"method":"addNum","args":[13]},{"method":"addNum","args":[14]},{"method":"addNum","args":[15]},{"method":"addNum","args":[16]},{"method":"addNum","args":[17]},{"method":"addNum","args":[18]},{"method":"addNum","args":[19]},{"method":"addNum","args":[20]},{"method":"addNum","args":[21]},{"method":"addNum","args":[22]},{"method":"addNum","args":[23]},{"method":"addNum","args":[24]},{"method":"addNum","args":[25]},{"method":"addNum","args":[26]},{"method":"addNum","args":[27]},{"method":"addNum","args":[28]},{"method":"addNum","args":[29]},{"method":"addNum","args":[30]},{"method":"addNum","args":[31]},{"method":"addNum","args":[32]},{"method":"addNum","args":[33]},{"method":"addNum","args":[34]},{"method":"addNum","args":[35]},{"method":"addNum","args":[36]},{"method":"addNum","args":[37]},{"method":"addNum","args":[38]},{"method":"addNum","args":[39]},{"method":"addNum","args":[40]},{"method":"addNum","args":[41]},{"method":"addNum","args":[42]},{"method":"addNum","args":[43]},{"method":"addNum","args":[44]},{"method":"addNum","args":[45]},{"method":"addNum","args":[46]},{"method":"addNum","args":[47]},{"method":"addNum","args":[48]},{"method":"addNum","args":[49]},{"method":"addNum","args":[50]},{"method":"addNum","args":[51]},{"method":"addNum","args":[52]},{"method":"addNum","args":[53]},{"method":"addNum","args":[54]},{"method":"addNum","args":[55]},{"method":"addNum","args":[56]},{"method":"addNum","args":[57]},{"method":"addNum","args":[58]},{"method":"addNum","args":[59]},{"method":"addNum","args":[60]},{"method":"addNum","args":[61]},{"method":"addNum","args":[62]},{"method":"addNum","args":[63]},{"method":"addNum","args":[64]},{"method":"addNum","args":[65]},{"method":"addNum","args":[66]},{"method":"addNum","args":[67]},{"method":"addNum","args":[68]},{"method":"addNum","args":[69]},{"method":"addNum","args":[70]},{"method":"addNum","args":[71]},{"method":"addNum","args":[72]},{"method":"addNum","args":[73]},{"method":"addNum","args":[74]},{"method":"addNum","args":[75]},{"method":"addNum","args":[76]},{"method":"addNum","args":[77]},{"method":"addNum","args":[78]},{"method":"addNum","args":[79]},{"method":"addNum","args":[80]},{"method":"addNum","args":[81]},{"method":"addNum","args":[82]},{"method":"addNum","args":[83]},{"method":"addNum","args":[84]},{"method":"addNum","args":[85]},{"method":"addNum","args":[86]},{"method":"addNum","args":[87]},{"method":"addNum","args":[88]},{"method":"addNum","args":[89]},{"method":"addNum","args":[90]},{"method":"addNum","args":[91]},{"method":"addNum","args":[92]},{"method":"addNum","args":[93]},{"method":"addNum","args":[94]},{"method":"addNum","args":[95]},{"method":"addNum","args":[96]},{"method":"addNum","args":[97]},{"method":"addNum","args":[98]},{"method":"addNum","args":[99]},{"method":"getIntervals","args":[]}]}

Expectednull

⏱ Performance - must finish in 2000ms

Adding 100 sequential numbers and then getting intervals tests O(n) insertion and retrieval performance within 2 seconds.

💡 Use balanced tree or sorted container to achieve O(log n) insertion.

💡 Avoid rebuilding intervals from scratch on each addNum call.

💡 Maintain merged intervals incrementally to optimize getIntervals.

Why it failed: TLE due to O(n log n) or worse per addNum or getIntervals. Fix by using balanced tree or sorted container with merge on insert. This is the performance complexity test.

✓ Efficient O(log n) insertion and O(n) retrieval confirmed.

Practice

1. Consider the following Python function that finds the minimum number of arrows to burst balloons represented as intervals. Given the input points = [[10,16],[2,8],[1,6],[7,12]], what is the value of arrows after processing all intervals?

easy

A. 1

B. 4

C. 3

D. 2

Solution

1. Step 1: Sort intervals by end coordinate

   Sorted points: [[1,6],[2,8],[7,12],[10,16]]

2. Step 2: Iterate and count arrows

   Start with arrow_pos=6, arrows=1. Next interval start=2 ≤ 6 (covered), next start=7 > 6 (new arrow), arrows=2, arrow_pos=12. Next start=10 ≤ 12 (covered).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Two arrows suffice to burst all balloons [OK]

Hint: Sort by end, count arrows when start > current arrow position [OK]

Common Mistakes:

• Not sorting intervals before processing
• Using start >= arrow_pos instead of start > arrow_pos
• Off-by-one errors in counting arrows

2. Given the following code and input intervals = [[1,4],[3,6],[2,8]], what is the value of count after the loop finishes?

easy

A. 2

B. 1

C. 3

D. 0

Solution

1. Step 1: Sort intervals by start ascending, end descending

   Sorted intervals: [[1,4],[2,8],[3,6]]

2. Step 2: Iterate and update count and max_end

   Iteration 1: end=4 > max_end=0 -> count=1, max_end=4 Iteration 2: end=8 > max_end=4 -> count=2, max_end=8 Iteration 3: end=6 ≤ max_end=8 -> count unchanged

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Count increments twice for uncovered intervals [OK]

Hint: Sort then count intervals with strictly greater end [OK]

Common Mistakes:

• Misorder intervals after sorting
• Off-by-one counting in loop

3. The following code attempts to count intervals containing each point using a line sweep. Identify the bug that causes incorrect counts for points exactly at interval ends.

medium

A. Line adding interval end event should use end + 1 instead of end.

B. Sorting key should sort points before interval starts.

C. Active count should be incremented after processing points, not before.

D. Result array initialization size is incorrect.

Solution

1. Step 1: Identify event creation for interval ends

   Interval end events use 'end' instead of 'end + 1', so points exactly at interval end are processed after the interval ends.

2. Step 2: Understand effect on counting

   Because end events are processed at 'end', points at 'end' see active count after decrement, missing that interval.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Changing to end + 1 fixes counting for points at interval ends [OK]

Hint: Interval end event must be at end+1 to include points at end [OK]

Common Mistakes:

• Using end instead of end+1
• Misordering events
• Incorrect active count update

4. Examine the following buggy code for Employee Free Time. Which line contains the subtle bug causing incorrect free time intervals?

medium

A. Line appending end event with (interval[1], -1)

B. Line appending start event with (interval[0], 1)

C. Line updating prev = time inside loop

D. Line sorting events with key=lambda x: (x[0], -x[1])

Solution

1. Step 1: Understand sorting order impact

   End events must come before start events at same time to avoid false free intervals.

2. Step 2: Identify bug in sorting key

   Sorting with key (x[0], -x[1]) puts start events before end events at ties, causing incorrect free time detection.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Correct sorting is (x[0], x[1]) to put end events before start [OK]

Hint: End events must sort before start events at same time [OK]

Common Mistakes:

• Sorting start before end events at same timestamp

5. If employees can have intervals with negative start or end times (e.g., [-5, 0]) or zero-length intervals, which modification to the sweep line algorithm is necessary to correctly find free time?

hard

A. Ignore zero-length intervals and ensure sorting places end events before start events at ties

B. Treat zero-length intervals as free time intervals

C. Sort events only by time, ignoring event type

D. Merge touching intervals as free time gaps

Solution

1. Step 1: Handle zero-length intervals

   Zero-length intervals like [2,2] do not represent busy time and should be ignored to avoid false free intervals.

2. Step 2: Maintain correct sorting order

   Sorting end events before start events at same time prevents reporting free time between touching intervals or zero-length intervals.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Ignoring zero-length intervals and correct sorting avoids invalid free times [OK]

Hint: Ignore zero-length intervals and sort end before start events [OK]

Common Mistakes:

• Counting zero-length intervals as free time
• Sorting start before end events