Summary Ranges

Easy#228merge

You get a sorted array of distinct whole numbers. Cover them with the fewest ranges of consecutive numbers and write each range as "a->b", or as "a" if it holds one number. Our example: [2, 3, 4, 6, 8, 9, 11] — the answer is ["2->4", "6", "8->9", "11"].

228 Summary RangesWalkthrough · 1×

Example: [2, 3, 4, 6, 8, 9, 11]. The numbers stand at their places on a number line, so the gaps are empty slots; the ranges are below them.

nums12345678910111223468911ranges
not reached yetcurrent number, the range it went intoalready in a rangelast rangeend + 1: where the next number has to beranges

nums has 7 numbers, not empty

01/21
restart · back · play · step
Speed
1function summaryRanges(nums):
2 if nums is empty: return []
3 ranges = [[nums[0], nums[0]]]
4 for each x after the first:
5 if x == ranges.last.end + 1:
6 ranges.last.end = x
7 else:
8 add [x, x] to ranges
9 return ranges as "a->b", or "a" when a == b
state
ranges
–
x
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. Each number is an interval [x, x]. Whole numbers have nothing between x and x + 1, so x joins the last range exactly when x = end + 1.
  2. The array is sorted, so the last range is the only one x could continue: every earlier range ends further left.
  3. A number that is not end + 1 means a missing number before it, and the range has to end there. So the ranges are as few as possible: each one stops only at a real gap.

Complexity

Time O(n): one pass over the numbers. Memory O(1) besides the answer itself.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.