Summary Ranges
EasyPrompt
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"ifa != b"a"ifa == 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 - 1- All the values of
numsare unique. numsis sorted in ascending order.
Approaches
2 approaches with complexity analysis and trade-offs.
Iterate through the array and check each element with its next element to find ranges.
Algorithm
- Initialize an empty result list
- For each number in the array:
- Store the current number as start
- While next number is consecutive, increment index
- When non-consecutive number found or end reached:
- If start equals current number, add single number
- Else add range "start->current"
Walkthrough
In this approach, we iterate through the array and for each element, we check if the next element is consecutive (current + 1). If it is consecutive, we continue until we find a non-consecutive element. When we find a non-consecutive element or reach the end of the array, we add the range to our result list.
public List<String> summaryRanges(int[] nums) { List<String> result = new ArrayList<>(); if (nums == null || nums.length == 0) return result; for (int i = 0; i < nums.length; i++) { int start = nums[i]; // Keep iterating while we find consecutive numbers while (i + 1 < nums.length && nums[i] + 1 == nums[i + 1]) { i++; } // Add range to result if (start != nums[i]) { result.add(start + "->" + nums[i]); } else { result.add(String.valueOf(start)); } } return result;}Complexity
Time
O(n) where n is the length of the input array as we need to traverse each element once
Space
O(1) excluding the space required for output
Trade-offs
Pros
Simple and straightforward implementation
Easy to understand
No extra space required except for output
Cons
Not optimized for very large arrays
Requires careful handling of integer overflow cases
Use two pointers to track the start and end of each range while iterating through the array.
Algorithm
- Initialize empty result list
- Use two pointers start and end
- While end pointer hasn't reached array end:
- Move end pointer until non-consecutive number found
- Add range between start and end to result
- Update start and end pointers for next range
Walkthrough
This approach uses two pointers - one to mark the start of a range and another to find the end of the range. We can optimize the previous approach by reducing the number of comparisons and making the code more readable.
public List<String> summaryRanges(int[] nums) { List<String> result = new ArrayList<>(); if (nums == null || nums.length == 0) return result; int start = 0; int end = 0; while (end < nums.length) { // Find the end of current range while (end + 1 < nums.length && nums[end] + 1 == nums[end + 1]) { end++; } // Add range to result if (start == end) { result.add(String.valueOf(nums[start])); } else { result.add(nums[start] + "->" + nums[end]); } // Move to next range end++; start = end; } return result;}Complexity
Time
O(n) where n is the length of the input array
Space
O(1) excluding the space required for output
Trade-offs
Pros
More readable and maintainable code
Reduced number of array accesses
Better handling of range boundaries
Cons
Still requires linear time complexity
May not be as intuitive for beginners
Solutions
Solution
public class Solution { public IList < string > SummaryRanges(int[] nums) { var ans = new List < string > (); for (int i = 0, j = 0, n = nums.Length; i < n; i = j + 1) { j = i; while (j + 1 < n && nums[j + 1] == nums[j] + 1) { ++j; } ans.Add(f(nums, i, j)); } return ans; } public string f(int[] nums, int i, int j) { return i == j ? nums[i].ToString() : string.Format("{0}->{1}", nums[i], nums[j]); }}class Solution { public List < String > summaryRanges ( int [] nums ) { List < String > ans = new ArrayList <>(); for ( int i = 0 , j , n = nums . length ; i < n ; i = j + 1 ) { j = i ; while ( j + 1 < n && nums [ j + 1 ] == nums [ j ] + 1 ) { ++ j ; } ans . add ( f ( nums , i , j )); } return ans ; } private String f ( int [] nums , int i , int j ) { return i == j ? nums [ i ] + "" : String . format ( "%d->%d" , nums [ i ], nums [ j ]); } }class Solution { public: vector < string > summaryRanges ( vector < int >& nums ) { vector < string > ans ; auto f = [ & ]( int i , int j ) { return i == j ? to_string ( nums [ i ]) : to_string ( nums [ i ]) + "->" + to_string ( nums [ j ]); }; for ( int i = 0 , j , n = nums . size (); i < n ; i = j + 1 ) { j = i ; while ( j + 1 < n && nums [ j + 1 ] == nums [ j ] + 1 ) { ++ j ; } ans . emplace_back ( f ( i , j )); } return ans ; } };class Solution : def summaryRanges ( self , nums : List [ int ]) -> List [ str ]: def f ( i : int , j : int ) -> str : return str ( nums [ i ]) if i == j else f ' { nums [ i ] } -> { nums [ j ] } ' i = 0 n = len ( nums ) ans = [] while i < n : j = i while j + 1 < n and nums [ j + 1 ] == nums [ j ] + 1 : j += 1 ans . append ( f ( i , j )) i = j + 1 return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.