[LeetCode] 163. Missing Ranges

Posted on | In

Problem

Given a sorted integer array nums, where the range of elements are in the inclusive range [lower, upper], return its missing ranges.

Example:

1
2
Input: nums = [0, 1, 3, 50, 75], lower = 0 and upper = 99,
Output: ["2", "4->49", "51->74", "76->99"]

Explanation

  1. First check if the array is empty. If it’s empty, then check if lower and upper the same. If the same, we return either lower or upper. Else we return the range from lower to upper.

  2. Next, we check if lower is less than the first element of the array. If it is, then we check if nums[0] - lower == 1. If their difference is equal to 1, we return lower. Else, we return the range from lower to nums[0] - 1.

  3. Next, loop from index i from 1 to nums.length() exclusive. Compare the current element nums[i] with its previous element nums[i-1]. If the difference is greater than 1, or current element is greater than its previous element and their difference is less than 0, in the case of the difference is overflow [-2147483648, 2147483647]. Then we check if the difference is equal to 2, then just add nums[i]-1 to the result list. Else we add the range of lower bound plus 1 to upper bound minus 1 to the result list, in other words, nums[i-1] + 1 to nums[i]-1.

  4. Next, we check upper is greater than the last element of the array. Then, if their difference is 1, we just add upper to the result list. Else, we add the range of nums[nums.length-1] + 1 to upper to the result list. At the end, return the result list.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
    public List<String> findMissingRanges(int[] nums, int lower, int upper) {
        List<String> res = new ArrayList<>();

        if (nums.length == 0) {
            if (lower == upper) {
                res.add(String.valueOf(lower));
                return res;
            } else {
                res.add(lower + "->" + upper);
                return res;
            }
        }

        if (lower < nums[0]) {
            if (nums[0] - lower == 1) {
                res.add(String.valueOf(lower));
            } else {
                res.add(String.valueOf(lower) + "->" + (nums[0] - 1));
            }
        }

        for (int i = 1; i < nums.length; i++) {
            if (nums[i] - nums[i - 1] > 1 ||
                (nums[i] > nums[i - 1] && nums[i] - nums[i - 1] < 0)) {
                if (nums[i] - nums[i - 1] == 2) {
                    res.add(String.valueOf(nums[i] - 1));
                } else {
                    res.add(nums[i - 1] + 1 + "->" + (nums[i] - 1));
                }
            }
        }

        if (upper > nums[nums.length - 1]) {
            if (upper - nums[nums.length - 1] == 1) {
                res.add(String.valueOf(upper));
            } else {
                res.add((nums[nums.length - 1] + 1) + "->" + upper);
            }
        }

        return res;
    }
}