228. Summary Ranges - cocoder39/coco39_LC GitHub Wiki

228. Summary Ranges

the inner while loop finds the end of each range, simplify the logic

class Solution:
    def summaryRanges(self, nums: List[int]) -> List[str]:
        n = len(nums)

        i = 0
        res = []
        while i < n:
            left = i
            while i + 1 < n and nums[i+1] == nums[i] + 1:
                i += 1
            if i > left:
                res.append(str(nums[left]) + '->' + str(nums[i]))
            else:
                res.append(str(nums[left]))
            i += 1
        return res

below solution is hard to manage compared with above one. need to deal with edge case eg last segment

class Solution:
    def summaryRanges(self, nums: List[int]) -> List[str]:
        n = len(nums)
        if n == 0:
            return []
        if n == 1:
            return [str(nums[0])]
        
        left = nums[0]
        res = []
        for right in range(1, n):
            if nums[right] > nums[right-1] + 1:
                if nums[right-1] != left:
                    res.append(str(left) + '->' + str(nums[right-1]))
                else:
                    res.append(str(left))
                left = nums[right]
        
        if nums[n-1] > nums[n-2] + 1:
            res.append(str(nums[n-1]))
        else:
            res.append(str(left) + '->' + str(nums[n-1]))
        return res

=============================================

class Solution {
public:
    vector<string> summaryRanges(vector<int>& nums) {
        int sz = nums.size();
        if (sz == 0) {
            return {};
        }
        
        vector<string> res;
        int start = 0;
        for (int i = 0; i < sz; i++) {
            if (i > 0 && nums[i] > nums[i - 1] + 1) {
                format(res, nums, start, i - 1);
                start = i;
            }
        }
        format(res, nums, start, sz - 1);
        return res;
    }
private:
    void format(vector<string>& res, vector<int>& nums, int start, int end) {
        if (start == end) {
            res.push_back(to_string(nums[start]));
        } else {
            res.push_back(to_string(nums[start]) + "->" + to_string(nums[end]));
        }
    }
};

follow up 1 : what if there exists duplicates

if (nums[start] == nums[end]) {
            res.push_back(to_string(nums[start]));
        }

follow up 2: neighbor elements within a range have equal difference

eg. [1, 2, 3, 5, 5, 8, 9, 13, 17, 19] -> [1->3/1], [5], [8->9/1], [13->17/4], [19]

class Solution {
public:
    vector<string> summaryRanges(vector<int>& nums) {
        int sz = nums.size();
        if (sz == 0) {
            return {};
        } 

        vector<string> res;
        int start = 0;
        for (int i = 0; i < sz; i++) {
            if (i > 0 && nums[i] - nums[i - 1] != nums[start + 1] - nums[start]) { //i >= 1
                format(res, nums, start, i - 1); 
                start = i; //works like resize the array such that only consider 
            } 
        }
        format(res, nums, start, sz - 1); //handle sz == 1/2
        return res;
    }
private:
    void format(vector<string>& res, vector<int>& nums, int start, int end) {
        if (nums[start] == nums[end]) { 
            res.push_back(to_string(nums[start]));
        } else {
            res.push_back(to_string(nums[start]) + "->" + to_string(nums[end]) + "/" + to_string(nums[end] - nums[end - 1]));
        }
    }
};
⚠️ **GitHub.com Fallback** ⚠️