228. Summary Ranges

Question

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"

Constraints:

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

Algorithm

1. Easy question, implement it using two pointers.
2. A few situations to handle :
   1. Single number
      1. Followed with a range
      2. Followed with another single number
   2. Consecutive digits
3. Don't forget to handle the remaining string in the string builder when loop is done

Code

class Solution {
    public List<String> summaryRanges(int[] nums) {
        List<String> res = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return res;
        }
        int left = 0, right = 0;
        StringBuilder sb = new StringBuilder();
        
        while (right < nums.length) {
            if (left == right) {
                sb = new StringBuilder();
                sb.append(nums[right++]);
            } else if (nums[right] == nums[right - 1] + 1) {
                right++;
            } else {
                if (left != right - 1) {
                    sb.append("->").append(nums[right - 1]);  
                }
                res.add(sb.toString());
                left = right;
            }
        }
        
        if (left != right - 1) {
            sb.append("->").append(nums[right - 1]);
        }
        res.add(sb.toString());
        return res;
    }
}