228. Summary Ranges

Intuition

Given a sorted unique integer array, we need to find contiguous ranges of numbers and represent them in a specific format. If a range consists of consecutive numbers, we represent it as "a->b". If it's a single number, it's represented as just "a".

Approach

1. Edge Case Handling: If the input array nums is empty, return an empty list immediately.
2. Initialization: Initialize variables to track the start (start) and end (end) of a range.
3. Iterate through the Array: Traverse through the sorted array nums. - If the current number nums[i] is consecutive to end + 1, update end to nums[i]. - If it's not consecutive, push the current range (start to end) to the result list in the required format and update start and end to nums[i].
4. Final Range: After the loop, add the last remaining range (start to end) to the result list.
5. Return Result: Return the list of ranges.

Complexity

Time Complexity:

O(n), where n is the number of elements in the input array nums. We iterate through the array once.

Space Complexity:

O(1) additional space complexity for storing variables (start, end) and O(n) space complexity for the output list in the worst case, where n is the number of ranges (if each number forms a separate range).

Code

C++

class Solution {
public:
    vector summaryRanges(vector& nums) {
        vector result;
        if (nums.empty()) return result;
        int start = nums[0];
        for (int i = 1; i <= nums.size(); ++i) {
            if (i < nums.size() && nums[i] == nums[i-1] + 1)
                continue;
            if (start == nums[i-1]) {
                result.push_back(to_string(start));
            } else {
                result.push_back(to_string(start) + "->" + to_string(nums[i-1]));
            }
            if (i < nums.size()) {
                start = nums[i];
            }
        }
        return result;
    }
};

Python

class Solution:
    def summaryRanges(self, nums: List[int]) -> List[str]:
        result = []
        if not nums:
            return result
        start = nums[0]
        for i in range(1, len(nums)):
            if nums[i] != nums[i - 1] + 1:
                if start == nums[i - 1]:
                    result.append(str(start))
                else:
                    result.append(f"{start}->{nums[i - 1]}")
                start = nums[i]
        if start == nums[-1]:
            result.append(str(start))
        else:
            result.append(f"{start}->{nums[-1]}")
        return result

Java

class Solution {
    public List summaryRanges(int[] nums) {
        List result = new ArrayList<>();
        if (nums.length == 0) {
            return result;
        }
        int start = nums[0];
        for (int i = 1; i <= nums.length; i++) {
            if (i < nums.length && nums[i] == nums[i - 1] + 1) {
                continue;
            }
            if (start == nums[i - 1]) {
                result.add(String.valueOf(start));
            } else {
                result.add(start + "->" + nums[i - 1]);
            }
            if (i < nums.length) {
                start = nums[i];
            }
        }
        return result;
    }
}

JavaScript

var summaryRanges = function(nums) {
    let result = []
    let start = nums[0]
    for(let i=1; i <= nums.length; i++) {
        if(nums[i] - nums[i-1] == 1) continue
        if(start == nums[i-1]) {
            result.push(`${start}`)
        } else {
            result.push(`${start}->${nums[i-1]}`)
        }
        start = nums[i]
    }
    return result
}