No carry
The last digit is less than 9. A single increment finishes the operation — no propagation needed.
Carry propagation, right to left.
A mechanical odometer clicks over from 0999 to 1000 — the rightmost wheel advances, and if it rolls past 9, it triggers the next wheel left. Incrementing a digit array works the same way: walk from the last digit backward, adding one. If a digit stays below 10, stop immediately. If every digit overflows (all nines), prepend a new leading 1. O(n) worst case. O(1) typical.
Watch the algorithm run
Carry Propagation
Start at the rightmost digit and try to add one. If the digit is less than 9, increment it and stop — no carry. If the digit is 9, it becomes 0 and the carry moves left. This chain continues until a digit absorbs the carry or we run out of digits.
The Algorithm
Walk the digit array from right to left. Most of the time only the last digit changes. The carry propagates only through consecutive nines.
-
1
Start from the last digit
Scan right to left. If the current digit is less than 9, increment it and return immediately.
-
2
Handle carry
If the digit is 9, set it to 0 and continue to the next digit to the left — the carry propagates.
-
3
Handle full carry-out
If every digit was 9, prepend a 1 to an array of all zeros. Example:
[9, 9, 9]→[1, 0, 0, 0].
The All-Nines Case
Understanding boundary behavior is as important as the main algorithm path.
Full carry-out
Every digit is 9. The carry propagates through all positions, creating a new leading 1. The result array is one element longer.
Complexity
Time: O(n) worst case — when all digits are 9.
Space: O(n) worst case — if the array must expand.
Otherwise O(1) extra.