Why it works
- 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.
- The array is sorted, so the last range is the only one x could continue: every earlier range ends further left.
- 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 ↗