Understanding an overflow issue in Java

Question

Given a sorted integer array without duplicates, return the summary of its ranges for consecutive numbers.

For example, given [0,1,2,4,5,7], return ["0->2","4->5","7"].

I proposed the following solution:

public List<String> summaryRanges(int[] nums) {
    if (nums == null){
        return null;
    }
    if (nums.length == 0){
        return new ArrayList<>();
    }
    if (nums.length == 1){
        List<String> arr = new ArrayList<>();
        arr.add(Integer.toString(nums[0]));
        return arr;
    }

    List<String> summary = new ArrayList<>();
    int n = nums.length;
    int begin = nums[0];
    int end;

    for (int i = 1; i < n; i++) {
        if (nums[i] - nums[i-1] > 1) {
            end = nums[i-1];
            if (begin == end){
                summary.add(Integer.toString(begin));

            }
            else{
                summary.add(Integer.toString(begin) + "->" + Integer.toString(end));
            }
            begin = nums[i];
        }
    }
    if (nums[n-1] - nums[n-2] > 1){
        summary.add(Integer.toString(nums[n-1]));
    }
    else{
        summary.add(Integer.toString(begin) + "->" +Integer.toString(nums[n-1]));
    }

    return summary;
}

This program fails for the following example: [-2147483648, -2147483647, 2147483647] (returns the wrong answer: ["-2147483648->2147483647"])

I suspect this is due to an overflow issue, but I can't figure out why exactly. On the opposite, this example solution I found passes this test case:

public List<String> summaryRanges(int[] nums) {
    List<String> result = new ArrayList<String>();

    if(nums == null || nums.length==0)
        return result;

    if(nums.length==1){
        result.add(nums[0]+"");
    }

    int pre = nums[0]; // previous element   
    int first = pre; // first element of each range

    for(int i=1; i<nums.length; i++){
            if(nums[i]==pre+1){
                if(i==nums.length-1){
                    result.add(first+"->"+nums[i]);
                }
            }else{
                if(first == pre){
                    result.add(first+"");
                }else{
                    result.add(first + "->"+pre);   
                }

                if(i==nums.length-1){
                    result.add(nums[i]+"");
                }

                first = nums[i];
            }

            pre = nums[i];
    }

    return result;
}

Why does this solution pass this test and not the one I proposed?

Answer 1

Yes, indeed, the problem is overflow.

The difference between your programs is, basically, that you are using the test:

nums[i] - nums[i-1] > 1

whereas the other program uses

nums[i]==pre+1

In a purely mathematical world, there should be no difference between comparing y to x+1 and comparing y-x to 1, but in the world of 32-bit integer, there is a big difference.

When you get to the numbers -Integer.MAX_VALUE and Integer.MAX_VALUE, which is what the numbers in your example array are, then your comparison is:

Integer.MAX_VALUE - -Integer.MAX_VALUE > 1

As the minus signs cancel each other, this means 2 * Integer.MAX_VALUE, which is larger than an int can hold, and you get an overflow. The result is -2 and that's not greater than 1.

In the other program's way, you would be asking whether

Integer.MAX_VALUE == - Integer.MAX_VALUE + 1

The left hand part is, of course, a legal integer. The right hand value is also a legal integer, because you are just stepping away from the minimum. Thus, no overflow, and the comparison would return false, which is good.

Answer 2

Can you try using absolute values wherever checking the differences:

Math.abs(nums[i]) - Math.abs(nums[i-1])

I suppose this looks like an issue here in case of negative numbers.