DSA problem
Summary Ranges
You are given a sorted unique integer array nums. A range [a, b] is the set of all integers from a to b (inclusive). Return the smallest sorted list of ranges that covers all the numbers in the array exactly. That is, each element of nums is covered by exactly one of the ranges, and no integer outside nums is included in any range.
Each range [a, b] must be printed in a specific compact form. If a == b, the string is just "a". Otherwise the string is "a->b", using an arrow to separate the start and end of the run. The output is the list of these range strings in the same order as the runs appear in the input.
The key observation is that consecutive integers in nums form a single range. Because nums is sorted and contains only distinct values, any two adjacent elements either differ by exactly one (extending the current run) or by more than one (closing the current run and starting a new one). This makes a single linear scan sufficient.
The optimal approach walks the array once, tracking the start index of the current run. At each step compare nums[i] with nums[i-1]: if they differ by more than one, the previous run ends at nums[i-1] and must be emitted, after which start advances to i. After the loop, the final run is emitted. The algorithm runs in O(n) time with O(1) auxiliary space beyond the output.
Examples
nums = [0,1,2,4,5,7]["0->2","4->5","7"]nums = [0,2,3,4,6,8,9]["0","2->4","6","8->9"]nums = [][]Constraints
- 0 <= nums.length <= 20
- -2^31 <= nums[i] <= 2^31 - 1
- All the values of nums are unique.
- nums is sorted in ascending order.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.