Summary Ranges
Compress a sorted list of numbers into ranges, and practise the start/end bookkeeping every interval problem needs
Problem Statement
Given a sorted array of distinct integers, return the smallest list of ranges that covers all of them exactly. Each range is written "a->b", or just "a" if it holds one number.
Input: nums = [0, 1, 2, 4, 5, 7]
Output: ["0->2", "4->5", "7"]
Input: nums = [0, 2, 3, 4, 6, 8, 9]
Output: ["0", "2->4", "6", "8->9"]
Input: nums = []
Output: []Intuition
This problem builds intervals rather than merging them, which makes it the gentlest place to learn the bookkeeping.
The input is sorted and distinct, so numbers form runs of consecutive values. A run continues while each number is exactly one more than the last, and ends the moment there is a gap.
[0, 1, 2, 4, 5, 7]
└──────┘ └──┘ └ runs: 0..2, 4..5, 7
gap gapThe insight
You cannot output a range when you start it — you do not yet know where it ends. So hold the start, walk forward, and output only when the run breaks.
That "hold something open until you know it is finished" shape is the same one Merge Intervals uses. Here there is no sorting or overlap logic in the way, so the pattern is easy to see.
The test for "still in the same run" is nums[i] == nums[i - 1] + 1. Because the values are distinct and sorted, anything else is a gap.
Approach
Remember where the current run began
Keep start = nums[0]. This value is not written out yet.
Walk forward while the run continues
If nums[i] is one more than nums[i - 1], the run is unbroken. Do nothing and keep going.
On a gap, close the run and open a new one
The run covers start to nums[i - 1] — the previous value, not the current one. Format it, then set start = nums[i].
Close the final run after the loop
The last run is still open when the array ends.
Solution
def summary_ranges(nums: list[int]) -> list[str]:
"""Compress a sorted, distinct array into range strings."""
if not nums:
return []
ranges: list[str] = []
start = nums[0]
for i in range(1, len(nums)):
if nums[i] != nums[i - 1] + 1:
# The run broke. It ended at the PREVIOUS value.
ranges.append(format_range(start, nums[i - 1]))
start = nums[i]
ranges.append(format_range(start, nums[-1]))
return ranges
def format_range(start: int, end: int) -> str:
return str(start) if start == end else f"{start}->{end}"Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(1)
Time — a single pass. No sorting is needed, because the input is already sorted; that guarantee is what makes this O(n) rather than O(n log n).
Space — O(1) beyond the output. Only start is tracked.
Edge Cases
Related Problems
- Merge Intervals — the same open/close bookkeeping, with overlap logic added
- Intervals — the overlap test and sorting rules