Summary Ranges
Easy · Arrays & Hashing · Explanation and code example
Scan Consecutive Runs
How it works
The sorted distinct input splits into maximal runs of consecutive values. Scan each run once, remembering its first and last values. Emit one number for a singleton and a start->end string for a longer run.
Steps
- Remember the first value of a run.
- Advance while the next value differs by one.
- Format the run and continue at the next unconsumed value.
Complexity
- Time: O(n), excluding integer formatting proportional to output characters.
- Space: O(1) working space plus output.
Things to watch for
- The input is sorted with no duplicates.
- A singleton has no arrow.
- Avoid overflowing a boundary value when checking adjacency in C++.
Python code example
class Solution:
def summaryRanges(self, nums: list[int]) -> list[str]:
ans = []
i = 0
while i < len(nums):
begin = nums[i]
while i < len(nums) - 1 and nums[i] == nums[i + 1] - 1:
i += 1
end = nums[i]
if begin == end:
ans.append(str(begin))
else:
ans.append(str(begin) + "->" + str(end))
i += 1
return ans
C++ code example
class Solution {
public:
vector<string> summaryRanges(vector<int>& nums) {
vector<string> ans;
for (int i = 0; i < nums.size(); ++i) {
const int begin = nums[i];
while (i + 1 < nums.size() && nums[i] == nums[i + 1] - 1)
++i;
const int end = nums[i];
if (begin == end)
ans.push_back(to_string(begin));
else
ans.push_back(to_string(begin) + "->" + to_string(end));
}
return ans;
}
};
Source and license
Explanation by LC Tracker. Code adapted from walkccc / Peng-Yu Chen · MIT license. Node types are supplied by LeetCode where needed.