Summary Ranges

Given a sorted array of unique integers, return the smallest list of ranges that cover all numbers exactly. A range is formatted as:

• "a->b" if a != b
• "a" if a == b

Why this is worth learning

A range ends exactly at a gap in the sorted unique input. Maximal consecutive runs are both sufficient and necessary for the smallest exact cover.

Before coding: one-minute experiment

How should [-2,-1,1,3,4] be represented?

Function signature

func SummaryRanges(nums []int) []string

Inputs / outputs

• nums: sorted, strictly increasing integers.
• Return: slice of range strings.

Example

nums = [0,1,2,4,5,7]
Output: ["0->2","4->5","7"]

Constraints

• 0 <= len(nums) <= 100_000
• -1_000_000_000 <= nums[i] <= 1_000_000_000

Core idea (near-solution)

Scan and build runs of consecutive numbers. Each run becomes one range.

Invariant: start marks the beginning of the current run; when a gap appears, you finalize that run.

Algorithm (step-by-step)

1. If empty, return empty.
2. Set start = nums[0], prev = nums[0].
3. For each next value x:
   • If x == prev + 1, continue the run.
   • Otherwise, close the current range (start to prev) and start a new run at x.
4. After the loop, close the final range.

Correctness sketch

Keep the first and last values of the current consecutive run. If the next value equals previous+1, extending the run preserves exact coverage without gaps. Otherwise the gap prevents any exact integer range from covering both the current run and the next value, so emitting the current run is forced. Restarting at the new value preserves the invariant that prior output covers precisely the finished prefix. After the scan, emit the final run. Every emitted range is maximal, and every gap forces a boundary, so no representation with fewer exact ranges is possible.

Trace (hand walkthrough)

Example input:
nums = [0,1,2,4,5,7]
Output: ["0->2","4->5","7"]

Walk:
- scan 0,1,2 -> run "0->2"
- gap at 4 -> run 4,5 -> "4->5"
- last single 7 -> "7"

Pitfalls to avoid

• Forgetting to flush the last range.
• Using string formatting that confuses singletons vs ranges.

Debugging lens

Test a final singleton, all consecutive values, negative transitions, and empty input. Forgetting the final flush loses the last run.

Complexity

• Time: O(n)
• Extra space: O(1) beyond output.

Implementation notes (Go)

• Track run start and previous value; emit on breaks.
• Format singletons as "x" and ranges as "x->y".

Reconstruction checkpoint

How should [-2,-1,1,3,4] be represented?

Return to Intervals · Module quiz