Short, Concise and Quick JAVA Solution time O(n), with necessary comments


  • 0
    /*
         * Thoughtway:
         * To find missing numbers in a certain range is equal to find gaps (span bigger than 1) between 
         * adjacent values in a number sequence. 
         * The number sequence is formed by (lower - 1) -> nums[0] ->...nums[n] -> (upper + 1);
         *
         * Method:
         * Maintain a "target" as the start value of the next potential missing range, intilize it as value "lower";
         * Check whether the "target" and (nums[0] - 1) could form a valid range. e.g. (0,0), (0, 3) etc.
         * Add the missing range to the result in the right format if found one;
         * Update the "target" value to nums[0] + 1 as the start value of next potential missing range;
         *
         * Corner Case:
         * To prevent overflow when updating "target" value, use long instead of int;
         */
    
    public class Solution {
        public List<String> findMissingRanges(int[] nums, int lower, int upper) {
            List<String> result = new ArrayList<>();
            long target = lower;
            long upper_new = (long)upper + 1;
            for (int i = 0; i <= nums.length; i ++) {
                long num = (i < nums.length ? nums[i] : upper_new);
                if (num > target) {
                    if (num > target + 1) {
                        result.add(target + "->" + (num - 1));
                    } else {
                        result.add(target + "");
                    }
                } 
                target = num + 1;
            }
            return result;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.