Accepted Java solution with explanation


  • 72
    public List<String> findMissingRanges(int[] a, int lo, int hi) {
      List<String> res = new ArrayList<String>();
      
      // the next number we need to find
      int next = lo;
      
      for (int i = 0; i < a.length; i++) {
        // not within the range yet
        if (a[i] < next) continue;
        
        // continue to find the next one
        if (a[i] == next) {
          next++;
          continue;
        }
        
        // get the missing range string format
        res.add(getRange(next, a[i] - 1));
        
        // now we need to find the next number
        next = a[i] + 1;
      }
      
      // do a final check
      if (next <= hi) res.add(getRange(next, hi));
    
      return res;
    }
    
    String getRange(int n1, int n2) {
      return (n1 == n2) ? String.valueOf(n1) : String.format("%d->%d", n1, n2);
    }

  • 0
    T
    This post is deleted!

  • 51
    V

    Without helper function

    public class Solution {
        public List<String> findMissingRanges(int[] nums, int lower, int upper) {
            List<String> list = new ArrayList<String>();
            for(int n : nums){
                int justBelow = n - 1;
                if(lower == justBelow) list.add(lower+"");
                else if(lower < justBelow) list.add(lower + "->" + justBelow);
                lower = n+1;
            }
            if(lower == upper) list.add(lower+"");
            else if(lower < upper) list.add(lower + "->" + upper);
            return list;
        }
    }

  • 0
    V

    Elegent code! Mine is so messy.


  • 9
    8

    I think when upper is less then any element of the array, this answer wouldn't be right.


  • 1
    K

    I think there is a bug when hi is smaller than last number in array, if that is the case, your output will include more ranges.


  • 0
    2

    Really concise and readable C++ implementation !

    The key idea is just to find the next number and record the missing ranges if we can not find the next number !

    Here is the C++ implementation of your idea:

       class Solution {
        public:
            vector<string> findMissingRanges(vector<int>& nums, int lower, int upper) {
                vector<string> ranges;
                int next = lower;
                for (int i = 0; i < nums.size(); i++ ) {
                    //if (nums[i] < next)  continue;
                    if (nums[i] == next) {
                        next ++;
                        continue;
                    }
                    ranges.push_back(getRange(next, nums[i] - 1));
                    next = nums[i] + 1;
                }
                if(next <= upper)  ranges.push_back(getRange(next, upper));
                return ranges;
            }
            
            string getRange(const int lower, const int upper) {
                if (lower == upper) {
                    return to_string(lower);
                } else {
                    return to_string(lower) + "->" + to_string(upper);
                }
            }
        };

  • 3

    They need to add more test cases:

    1. when the input lower is bigger than upper.
    2. when the input lower is smaller than nums[0].
    3. when the input upper is bigger than the last elem in nums.

    The above three could happen all together or mixed.

    If we use "Custom Testcase", the back code of the comparing result handle all these correctly.


  • 2
    L

    Some test cases are not covered in this solution, here is an test case that will fail the code.

    	int[] nums = new int[] { 50, 75 };
    	int lower = 0;
    	int hight = 10;
    

    Expected output: [0->10]
    Actual output: [0->49, 51->74]


  • 2
    W

    To the above two comments:

    "Given a sorted integer array where the range of elements are [lower, upper] inclusive"
    The problem made it clear that the elements will be between lower and upper.
    Of course, the problem statement is not in very elegant wording, like some other problems.


  • 1
    C

    @wei88 Thanks for clarifying.... My code is more than 80 lines to handle all these crazy boundaries...


  • 0
    H

    @vimukthi You may add a nums[i] <= upper in you for loop. Anyway , it's a very good solution, thank you for sharing!


  • 3
    N

    @825800401
    Given a sorted integer array where the range of elements are [lower, upper] inclusive

    So I think this answer is right.

    Although at first I thought it was not as well.


  • 0
    C

    It is a great solution, but in getRange(), why you don't n1 > n2, what if next =a[i]?


  • 4
    G

    @jeantimex

    We need to add the below condition to the final check to pass the solution.

    if(next <= upper && upper != Integer.MAX_VALUE ) res.add(getRange(next, upper));
    

    Please let me know if any one has better ideas. Like changing "next" to long so that it would not go negative.


  • 1
    N

    @JellyDG said in Accepted Java solution with explanation:

    when the input upper is bigger than the last elem in nums.

    1. when the input upper is bigger than the last elem in nuts.
      This test case is still not included in the solution.

    In addition, now the test cases includes Integer.MAX_VALUE, so that current code suffered from overflow problems.


  • 14

    Add two blocks of code to deal with overflow problem:

    public class Solution {
        public List<String> findMissingRanges(int[] nums, int lower, int upper) {
            List<String> res = new ArrayList<>();
            for(int num: nums) {
                // if num is MIN, num - 1 will be MAX
                if(num == Integer.MIN_VALUE) {
                    lower = num + 1;
                    continue;
                }
                
                if(lower < num - 1) res.add(lower + "->" + (num - 1));
                else if(lower == num - 1) res.add(lower + "");
                
                lower = num + 1;
            }
            
            // if the last num is MAX, num + 1 will be MIN
            if(lower == Integer.MIN_VALUE) return res;
            
            if(lower == upper) res.add(lower + "");
            else if(lower < upper) res.add(lower + "->" + upper);
            
            return res;
        }
    }
    

  • 3
    Y

    for case [2147483647], 0, 2147483647, your code overflow.
    add a if statement when you update next:
    if(nums[i] < Integer.MAX_VALUE) next = nums[i]+1;
    else return res;


  • 0
    G

    @kema I have the same idea. I think if(nums[i] > upper) break; this line should be put in the first line when we jump into the loop.


  • 0

    @vimukthi Very clear! Thanks for sharing!


Log in to reply
 

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