Leetcode Study Day 23

Summary Ranges

You are given a sorted unique integer array nums. A range [a,b] is the set of all integers from a to b (inclusive).

Return the smallest sorted list of ranges that cover all the numbers in the array exactly. That is, each element of nums is covered by exactly one of the ranges, and there is no integer x such that x is in one of the ranges but not in nums.

Each range [a,b] in the list should be output as:

“a->b” if a != b
“a” if a == b

Example 1:

Input: nums = [0,1,2,4,5,7]
Output: ["0->2","4->5","7"]
Explanation: The ranges are:
[0,2] --> "0->2"
[4,5] --> "4->5"
[7,7] --> "7"
Example 2:

Input: nums = [0,2,3,4,6,8,9]
Output: ["0","2->4","6","8->9"]
Explanation: The ranges are:
[0,0] --> "0"
[2,4] --> "2->4"
[6,6] --> "6"
[8,9] --> "8->9"

My solution

My solution is redundant and not elegant. I use two pointers to record the first and last number of a range. If the next number is not the next number of the last number, then I push the range to the answer vector. If the next number is the next number of the last number, then I update the last number. If the last number is the last number of the array, then I push the range to the answer vector. If the array is empty, then I return an empty vector. If the array only has one number, then I return a vector with only one element.

class Solution {
public:
    vector<string> summaryRanges(vector<int>& nums) {
        int n = nums.size();
        vector<string> ans;
        string single_ans = "";
        if (nums.empty()){
            return ans;
        }
        int first = nums[0];
        int last = nums[0] ;
        if (nums.size() == 1){
            ans.push_back(to_string(nums[0]));
            return ans;
        }
        for (int i = 0; i < n-1; i ++){
            if(nums[i+1] != nums[i] + 1 && first != last){
                single_ans = to_string(first) + "->" + to_string(last);
                ans.push_back(single_ans);
                first = last = nums[i+1];
            }
            else if (nums[i+1] != nums[i] + 1 && first == last){
                single_ans = to_string(first);
                ans.push_back(single_ans);
                first = last = nums[i+1];
            }
            else{
                last++;
            }
        }
        if (nums[n-1] != nums[n-2]+1)
            ans.push_back(to_string(nums[n-1]));
        else
            ans.push_back(to_string(first) + "->" + to_string(last));
        return ans;
    }
};

Solution from Leetcode

A solution with similar idea but more elegant shows below:

class Solution {
public:
    vector<string> summaryRanges(vector<int>& arr) {
        int n = arr.size(); // extracting size of the array
        vector<string> ans; // declaring answer array to store our answer
        
        string temp = ""; // temproray string that stores all possible answer
        
        for(int i = 0; i < n; i++) // start traversing from the array
        {
            int j = i; // declare anthor pointer that will move
            
            // run that pointer until our range is not break
            while(j + 1 < n && arr[j + 1] == arr[j] + 1)
            {
                j++;
            }
            
            // if j > i, that means we got our range more than one element
            if(j > i)
            {
                temp += to_string(arr[i]); // first store starting point
                temp += "->"; // then store arrow, as question wants it
                temp += to_string(arr[j]); // and lastly store the end point
            }
            else // we got only one element as range
            {
                temp += to_string(arr[i]); // then store that element in temp
            }
            
            ans.push_back(temp); // push one possible answer string to our answer
            temp = ""; // again reintiliaze temp for new possible answers
            i = j; // and move i to j for a fresh start
        }
        
        return ans; // and at last finally return the answer array
    }
};

In his code, he doesn’t need to check if the array is empty or only has one element. He uses a while loop to check if the next number is the next number of the last number. If it is, then he updates the last number. If it is not, then he pushes the range to the answer vector.