Search⌘ K
AI Features
Home
Courses
Grokking the Coding Interview Patterns

Solution: Data Stream as Disjoint Intervals

Explore how to implement the Summary Ranges class to maintain a compact, sorted collection of disjoint intervals from a stream of integers. Understand the process to add numbers, merge overlapping intervals, and retrieve these intervals efficiently, using a sorted map data structure. This lesson helps you apply the intervals pattern to solve streaming and merging interval problems common in coding interviews.

We'll cover the following...

Statement

You are given a stream of non-negative integers a1,a2,…,ana_1, a_2, \dots, a_n. At any point, you need to summarize all numbers seen so far as a list of disjoint intervals.

Your task is to implement the Summary Ranges class, where:

  • Constructor: Initializes the Summary Ranges object with an empty stream.

  • Add Num(int value): Adds the integer value to the stream.

  • Get Intervals(): Returns the current summary of numbers as a list of disjoint intervals [start_i, end_i], sorted by start_i.

Note: Each number belongs to exactly one interval. Intervals must merge whenever new numbers connect or extend existing ones, and duplicate insertions should not affect the summary.

Constraints:

  • 0≤0 \leq value ≤104\leq 10^4 ...