Leetcode: Plus One

Given a non-negative number represented as an array of digits, plus one to the number.

The digits are stored such that the most significant digit is at the head of the list.

Understand the problem:
The problem gives an array of digits, return a new array plus one to the number. Note that the digits are stored such that the most significant digit is at the head of the list. 
We can take several examples to show the problem:
For the input array 123, the new array is 124.
For the input array 99, the new array is 100. 

Solution:
The solution is again very similar to adding the two integers. So we can add from the last digit. Note the carry number after the loop iteration. 

Code (Java):

public class Solution {
    public int[] plusOne(int[] digits) {
        ArrayList<Integer> result = new ArrayList<Integer>();
        if (digits == null || digits.length == 0) {
            int[] temp = {1};
            return temp;
        }
        
        int carry = 0;
        for (int i = digits.length - 1; i >= 0; i--) {
            if (i == digits.length - 1) {
                carry = carry + digits[i] + 1;
            } else {
                carry += digits[i];
            }
            result.add(0, carry % 10);
            carry /= 10;
        }
        
        if (carry == 1) {
            result.add(0, 1);
        }
        int resultArray[] = new int[result.size()];
        for (int i = 0; i < result.size(); i++) {
            resultArray[i] = result.get(i);
        }
        
        return resultArray;
    }
}

Discussion:
The solution itself is correct but not very efficient. In this solution, we need to traverse all digits of the array, no matter if there is a carry value. Actually we know that only if the digit is 9, there is a carry value to consider. So one better idea is to plus one at the original digital array. Then we can safely stop the process as long as there is no carry value. 

Code (Java):

public class Solution {
    public int[] plusOne(int[] digits) {
        if (digits == null || digits.length== 0) {
            int[] temp = {1};
            return temp;
        }
        
        int carry = 1;
        int i;
        for (i = digits.length - 1; i >= 0; i--) {
            if (digits[i] == 9) {
                digits[i] = 0;
            } else {
                carry += digits[i];
                digits[i] = carry;
                break;
            }
        }
        
        if (i < 0) {
            int[] result = new int[digits.length + 1];
            result[0] = 1;
            return result; 
        } else {
            return digits;
        }
    }
}

Summary:
The second solution is smart by not easy to understand at the first glance. Both of the solutions have its pros and cons. In the first solution, we have to iterate all digits of the array no matter if there exists the carry value. However, it does not modify the original array, which is sometimes preferred in certain cases. The second solution is neat but modify the original input array. In addition, the second solution is restricted to only plus one problem, whereas the first solution is more general to any adding two numbers problems. 

So the take-away message is no matter what solution you come out, you need to justify and analyze it.