Summary Ranges
The key idea
Because the array is sorted with no duplicates, a range breaks exactly where the gap between two neighbours is more than 1. Mark the start of each run, scan until the chain of consecutive numbers stops, then emit that run as a single range.
Problem
You are given a sorted integer array nums with no duplicates.
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 there is no number x such that x is in one of the ranges but not in nums.
Each range [a, b] in the list should be output as one of the following:
- "a->b" if a != b
- "a" if a == b
Constraints
0 <= nums.length <= 20-2^31 <= nums[i] <= 2^31 - 1- All the values of
numsare unique. numsis sorted in ascending order.
Examples
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->0","2->4","6","8->9"]
Complexity
Time: O(n) Space: O(1)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Two Pointers problems
- 3SumMEDIUM
- 4SumMEDIUM
- Concatenation of ArrayEASY
- Container With Most WaterMEDIUM
- Is SubsequenceEASY
- Merge Sorted ArrayEASY
- Merge Strings AlternatelyEASY
- Move ZeroesEASY
- Next PermutationMEDIUM
- Remove Duplicates from Sorted ArrayEASY
- Remove Duplicates from Sorted Array IIMEDIUM
- Remove ElementEASY