Summary Ranges [Easy-Medium] — Linear Scan
Advertisement
Problem Statement
Given a sorted unique integer array, return the smallest sorted list of ranges that covers all numbers exactly.
Input: [0,1,2,4,5,7] → Output: ["0->2","4->5","7"]
Solutions
Python
def summaryRanges(nums: list[str]) -> list[str]:
res, i, n = [], 0, len(nums)
while i < n:
start = nums[i]
while i + 1 < n and nums[i+1] == nums[i] + 1:
i += 1
if nums[i] == start:
res.append(str(start))
else:
res.append(f"{start}->{nums[i]}")
i += 1
return res
JavaScript
var summaryRanges = function(nums) {
const res=[];
for(let i=0;i<nums.length;){
const start=nums[i];
while(i+1<nums.length&&nums[i+1]===nums[i]+1)i++;
res.push(nums[i]===start?`${start}`:`${start}->${nums[i]}`);
i++;
}
return res;
};
C++
vector<string> summaryRanges(vector<int>& nums) {
vector<string> res;
for(int i=0;i<nums.size();){
int start=nums[i];
while(i+1<nums.size()&&nums[i+1]==nums[i]+1)i++;
if(nums[i]==start) res.push_back(to_string(start));
else res.push_back(to_string(start)+"->"+to_string(nums[i]));
i++;
}
return res;
}
Complexity
- Time: O(n)
- Space: O(1)
Advertisement