> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Data Stream as Disjoint Intervals

> Tested Python solution for LeetCode 352 with 12 pytest cases. Generate a practice environment with lcpy.

LeetCode 352, [Hard](/catalog/hard). Topics: [Hash Table](/catalog/topics/hash-table), [Binary Search](/catalog/topics/binary-search), [Union-Find](/catalog/topics/union-find), [Design](/catalog/topics/design), [Data Stream](/catalog/topics/data-stream), [Ordered Set](/catalog/topics/ordered-set). [View on LeetCode](https://leetcode.com/problems/data-stream-as-disjoint-intervals/description/).

Generate this problem as a practice environment: tested reference solution, 12 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 352   # by problem number
lcpy gen -s data_stream_as_disjoint_intervals   # by problem name
```

## Problem

Given a data stream input of non-negative integers `a1, a2, ..., an`, summarize the numbers seen so far as a list of disjoint intervals.

Implement the `SummaryRanges` class:

* `SummaryRanges()` Initializes the object with an empty stream.
* `void addNum(int value)` Adds the integer `value` to the stream.
* `int[][] getIntervals()` Returns a summary of the integers in the stream currently as a list of disjoint intervals `[starti, endi]`. The answer should be sorted by `starti`.

### Examples

```
Input
['SummaryRanges', 'addNum', 'getIntervals', 'addNum', 'getIntervals', 'addNum', 'getIntervals', 'addNum', 'getIntervals', 'addNum', 'getIntervals']
[[], [1], [], [3], [], [7], [], [2], [], [6], []]
Output
[None, None, [[1, 1]], None, [[1, 1], [3, 3]], None, [[1, 1], [3, 3], [7, 7]], None, [[1, 3], [7, 7]], None, [[1, 3], [6, 7]]]

Explanation
SummaryRanges summaryRanges = new SummaryRanges();
summaryRanges.addNum(1);      // arr = [1]
summaryRanges.getIntervals(); // return [[1, 1]]
summaryRanges.addNum(3);      // arr = [1, 3]
summaryRanges.getIntervals(); // return [[1, 1], [3, 3]]
summaryRanges.addNum(7);      // arr = [1, 3, 7]
summaryRanges.getIntervals(); // return [[1, 1], [3, 3], [7, 7]]
summaryRanges.addNum(2);      // arr = [1, 2, 3, 7]
summaryRanges.getIntervals(); // return [[1, 3], [7, 7]]
summaryRanges.addNum(6);      // arr = [1, 2, 3, 6, 7]
summaryRanges.getIntervals(); // return [[1, 3], [6, 7]]
```

### Constraints

* 0 \<= value \<= 10\<sup>4\</sup>
* At most 3 \* 10\<sup>4\</sup> calls will be made to `addNum` and `getIntervals`.
* At most 10\<sup>2\</sup> calls will be made to `getIntervals`.

**Follow up:** What if there are lots of merges and the number of disjoint intervals is small compared to the size of the data stream?

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/data_stream_as_disjoint_intervals/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/data_stream_as_disjoint_intervals/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
from bisect import bisect_left


class SummaryRanges:
    # Maintains starts sorted; interval i covers [starts[i], ends[i]].
    # add_num: O(log n) lookup + O(n) list insert; get_intervals: O(k).
    # Space: O(n)
    def __init__(self) -> None:
        self._starts: list[int] = []
        self._ends: list[int] = []

    def add_num(self, value: int) -> None:
        index = bisect_left(self._starts, value)
        if index < len(self._starts) and self._starts[index] == value:
            return  # duplicate
        # value lands strictly between interval index-1 and index
        left_adjacent = index > 0 and self._ends[index - 1] == value - 1
        right_adjacent = index < len(self._starts) and self._starts[index] == value + 1
        if left_adjacent and right_adjacent:
            # bridge the two intervals
            self._ends[index - 1] = self._ends[index]
            del self._starts[index]
            del self._ends[index]
        elif left_adjacent:
            self._ends[index - 1] = value
        elif right_adjacent:
            self._starts[index] = value
        else:
            self._starts.insert(index, value)
            self._ends.insert(index, value)

    def get_intervals(self) -> list[list[int]]:
        return [[start, end] for start, end in zip(self._starts, self._ends, strict=True)]
```

## Complexity

| Time | Space |
| - | - |
| - | O(n) |

## Tags

[NeetCode All](/catalog/neetcode).


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.