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 == bExample 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.The key idea in Summary Ranges is to scan the sorted array and group consecutive numbers into ranges. Since the array is already sorted and contains unique values, we can iterate once and track the start of the current range. As long as the next number is exactly current + 1, the range continues.
When a break occurs (i.e., the next number is not consecutive), we finalize the current range and start a new one. If the range contains only one element, we output that number directly. Otherwise, we format it as start->end. This technique is essentially a linear traversal with two pointers: one marking the start of a range and the other expanding it.
Because each element is visited only once, the algorithm runs in O(n) time. Apart from the result list, it uses O(1) extra space, making it efficient for large arrays.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Linear Scan / Two Pointer Range Tracking | O(n) | O(1) (excluding output) |
Greg Hogg
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.
Time Complexity: O(n)
Space Complexity: O(n)
1
2function summaryRanges(nums) {
3 const result = [];
4 let i = 0;
5 while (i < nums.length) {
6 let start = i;
7 while (i + 1 < nums.length && nums[i] + 1 === nums[i + 1]) {
8 i++;
9 }
10 if (start === i) {
11 result.push(`${nums[start]}`);
12 } else {
13 result.push(`${nums[start]}->${nums[i]}`);
14 }
15 i++;
16 }
17 return result;
18}
19The JavaScript solution is implemented using a loop to identify ranges. It employs backticks for easy string interpolation when creating the range strings. Result is returned as an array of strings.
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.
Time Complexity: O(n)
Space Complexity: O(n)
1
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
A linear scan works because the numbers are sorted. This allows us to detect consecutive sequences by comparing adjacent elements and grouping them efficiently in a single pass.
Yes, variations of range grouping and interval detection problems appear in FAANG-style interviews. They test your ability to recognize patterns in arrays and implement efficient single-pass solutions.
An array traversal with simple variables or two pointers is sufficient for this problem. Since the input is already sorted and unique, no additional data structures like hash maps or sets are required.
The optimal approach is a linear scan of the sorted array while tracking the start of each range. When consecutive numbers continue, extend the range; when they break, record the range and start a new one. This ensures O(n) time complexity.
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.