163-Missing Ranges

// LeetCode URL: https://leetcode.com/problems/missing-ranges/

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * This soultion will work if the numbers in nums array are guaranteed to be in
 * [lower, upper] range.
 *
 * Time Complexity: O(N)
 *
 * Space Complexity: O(N)
 *
 * N = Length of nums array.
 */
class Solution1 {
    public List<String> findMissingRanges(int[] nums, int lower, int upper) {
        List<String> result = new ArrayList<>();
        if (lower > upper) {
            return result;
        }
        if (nums == null || nums.length == 0) {
            result.add(getRangeStr(lower, upper));
            return result;
        }
        if (lower == upper) {
            int idx = Arrays.binarySearch(nums, lower);
            if (idx < 0) {
                result.add(getRangeStr(lower, upper));
            }
            return result;
        }

        int nextStart = lower;

        for (int n : nums) {
            // Skip the current number if it is less than the next starting number
            if (n < nextStart) {
                continue;
            }

            // Current number is part of the range, increment the missing range starting
            // number.
            if (n == nextStart) {
                if (n == Integer.MAX_VALUE) {
                    return result;
                }
                nextStart++;
                continue;
            }

            result.add(getRangeStr(nextStart, n - 1));

            if (n == Integer.MAX_VALUE) {
                return result;
            }

            nextStart = n + 1;
        }

        // Create the range for the numbers missing between the last number in nums
        // array and upper limit.
        if (nextStart <= upper) {
            result.add(getRangeStr(nextStart, upper));
        }

        return result;
    }

    private String getRangeStr(int s, int e) {
        if (s == e) {
            return String.valueOf(s);
        }
        return s + "->" + e;
    }
}

/**
 * This soultion will work if the numbers in nums array are in
 * [Integer.MIN_VALUE, Integer.MAX_VALUE] range but may be out of [lower, upper]
 * range.
 *
 * Time Complexity: O(N)
 *
 * Space Complexity: O(N)
 *
 * N = Length of nums array.
 */
class Solution2 {
    public List<String> findMissingRanges(int[] nums, int lower, int upper) {
        List<String> result = new ArrayList<>();
        if (lower > upper) {
            return result;
        }
        if (nums == null || nums.length == 0) {
            result.add(getRangeStr(lower, upper));
            return result;
        }
        if (lower == upper) {
            int idx = Arrays.binarySearch(nums, lower);
            if (idx < 0) {
                result.add(getRangeStr(lower, upper));
            }
            return result;
        }

        int nextStart = lower;

        for (int n : nums) {
            if (n < nextStart) {
                continue;
            }
            if (n == nextStart) {
                if (n == upper) {
                    return result;
                }
                nextStart++;
                continue;
            }

            result.add(getRangeStr(nextStart, Math.min(upper, n - 1)));

            if (upper <= n) {
                return result;
            }
            nextStart = n + 1;
        }

        if (nextStart <= upper) {
            result.add(getRangeStr(nextStart, upper));
        }

        return result;
    }

    private String getRangeStr(int s, int e) {
        if (s == e) {
            return String.valueOf(s);
        }
        return s + "->" + e;
    }
}