https://leetcode.com/problems/summary-ranges/description/

C++

class Solution {
public:
    vector<string> summaryRanges(vector<int>& nums) {
        vector<string> ranges;

        for(int i = 0; i < nums.size(); i++){
            int start = nums[i];
            // Keep iterating until the next elemet is the one more than the current element
            while(i + 1 < nums.size() && nums[i] + 1 == nums[i + 1]){
                i++;
            }

            if (start != nums[i]){
                ranges.push_back(to_string(start) + "->" + to_string(nums[i]));
            }
            else{
                ranges.push_back(to_string(start));
            }
        }
        return ranges;
    }
};

Complexity Analysis

Here $n$ is the number of elements in nums.

• Time complexity: $O(n)$.
  • We iterate over each nums element once, either including it in the current range or creating a new range from it, which takes $O(n)$ time for $n$ elements.
  • We also add all of the ranges to the ranges list. In the worst-case situation, $n$ elements could be added to the list if each consecutive element in nums differs by more than 1, requiring $O(n)$ time to insert all the required ranges.
• Space complexity: $O(1)$.
  • Except for a few integer variables like i and start that use constant space, we do not consume any space (if we ignore the space consumed by the input and output).

Python

def summaryRanges(self, nums: List[int]) -> List[str]:
    intervals = []
    i = 0

    while i < len(nums):
        start = nums[i]
        while i + 1 < len(nums) and nums[i] + 1 == nums[i+1]:
            i += 1
        
        if start != nums[i]:
            intervals.append(f"{start}->{nums[i]}")
        else:
            intervals.append(f"{start}")
        
        i += 1
    return intervals

$Time=O(N)$

$Space=O(1)$