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
There is no meaningfully slower classical approach here: the array is already sorted, so any correct solution is essentially a linear scan — the ladder starts at the naive design and the “optimization” is about shape, not asymptotics.
The most literal design walks each run to its end with an inner loop:
from typing import List
class Solution:
def summaryRanges(self, 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 insight: 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
class Solution:
def summaryRanges(self, 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]:
| i | nums[i] | edge? | emitted | start after |
|---|
| 0 | 0 | no (0+1 == 1) | — | 0 |
| 1 | 1 | no (1+1 == 2) | — | 0 |
| 2 | 2 | yes (2+1 != 4) | "0->2" | 3 |
| 3 | 4 | no (4+1 == 5) | — | 3 |
| 4 | 5 | yes (5+1 != 7) | "4->5" | 5 |
| 5 | 7 | yes (last index) | "7" | 6 |
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 win is a single loop with one clearly stated edge condition, which is much harder to get off-by-one wrong.
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 worries are a red herring in Python, but note 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 crisp definition of “this element is the group’s right edge” (last element, or the successor breaks the group’s invariant). Emit at edges, reset the marker, and the empty input and final group fall out for free. The same start-marker skeleton handles run-length encoding, grouping equal elements, and detecting missing ranges.