Abstract / Summary

Track a data stream of integers and keep a list of non overlapping intervals sorted by start value.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 60% (200k+ submissions).

Typical patterns to solve this problem:

• Binary Search
• Design
• Ordered Set

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The SummaryRanges class maintains a dynamic collection of integer values and provides a snapshot of the current data as a list of disjoint, sorted intervals. Internally it relies on an ordered container to keep the elements unique and automatically sorted, which simplifies the construction of the interval list. The public interface consists of two operations: addNum to insert a new value and getIntervals to retrieve the current set of intervals.

Core Data Structure

The class declares a single private member:

set<int> all;

std::set guarantees that every inserted element appears exactly once and that the elements are kept in ascending order. This property eliminates the need for explicit duplicate checks or a separate sorting step when the intervals are generated.

Adding Numbers

The insertion routine is straightforward:

void addNum(int value) {
    all.insert(value);
}

Because std::set::insert performs a logarithmic-time search before placement, the container remains ordered without additional work. Duplicate values are silently ignored, preserving the invariant that each number appears at most once.

Generating Intervals

The getIntervals method walks the ordered set and groups consecutive numbers into ranges. The method begins by handling the empty-set case:

vector<vector<int>> result;
if (all.empty())
    return result;

Two sentinel variables, from and to, are initialized to a value that cannot be a legitimate element (-2). This choice ensures that the first element encountered will always start a new interval:

int from = -2;
int to   = -2;

The core loop iterates over every element x in the set:

for (auto x : all)
{
    if (x != to + 1)
    {
        // new interval
        if (from >= 0)
            result.push_back({ from, to });
        from = to = x;
        continue;
    }

    to = x;
}

When the current element x is not exactly one greater than to, the sequence of consecutive numbers has been broken. If an interval is already in progress (from >= 0), it is emitted into the result vector. A new interval is then started with both from and to set to x. If x does follow the previous number (x == to + 1), the interval is simply extended by updating to.

After the loop finishes, the final interval-still held in from and to-is added:

result.push_back({ from, to });
return result;

The result is a vector of two-element vectors, each representing the inclusive lower and upper bounds of an interval.

Edge Cases Handled

The implementation gracefully manages several boundary conditions. When the container is empty, the method returns an empty vector without entering the loop. A single inserted value produces a one-element interval because the loop runs once, the if (x != to + 1) branch creates a new interval, and the final push adds [value, value]. The sentinel initialization (-2) works for any non-negative input because the first comparison always triggers a new interval; the code also functions correctly for negative inputs because the sentinel is lower than any possible element, and the from >= 0 guard prevents emitting a spurious interval before the first real value is seen. Non-consecutive numbers are split into separate intervals, while long runs of consecutive numbers are collapsed into a single range.

Performance Optimizations

The choice of std::set provides two key efficiencies. First, it maintains order automatically, so the interval construction can proceed with a single linear pass over the container, avoiding an explicit sort. Second, the set enforces uniqueness at insertion time, eliminating the need for additional duplicate-removal logic. The interval generation uses push_back on a vector, which amortizes allocation costs and yields fast appends. By keeping only the minimal state (from, to) during iteration, the algorithm avoids auxiliary data structures, resulting in low memory overhead. The overall design leverages the standard library’s well-optimized containers to achieve concise and efficient behavior.

Imagine there is a magical toy box that likes to keep all the number blocks in perfect order. When a new number block arrives, the box finds the right spot for it and tucks it away safely. Inside the box, the numbers are kept in a special arrangement so they never get mixed up.

When someone asks to see how the numbers are bunched together, the box starts walking through all the blocks one by one. It looks for groups of numbers that are sitting right next to each other, like a train of blocks that go one after another without any gaps. It marks where each train begins and where it ends by remembering the first and the last block in a row. If there is a big jump between numbers, it knows that a new train must be starting. At the very end, it makes a list of all these little trains so everyone can see which numbers are connected.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

not analyzed yet

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++					Java		Python	TS
	WalkCCC	C++					Java		Python
	leetcode.ca	C++					Java		Python
	LeetcodeHelp	C++					Java		Python
	Progiez	C++					Java		Python
github	BigEggStudy			C#
	black-shadows	C++
	chenyanzhe	C++
	everthis		JS
	fsq	C++
	halfrost							Go
	JoshCrozier		JS
	keineahnung2345	C++
	linouk23	C++
	lzl124631x	C++
	martianoff				Scala
	ruoru					Rust
	suxrobGM			C#
	vthwang						Java
	wisdompeak	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Java, Python
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
chenyanzhe	C++
everthis	JavaScript
fsq	C++
halfrost	Go
JoshCrozier	JavaScript
keineahnung2345	C++
linouk23	C++
lzl124631x	C++
martianoff	Scala
ruoru	Rust
suxrobGM	C#
vthwang	Java
wisdompeak	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality