Summary Ranges
LeetCode #228 · Easy · Arrays · C++ solution with worked-out approach and complexity analysis.
Approach
Linear Scan with Range Tracking
Key insight
Since the array is sorted and contains unique elements, consecutive numbers differ by exactly 1. We track the start and end of each range, extending the range when we find consecutive numbers.
Strategy
- 1Handle empty array edge case
- 2Initialize start and end pointers to the first element
- 3For each subsequent element:
- 4After the loop, don't forget to add the last range
Time
O(n)
single pass through the array
Space
O(1)
excluding the output array
Problem description(from LeetCode)
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
Examples
Example 1
- Input:
- nums = [0,1,2,4,5,7]
- Output:
- ["0->2","4->5","7"]
- Note:
- The ranges are: [0,2] --> "0->2" [4,5] --> "4->5" [7,7] --> "7" Input: nums = [0,2,3,4,6,8,9] Output: ["0","2->4","6","8->9"]
Constraints
- •0 <= nums.length <= 20
- •-2^31 <= nums[i] <= 2^31 - 1
- •All the values of nums are unique.
- •nums is sorted in ascending order.
C++ Solution
solution.cpp
class Solution {
public:
vector<string> summaryRanges(vector<int> &nums) {
vector<string> res;
if (nums.empty()) return res;
int start = nums[0], end = nums[0];
for (int i = 1; i < nums.size(); i++) {
if (nums[i] == end + 1) {
end = nums[i];
} else {
if (start == end) res.push_back(to_string(start));
else res.push_back(to_string(start) + "->" + to_string(end));
start = end = nums[i];
}
}
if (start == end) res.push_back(to_string(start));
else res.push_back(to_string(start) + "->" + to_string(end));
return res;
}
};