228. Summary Ranges

228

EasyIntervals and Sweep LineLinear scan with run boundariesGroup consecutive runs

Summary Ranges

Given a sorted unique integer array nums, return the smallest sorted list of ranges that covers all the numbers exactly. Each range [a,b] is formatted as 'a->b' if a != b, or just 'a' if it is a single number.

Open official problem prompt ↗

In plain English

Compress a sorted list of distinct integers into the fewest contiguous ranges that together contain exactly those integers.

Picture it like this

Like listing page numbers you read: instead of '3,4,5,6' you write '3-6', and a lone page just as itself.

Example

Input: nums = [0,1,2,4,5,7]
Output: ["0->2","4->5","7"]
Why: 0,1,2 are consecutive so they form 0->2; 4,5 form 4->5; 7 stands alone.

Constraints

0 <= nums.length <= 20-2^31 <= nums[i] <= 2^31 - 1All values are uniquenums is sorted in ascending order

Pattern lesson

See the pattern, then code

Group consecutive runs

↗

Intervals and Sweep Line

Meetings, schedules, overlapping ranges, resource allocation, or timeline events.. Consecutive numbers differ by exactly 1; a run ends the moment the next number is not one more than the current, so track the start of each run and close it at every break.

New words, made simpleKnow these before the algorithm

Consecutive run: A maximal stretch of integers each exactly one larger than the previous.
Range string: The 'a->b' or 'a' text representation of a run.
Run boundary: The point where nums[i+1] != nums[i] + 1, ending the current run.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Build every number then group

Unnecessary extra work; the input is already sorted and unique.

Expand into a set and re-detect adjacency afterward.

Time O(n)Space O(n)

Best choiceSingle pass over runs

One linear scan with no auxiliary structure — ideal.

Walk the array, extending a run while values stay consecutive, and emit each run when it breaks.

Time O(n)Space O(1)

The rule we keep true

Invariant

When the inner loop stops, nums[i] holds the last value of the run that began at 'start', and every index before the outer i has already been emitted.

Why this is correct

Reasoning

Because the array is sorted and unique, a difference of exactly 1 is both necessary and sufficient for two neighbors to belong to the same range; extending until that fails and no further captures each maximal run exactly once.

The algorithm in three movesSay these aloud before coding

1Start a run at the current number

run 0..2 -> "0->2"

2Advance while the next number is exactly one greater

run 4..5 -> "4->5"

3Emit 'start' if the run has length 1, else 'start->end'

single 7 -> "7"

4Move to the number after the run and repeat

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Read0,1,2

2 · AskDoes each next equal prev+1?

3 · Update statestart = 0

4 · Resultextend to nums[i]=2, emit "0->2"

Key takeaway

The consecutive run 0,1,2 collapses to the single range 0->2.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 6Anchor the run start
Record where the current contiguous stretch begins.
2
Lines 7-8Extend the run
Advance i while the next value is exactly one greater, absorbing the whole run.
3
Lines 9-12Format the run
Emit a single number if start equals the run end, otherwise 'start->end'.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

Empty array returns []
Single element returns ["x"]
No consecutive values gives all singletons
Large values near INT limits (no overflow in Python)
Entire array one long run

Common beginner mistakes

Comparing values by index difference instead of value+1 (works only because uniqueness holds)
Off-by-one in the inner bound check i+1 < n
Forgetting the single-number format and always writing 'a->a'

Check your understanding

Why is checking nums[i+1] == nums[i] + 1 enough, without also verifying sortedness or uniqueness?

Summary Ranges

Summary Ranges

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Intervals and Sweep Line