Add 1 to an integer represented as an array of digits
Simpler implementation

You can simplify a lot the iteration through the digits. Resizing with an ArrayList would definitely be worse, as it's simply a wrapper of an array and you would need to box/unbox the ints to Integer.

This uses the same algorithm, but with less instructions and it will therefore be a bit faster:

public int[] plusOne(int[] digits) {
  int len = digits.length;
  if (len == 0)
    return digits;

  for (int i = len - 1; i &gt;= 0; i--) {
    if (digits[i] == 9) {
      digits[i] = 0;
    } else {
      digits[i]++;
      return digits;
    }
  }

  return newArray(len + 1);
}


New array

In the case where we create a new array, we know that it will be filled by a 1 followed by all zeros. Since in Java all variables not explicitly initialized have their default values (0 in case of int), we can simply do:

private int[] newArray(int size) {
  int[] arr = new int[size];
  arr[0] = 1;
  return arr;
}


This will save us one read and one write for every position.

Benchmark

I did a test with JMH, comparing both solutions. 

Parameters:

# Warmup: 5 iterations, 1 s each
# Measurement: 5 iterations, 1 s each
# Benchmark mode: Average time, time/op


Input data sets:


"mixed": Starts with {0,0,0,0,0,0,0,0,0,0}, and gets increased in every iteration;
"10000x9": It's an array composed of 10 000 '9's, like {9, 9, 9, 9, ...}. This is reset back to all-9s in every iteration.


Results:

Benchmark              Mode  Cnt      Score     Error  Units
Test.fill              avgt    5   1852.195 ▒ 101.178  ns/op
Test.new_10000x9       avgt    5   8793.836 ▒ 176.757  ns/op
Test.new_mix           avgt    5      3.957 ▒   0.040  ns/op
Test.original_10000x9  avgt    5  15761.188 ▒  46.132  ns/op
Test.original_mix      avgt    5      4.209 ▒   0.026  ns/op


The fill test case was just to figure out the approximate overhead of resetting the array to 9's in the 10000x9 tests. If we remove that time from the results of the 10000x9 test cases, we see that the new implementation is about twice as fast.