Condense Values Into Ranges
Problem
You are given a sorted list of distinct integers. Describe it as the shortest possible list of runs of consecutive integers, in order. Write a run as "a->b" when it covers more than one value, and as just "a" when it holds a single value.
Examples
Input: nums = [0, 1, 2, 4, 5, 7]
Output: ["0->2", "4->5", "7"]Input: nums = [-3, -1, 0]
Output: ["-3", "-1->0"]
Why: negative values follow the same ruleInput: nums = []
Output: []
Why: edge case, no values means no runsHints
0 / 3
Because the list is sorted and has no repeats, a run can only break between two neighbouring entries.
A run continues exactly while each next value is one more than the value before it. Everything else is bookkeeping about where the current run started.
Keep the index where the current run starts. Extend an end index while the next value is exactly one larger. Then write the run, as a single value or as start arrow end, and begin the next run just after it.
Solution
Sorted, distinct input means a run breaks precisely where two neighbours differ by more than one, so a single left-to-right sweep finds every boundary. The outer loop marks where a run starts, the inner loop stretches its end while values stay consecutive, and the pair of indexes is then written in whichever of the two formats applies. Each index is visited once by the inner loop overall, so time is O(n) and space is O(1) beyond the output.
def condense(nums):
out, i = [], 0
while i < len(nums):
j = i
while j + 1 < len(nums) and nums[j + 1] == nums[j] + 1:
j += 1 # the run is still consecutive
out.append(str(nums[i]) if i == j else f"{nums[i]}->{nums[j]}")
i = j + 1 # next run starts after this one
return out
print(condense([0, 1, 2, 4, 5, 7])) # -> ['0->2', '4->5', '7']
print(condense([-3, -1, 0])) # -> ['-3', '-1->0']
print(condense([])) # -> []Stuck on the idea rather than the code? Interval Basics & Sorting covers it.