Summary Ranges
Problem statement
You're given a sorted list of unique integers, nums — think of it as a
list of allocated port numbers, or healthy instance IDs in a fleet, already
in order with no repeats.
A range [a, b] covers every integer from a to b, inclusive. Return
the smallest sorted list of ranges that together cover exactly the numbers in
nums — every value in nums falls inside exactly one range, and no range
contains a value that isn't in nums.
Write each range as:
"a->b"if the range has more than one number (a != b)"a"if the range is a single number (a == b)
Examples
Example 1
Input: nums = [0,1,2,4,5,7]
Output: ["0->2","4->5","7"]
Explanation: 0, 1 and 2 are three numbers in a row, so they collapse into one range, "0->2". 4 and 5 are consecutive too, giving "4->5". 7 stands alone with no neighbour on either side, so it's printed as just "7".
Example 2
Input: nums = [0,2,3,4,6,8,9]
Output: ["0","2->4","6","8->9"]
Explanation: 0 has no neighbour (1 is missing), so it's its own range. 2, 3 and 4 run together into "2->4". 6 is isolated (5 and 7 are both missing). 8 and 9 are consecutive, giving "8->9".
Hints
Approach
Optimal: Two pointers
Intuition
nums is already sorted with no duplicates, so there's no need to ask a set
"does the next number exist?" — you can just look at the next array slot. A
range breaks exactly where nums[i + 1] != nums[i] + 1. Walk the array once:
remember where the current range started, and the moment that "+1 each step"
pattern breaks (or the array ends), close the range there and start the next
one right after it. This is also naturally safe from the integer-overflow
trap the brute-force version had to guard against: it only ever adds 1 to a
value it already knows isn't the array's largest element, so that addition
never overflows.
Steps
- If
numsis empty, return an empty list right away. - Set
start = 0— the index where the current range begins. - Walk
ifrom0to the last index. At eachi, check: isithe last index, or doesnums[i + 1]differ fromnums[i] + 1? Either way means the current range ends atnums[i]. - When a range ends, format it —
"nums[start]"ifnums[start] == nums[i], otherwise"nums[start]->nums[i]"— append it to the result, and setstart = i + 1to begin the next range. - Return the result once the walk finishes.
Dry run
nums = [0, 2, 3, 4, 6, 8, 9], start = 0
| i | nums[i] | last index or next ≠ nums[i]+1? | action |
|---|---|---|---|
| 0 | 0 | next is 2, 2 ≠ 1 → yes | emit "0", start = 1 |
| 1 | 2 | next is 3 = 2+1 → no | keep going |
| 2 | 3 | next is 4 = 3+1 → no | keep going |
| 3 | 4 | next is 6, 6 ≠ 5 → yes | emit "2->4", start = 4 |
| 4 | 6 | next is 8, 8 ≠ 7 → yes | emit "6", start = 5 |
| 5 | 8 | next is 9 = 8+1 → no | keep going |
| 6 | 9 | last index → yes | emit "8->9" |
Result: ["0", "2->4", "6", "8->9"], matching Example 2.
Edge cases: an empty nums is checked before the loop and returns []
directly. A single-element array closes its one range on the first (and
only, last-index) iteration.
Complexity
Time O(n) - a single pass over the array; each index is looked at once.
Space O(1) - extra — no hash set is needed, only the output list and a couple of index variables.
class Solution:
def summaryRanges(self, nums: list[int]) -> list[str]:
n = len(nums)
result = []
start = 0
for i in range(n):
if i == n - 1 or nums[i + 1] != nums[i] + 1:
if nums[start] == nums[i]:
result.append(str(nums[start]))
else:
result.append(f"{nums[start]}->{nums[i]}")
start = i + 1
return result
if __name__ == "__main__":
print(Solution().summaryRanges([0, 1, 2, 4, 5, 7])) # ['0->2', '4->5', '7']
print(Solution().summaryRanges([0, 2, 3, 4, 6, 8, 9])) # ['0', '2->4', '6', '8->9']RecapThe whole problem in a few lines, for the night before
- Spot it: turn a sorted unique list into ranges like "0->2"
- Idea: one pass; remember the start of a run, and when the next number is not previous + 1, close the range
- Cost: O(n) time, O(1) extra space
- Trap: a single-number range is "5", not "5->5"; and close the last range after the loop
Interview follow-ups
What if
numscould contain duplicate values?Deduplicate first — put the values in a set, or, after sorting, skip over any value equal to the one before it — so each distinct value is only ever the start of one range. The rest of the two-pointer walk is unchanged, since it only cares about distinct consecutive values.
The array is too large to hold in memory — say, a billion sorted IDs arriving one at a time as a stream. What changes?
You don't need the whole array in memory at once: keep just the current range's start and the last value you saw. Each time a new value arrives, compare it to
last + 1, the same check the two-pointer version makes between neighbours. The moment the streak breaks, format and emit the range that just closed, then start a new one at the incoming value. Memory stays O(1) beyond whatever you do with the output.
Frequently asked questions
Because nums is already sorted with no duplicates, "is the next number consecutive?" is just "look at the next array slot and compare it to the current value plus one." A hash set is only needed when you can't rely on order — which is exactly the situation the brute-force approach pretends it's in.
nums[i] can be as small as Integer.MIN_VALUE (-2^31). Computing x - 1 in a plain 32-bit integer wraps around to Integer.MAX_VALUE instead of going further negative, so a lookup could wrongly report that a huge positive number "comes right before" the smallest possible one. The fix used above is to do the arithmetic in a wider type (long in Java, long long in C++) so the subtraction never overflows. Python doesn't have this problem, since its integers grow as large as needed automatically.
Turning a long list of individual identifiers — open ports, healthy instance IDs, allocated IPs in a subnet — into a short, human-readable "ranges" report is a real formatting task, and it's exactly this problem's output shape.
Sort it first, which costs O(n log n), and then either approach works on the sorted result. Or skip sorting and use the hash-set approach directly — it never relies on the array's order, only on correct membership checks, so it works on an unsorted (but still duplicate-free) list as-is.