Summary Ranges

Problem

You’re given a sorted integer array nums with all elements distinct. Compress it into the shortest possible list of range strings that together cover exactly the numbers present:

• a run of consecutive integers a, a+1, ..., b (with a != b) becomes the string "a->b";
• an isolated number a becomes just "a".

Return the ranges in ascending order.

Examples

• Input: nums = [0, 1, 2, 4, 5, 7] → Output: ["0->2", "4->5", "7"] 0–2 are consecutive, 4–5 are consecutive, 7 stands alone.
• Input: nums = [0, 2, 3, 4, 6, 8, 9] → Output: ["0", "2->4", "6", "8->9"] Runs break wherever the gap between neighbors exceeds 1.
• Input: nums = [-3, -2, -1, 5] → Output: ["-3->-1", "5"] Negative numbers form runs the same way; -3,-2,-1 is one run.

Constraints

• 0 <= len(nums) <= 20
• -2^31 <= nums[i] <= 2^31 - 1
• All values are unique and nums is sorted ascending

A single O(n) pass is expected: the array is sorted, so each run is a stretch of adjacent indices.

Think about it first

TL;DR

One linear pass that tracks each run’s start and emits at every break — O(n) time, O(1) extra space beyond the output.

Approach 1 — Brute force

Because the array is already sorted, every correct solution is a linear scan; there is no slower classical approach to improve on. The difference between approaches is code shape, not asymptotics.

The most literal design walks each run to its end with an inner loop:

from typing import List


def summaryRanges(nums: List[int]) -> List[str]:
    result = []
    i = 0
    n = len(nums)
    while i < n:
        j = i
        while j + 1 < n and nums[j + 1] == nums[j] + 1:
            j += 1
        if i == j:
            result.append(str(nums[i]))
        else:
            result.append(f"{nums[i]}->{nums[j]}")
        i = j + 1
    return result

Complexity: O(n) time — despite the nested while, the pointers i and j each advance monotonically through the array, so every element is visited a constant number of times. O(1) extra space beyond the output. The constraints (n ≤ 20) put no pressure on anything; the exercise is writing the boundary logic cleanly.

Approach 2 — Single pass with a run-start marker

The inner loop is unnecessary. A run ends at index i exactly when i is the last index or nums[i] + 1 != nums[i + 1], so one flat loop suffices: remember where the current run started, and emit whenever the current element is a run’s right edge.

from typing import List


def summaryRanges(nums: List[int]) -> List[str]:
    result = []
    n = len(nums)
    start = 0
    for i in range(n):
        is_edge = i == n - 1 or nums[i] + 1 != nums[i + 1]
        if is_edge:
            if start == i:
                result.append(str(nums[start]))
            else:
                result.append(f"{nums[start]}->{nums[i]}")
            start = i + 1
    return result

Walkthrough on nums = [0, 1, 2, 4, 5, 7]:

Result: ["0->2", "4->5", "7"] — matches the expected output.

Complexity: O(n) time, O(1) extra space beyond the output list. Same asymptotics as Approach 1; the gain is a single loop with one stated edge condition, which is less prone to off-by-one errors.

Common pitfalls

• The empty array: nums = [] must return []. Both loops above handle it naturally — but versions that pre-seed start = nums[0] crash on it.
• Forgetting to flush the final run: if you only emit on a gap, the run that reaches the end of the array is silently dropped. Treating “last index” as an edge (or appending once more after the loop) fixes it.
• Emitting "a->a" for singleton runs instead of "a" — the two cases need the explicit start == i branch.
• Overflow does not matter in Python, but the values span the full 32-bit range, so nums[i] + 1 on INT_MAX would overflow in C/Java. Mention it if asked about other languages.

Pattern takeaway

Grouping a sorted sequence into maximal runs needs exactly one remembered index, where the current group began, plus a clear definition of “this element is the group’s right edge” (last element, or the successor breaks the group’s invariant). Emit at edges and reset the marker; the empty input and final group are then handled without special cases. The same start-marker skeleton handles run-length encoding, grouping equal elements, and detecting missing ranges.