Return to Answer

public int[] plusOne(int[] digits) {
 int len = digits.length;
 if (len == 0)
 return digits;
 for (int i = len - 1; i >= 0; i--) {
 if (digits[i] == 9) {
 digits[i] = 0;
 } else {
 digits[i]++;
 return digits;
 }
 }
 return resize(digits, len + 1);
}

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

public int[] plusOne(int[] digits) {
 int len = digits.length;
 if (len == 0)
 return digits;
 for (int i = len - 1; i >= 0; i--) {
 if (digits[i] == 9) {
 digits[i] = 0;
 } else {
 digits[i]++;
 return digits;
 }
 }
 return newArray(len + 1);
}

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

This uses the same algorithm, but with less instructions:

Benchmark

Benchmark Mode Cnt Score Error Units
Test.fill avgt 5 1827.012 ▒ 13.510 ns/op
Test.new_10000x9 avgt 5 12594.067 ▒ 81.100 ns/op
Test.new_mix avgt 5 3.979 ▒ 0.030 ns/op
Test.original_10000x9 avgt 5 15871.266 ▒ 144.449 ns/op
Test.original_mix avgt 5 4.234 ▒ 0.039 ns/op

The fill test case was just to figure out the approximate overhead of resetting the array to 9's in the 10000x9 test iterations. If we remove that initialization time, we conclude that in the 10000x9 test case there was a 23% cut on the execution time.

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

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[] resize(int[] arr, int size) {
 int[] copy = new int[size];
 copy[0] = 1;
 return copy;
}

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

Benchmark

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.

Simpler solution

You can simplify a lot the iteration through the digits. This uses the same algorithm, but with less instructions:

public int[] plusOne2(int[] digits) {
 int len = digits.length;
 if (len == 0)
 return digits;
 int carry = 1;
 for (int i = len - 1; i >= 0; i--) {
 if (digits[i] == 9) {
 carry = 1;
 digits[i] = 0;
 } else {
 digits[i]++;
 break;
 }
 }
 if (carry == 1) {
 return resize(digits, len + 1);
 }
 return digits;
}

Input data sets=:

• "mixed": {1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 2, 3}
• "12x9": {9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9}

Benchmark Mode Cnt Score Error Units
Test.new_12x9 avgt 5 18.005 ▒ 0.987 ns/op
Test.original_12x9 avgt 5 4.330 ▒ 0.127 ns/op
Test.new_mix avgt 5 17.989 ▒ 0.505 ns/op
Test.original_mix avgt 5 4.373 ▒ 0.176 ns/op

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:

public int[] plusOne(int[] digits) {
 int len = digits.length;
 if (len == 0)
 return digits;
 for (int i = len - 1; i >= 0; i--) {
 if (digits[i] == 9) {
 digits[i] = 0;
 } else {
 digits[i]++;
 return digits;
 }
 }
 return resize(digits, len + 1);
}

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.

Benchmark Mode Cnt Score Error Units
Test.fill  avgt 5  1827.012 ▒  13.510 ns/op
Test.new_10000x9  avgt 5 12594.067 ▒  81.100 ns/op
Test.new_mix avgt 5  3.979 ▒ 0.030 ns/op
Test.original_10000x9 avgt 5 15871.266 ▒ 144.449 ns/op
Test.original_mix avgt 5 4.234 ▒ 0.039 ns/op

The fill test case was just to figure out the approximate overhead of resetting the array to 9's in the 10000x9 test iterations. If we remove that initialization time, we conclude that in the 10000x9 test case there was a 23% cut on the execution time.