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.
This approach involves detecting the start and end of each range by iterating through the array sequentially. You remember the start of a potential range and adjust the range's end as long as consecutive numbers are found. When a break in consecutiveness occurs, you fix the end of the current range and start a new one.
The C solution iterates through the sorted array. It uses a start pointer that marks the beginning of a range. If consecutive numbers appear, it keeps adjusting the endpoint of the range. When non-consecutiveness is found (or array ends), it forms a string for that range and starts a new one.
Time Complexity: O(n)
Space Complexity: O(n)
This approach utilizes a two-pointer method where one pointer marks the beginning of a new range, and another pointer (or the loop index itself) expands the range as far as possible until the next number isn't consecutive. Once a sequence ends, if numbers are the same, it is a single-element range; otherwise, a range connecting two different numbers is formed.
The two-pointer approach in C keeps two indices. The starting pointer begins a new potential range. The other adjusts as long as numbers are consecutive. Once they diverge, it involves forming a possible range string or single number and returning when done.
Time Complexity: O(n)
Space Complexity: O(n)
We can use two pointers i and j to find the left and right endpoints of each interval.
Traverse the array, when j + 1 < n and nums[j + 1] = nums[j] + 1, move j to the right, otherwise the interval [i, j] has been found, add it to the answer, then move i to the position of j + 1, and continue to find the next interval.
Time complexity O(n), where n is the length of the array. Space complexity O(1).
| Approach | Complexity |
|---|---|
| Sequential Range Detection | Time Complexity: O(n) |
| Optimal Pointer Movement | Time Complexity: O(n) |
| Two Pointers | — |
| 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 |
Summary Ranges - Leetcode 228 - Arrays & Strings (Python) • Greg Hogg • 30,039 views views
Watch 9 more video solutions →Practice Summary Ranges with our built-in code editor and test cases.
Practice on FleetCode