Watch 10 video solutions for Summary Ranges, a easy level problem involving Array. This walkthrough by Greg Hogg has 18,649 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 cover 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 integer 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:
"a->b" if a != b"a" if a == b
Example 1:
Input: nums = [0,1,2,4,5,7] Output: ["0->2","4->5","7"] Explanation: The ranges are: [0,2] --> "0->2" [4,5] --> "4->5" [7,7] --> "7"
Example 2:
Input: nums = [0,2,3,4,6,8,9] Output: ["0","2->4","6","8->9"] Explanation: The ranges are: [0,0] --> "0" [2,4] --> "2->4" [6,6] --> "6" [8,9] --> "8->9"
Constraints:
0 <= nums.length <= 20-231 <= nums[i] <= 231 - 1nums are unique.nums is sorted in ascending order.Problem Overview: You receive a sorted array of unique integers. The goal is to compress consecutive numbers into range strings. A single number becomes "x", while a sequence like 1,2,3 becomes "1->3". The result is a list of ranges covering the entire array.
The key observation: because the array is sorted and contains no duplicates, consecutive numbers always appear next to each other. The problem reduces to detecting where a sequence starts and where it breaks.
Approach 1: Sequential Range Detection (O(n) time, O(1) space)
Iterate through the array while tracking the start of the current range. For each element, check whether the next number continues the sequence using nums[i] + 1 == nums[i+1]. When this condition fails, the range ends. If the start and end indices are the same, output a single value string; otherwise output start->end. Then reset the start pointer to the next element and continue scanning.
This approach works because every element belongs to exactly one range, so the array only needs a single pass. No additional data structures are required. It’s straightforward and highly readable, making it a common baseline implementation.
Approach 2: Optimal Pointer Movement (O(n) time, O(1) space)
This method uses a two‑pointer style scan. One pointer marks the beginning of a range, while the other pointer advances forward as long as numbers remain consecutive. When the sequence breaks, the interval between the two pointers forms a valid range. Format the result and move the start pointer to the next unexplored position.
The difference from the previous approach is that the forward pointer aggressively expands the range before producing output. Each element is still visited once, giving linear time complexity. Because only a few index variables are used, the space complexity remains constant.
This pattern appears often in problems involving sorted arrays and interval compression. Similar pointer movement techniques show up in problems involving array traversal and range grouping.
Recommended for interviews: Interviewers expect the linear scan solution. Either sequential detection or two‑pointer expansion demonstrates the same key insight: detect boundaries where consecutive numbers stop. A brute force or nested scan would signal missed optimization opportunities, while the O(n) approach shows you recognize sorted array structure and exploit it efficiently.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sequential Range Detection | O(n) | O(1) | Simple single-pass scan when array is already sorted and you want the most readable implementation |
| Optimal Pointer Movement | O(n) | O(1) | When using two-pointer range expansion patterns common in sorted array and interval problems |