0228.md

228. Summary Ranges

Level:

Topic:

Question

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.

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"

Intuition

• while the current +1 == next
• if the pointers are not equal, add the start -> current to string
• else, only the start

Code

Time: O(n)
Space: O(1)

public List<String> summaryRanges(int[] nums) {
    List<String> ans = new ArrayList<>();
    int n = nums.length;
    for (int i = 0, j = 0; i < n; i++) {
        j = i;
        while (i+1 < n && nums[i]+1 == nums[i+1])
            i++;

        if (i > j)
            ans.add(nums[j] + "->" + nums[i]);
        else
            ans.add(String.valueOf(nums[j]));
    }
    return ans;
}