My concise java accepted solution


  • 36
    J
    public class Solution {
        public List<String> findMissingRanges(int[] A, int lower, int upper) {
            List<String> result = new ArrayList<String>();
            int pre = lower - 1;
            for(int i = 0 ; i <= A.length  ; i++){
                int after = i == A.length ? upper + 1 : A[i]; 
                if(pre + 2 == after){
                    result.add(String.valueOf(pre + 1));
                }else if(pre + 2 < after){
                    result.add(String.valueOf(pre + 1) + "->" + String.valueOf(after - 1));
                }
                pre = after;
            }
            return result;
        }
    }

  • 1
    S

    It is very clever to set pre=lower-1. Concise!


  • -5
    W

    You code failed at test case [0,1,50,100] 0, 3, the result is ["2->49","51->99"].
    You did not consider when A[i] beyond upper case in the loop. Leetcode test cases are not correct.


  • 1

    "Given a sorted integer array where the range of elements are [lower, upper] inclusive" , the assumption is in the range.


  • 0
    W

    Opoos, my bad!


  • 3
    C

    good solution, but will fail when lower == Integer.MIN_VALUE


  • 0
    K

    Thanks for sharing the solution. Here's my solution that uses a similar approach.

    public class Solution {
        public List<String> findMissingRanges(int[] nums, int lower, int upper) {
            List<String> list = new LinkedList<String>();
            if(nums.length == 0) {
                missingRange(list,lower-1,upper+1);
                return list;
            }
            
            missingRange(list,lower-1,nums[0]);
            for(int i = 1; i < nums.length; i++) {
                missingRange(list,nums[i-1],nums[i]);
            }
            missingRange(list,nums[nums.length-1],upper+1);
            return list;
        }
        
        public void missingRange(List<String> list, int cur, int next) {
            if(next - cur == 1 || next - cur == 0) return;
            else if(next - cur == 2) list.add((cur+1) + "");
            else list.add(cur+1 + "->" + (next-1));
        }
    }

  • 0
    C

    Very nice solution!
    This is my python implementation based on your code:

    def findMissingRanges(self, nums, lower, upper):
            prev = lower - 1
            ret = []
            for i in xrange(len(nums) + 1):
                nxt = upper + 1 if i == len(nums) else nums[i]
                if prev + 2 == nxt:
                    ret.append('%d' % (prev + 1))
                elif prev + 2 < nxt:
                    ret.append('%d->%d' % (prev + 1, nxt - 1))
                prev = nxt
                
            return ret

  • 5
    G

    Nice solution! I have a similar solution and I think mine is more readable.

    public class Solution {
        public List<String> findMissingRanges(int[] nums, int lower, int upper) {
            List<String> result = new ArrayList<>();
            for (int i = 0; i <= nums.length; i++) {
                int start = i == 0 ? lower : nums[i - 1] + 1;
                int end = i == nums.length ? upper : nums[i] - 1;
                addMissing(result, start, end);
            }
            return result;
        }
        
        public void addMissing(List<String> result, int start, int end) {
            if (start > end) return;
            else if (start == end) result.add(start + "");
            else result.add(start + "->" + end);
        }
    }

  • 2
    2

    Use long instead of int. Or it will fail lower = Integer.MIN_VALUE or upper = Integer.MAX_VALUE

    public class Solution {
        public List<String> findMissingRanges(int[] nums, int lower, int upper) {
            List<String> result = new ArrayList<>();
            for (int i = -1; i < nums.length; i++) {
                long cur = (i == -1) ? (long)lower - 1 : nums[i];
                long next = (i == nums.length - 1) ? (long)upper + 1 : nums[i + 1];
                if (cur + 1 != next) {
                    result.add(parseRange(cur, next));
                }
            }
            return result;
        }
        private String parseRange(long i, long j) {
            StringBuilder sb = new StringBuilder();
            sb.append(i + 1);
            if (i + 2 != j) {
                sb.append("->").append(j - 1);
            }
            return sb.toString();
        }
    }

  • 2
    P

    I rewrite it to cpp

    vector<string> findMissingRanges(vector<int>& nums, int lower, int upper) {
       vector<string> res;
        int pre = lower - 1;
        for(int i = 0 ; i <= nums.size() ; i++){
            int after = i == nums.size() ? upper + 1 : nums[i]; 
            if(pre + 2 == after){
                res.push_back(to_string(pre + 1));
            }else if(pre + 2 < after){
                res.push_back(to_string(pre + 1) + "->" + to_string(after - 1));
            }
            pre = after;
        }
        return res;
    }
    

  • 0
    L

    @jccg1000021953 Really clean and nice code !


  • 1
    N

    @jccg1000021953

    Nice work, because your solution is robust to the new cases that might incur overflow to most of the answers include the most votes answer.

    The new test case Leetcode newly added, and I believe might incur overflow is :

    [2147483647]
    0
    2147483647


  • 0
    N

    @2016trojan
    I have test the lower = Integer.MIN_VALUE or upper = Integer.MAX_VALUE

    I believe your code is valid, but the original post's code still work.

    I believe one of the benefit of original post is that it is robust to overflow.

    And, your code is not correct if following test case given:

    Input:
    [1,1,1]
    1
    1
    Output:
    ["2->0","2->0"]
    Expected:
    []

    You might be my alumni, or from UCLA LOL.
    Anyway, please check you code.


  • 0
    N

    Your code would fail under test case “[-2147483648,-2147483648,0,2147483647,2147483647], -2147483648, 2147483647". Here is my changed version:
    """
    public class Solution {
    public List<String> findMissingRanges(int[] A, int lower, int upper) {
    List<String> result = new ArrayList<String>();
    int pre = lower - 1;
    int i = 0;

        for(; i < A.length; i++){
            int after = A[i];
            if(pre + 2 == after){
                result.add(String.valueOf(pre + 1));
            }else if(pre + 2 < after){
                result.add(String.valueOf(pre + 1) + "->" + String.valueOf(after - 1));
            }
            pre = after;
            if(pre >= upper){
                break;
            }
        }
        if(i == A.length){
            if(pre + 1 == upper){
                result.add(String.valueOf(pre + 1));
            }
            else if(pre + 1 < upper){
                result.add(String.valueOf(pre + 1) + "->" + String.valueOf(upper));
            }
        }
        return result;
    }
    

    }
    """


  • 0
    J

    @nsbdsxh
    good point, but your code would fail under the case
    [0,2147483646,2147483647]
    0
    2147483647, I made a small change:
    ...
    if((i == 0 || pre <= 2147483646) && pre + 2 == after){
    result.add(String.valueOf(pre + 1));
    } else if((i == 0 || pre <= 2147463646) && pre + 2 < after){
    result.add(String.valueOf(pre + 1) + "->" + String.valueOf(after - 1));
    }
    ...


  • 2

    Same idea. To handle extreme cases, change int to long:

    public class Solution {
        public List<String> findMissingRanges(int[] nums, int lower, int upper) {
            List<String> res = new ArrayList<String>(); 
            long p1 = (long)lower-1;
            long p2 = 0;//just a dummy value 
    
            for(int i = 0; i<=nums.length; i++){
                if(i==nums.length) p2 = (long)upper+1; 
                else p2 = nums[i]; 
                
                if(p2==p1+2){
                    res.add(p1+1+""); 
                }else if(p2>p1+2){
                    res.add( (p1+1) + "->" + (p2-1) ); 
                }
                p1 = p2; 
            }
            
            return res; 
        }
    }
    

    Explanation
    This question is about what you have and what you should have. lower and upper is what you should have, nums is what you have. By changing lower to lower - 1, and upper to upper + 1, we converted all our data to what you have. (because you should have lower, but we "have" lower-1)

    Now, loop through all we have, that is [lower-1 --> nums --> upper+1], and properly record all gaps between two consecutive numbers, if necessary. Easy.

    *Man... I actually faced this question in an interview years before... I wish I knew what I know right now...


  • 0
    F

    Very simliar.

    public List<String> findMissingRanges(int[] nums, int lower, int upper) {
        List<String> res = new ArrayList<>();
        long start = lower;
        for (int i = 0; i <= nums.length; i++) {
          long end = (i == nums.length ? (long) upper + 1 : nums[i]);
          if (end > start) {
            if (start + 1 == end)
              res.add(String.valueOf(start));
            else
              res.add(start + "->" + (end - 1));
    
          }
          start = end + 1;
        }
        return res;
      }
    

  • 0
    L

    same idea

    public class Solution {
        public List<String> findMissingRanges(int[] nums, int lower, int upper) {
            List<String> res = new ArrayList<>();
            for(int i = -1; i < nums.length; i++) {
                long left = (i == -1) ? (long)lower - 1 : nums[i];
                long right = (i + 1 == nums.length) ? (long)upper + 1: nums[i + 1];
                String temp = null;
                if(right == 2 + left) {
                    temp = String.valueOf(right - 1);
                } else if(right > 2 + left) {
                    temp = String.valueOf(left + 1) + "->" + String.valueOf(right - 1);
                }
                if(temp != null) {
                    res.add(temp);
                }
            }
            return res;
        }
    }
    

Log in to reply
 

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