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

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

• Invariant: start marks the beginning of the current run; when a gap appears, you finalize that run.
• Sorting establishes a consistent processing order.
• Merge/greedy steps maintain a correct partial solution.
• After processing all intervals, the result is optimal and complete.

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.

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".