LeetCode Notes: Summary Ranges

#leetcode

Question

You are given a sorted unique integer array nums.

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"

Example 3:

Input: nums = []

Output: []

Example 4:

Input: nums = [-1]

Output: ["-1"]

Example 5:

Input: nums = [0]

Output: ["0"]

Constraints:

  • 0 <= nums.length <= 20
  • -231 <= nums[i] <= 231 - 1
  • All the values of nums are unique.
  • nums is sorted in ascending order.

Solution

Analysis:

Use the reduce method to traverse the entire array. The key is to compare whether the current number is 1 greater than the previous number. Only when it is greater than 1, the current number and the previous number are in the same combination, otherwise, a new array must be created.

Code:

/**
 * @param {number[]} nums
 * @return {string[]}
 */
var summaryRanges = function(nums) {

    // In special cases, return an empty array directly
    if(nums.length === 0) return nums;

    // Set a temporary array to store a complete array range, initialized to the first number
    let preArr = [nums[0]];

    // Result array
    const resultArr = [];

    // Use reduce to easily compare the current number with the previous number
    nums.reduce((pre,cur)=>{
        
        // Only the current number is incremented by 1 from the previous number, it belongs to the same complete range
        if(pre + 1 === cur){
            preArr.push(cur);
        }else{
            // Otherwise, you need to store the last complete range into the result array, and then reinitialize a new complete range
            resultArr.push(preArr);
            preArr = [cur];
        }
        
        // The current number must be returned in order to pass the current number to the next loop for comparison
        return cur

    })

    // The last complete range is not intercepted in the reduce loop above, so it is stored separately here
    resultArr.push(preArr)

    // call the conversion method
    return transformArr(resultArr);

    // Conversion method
    // Convert the array to the format required by the question
    // [1,2,3] => '1->3'
    // [1] => '1'
    function transformArr(arr){
        return arr.map((cur,index)=>{
            if(cur.length === 1){
                return cur.shift()+''
            }else{
                return cur.shift() +'->' + cur.pop()
            }
        })
    }

};

Reference

Comments