Summary Ranges [Easy-Medium] — Linear Scan

Sanjeev SharmaSanjeev Sharma
1 min read

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

Sanjeev Sharma

Written by

Sanjeev Sharma

Full Stack Engineer · E-mopro