Plus One - Video Solutions

Problem Overview: You receive a non-empty array where each element represents a digit of a non‑negative integer. The digits are stored in order from most significant to least significant. The task is to add one to the integer and return the resulting array of digits without converting it into a built-in large integer type.

This problem mainly tests how you handle carry propagation in an array. When the last digit becomes 10 after adding one, the carry must move left across digits until a non‑9 digit is found or a new leading digit is created.

Approach 1: Iterative Backtracking Approach (Carry Propagation) (Time: O(n), Space: O(1))

This approach processes the digits from right to left, mimicking how addition works manually. Start at the last index and increment the digit. If the digit becomes less than 10, the operation is complete and the array can be returned immediately. When the digit becomes 10 (meaning the original value was 9), reset it to 0 and propagate the carry to the next digit on the left.

The key insight is that only trailing 9s require carry propagation. The moment a digit less than 9 is found, incrementing it resolves the entire operation. If the loop finishes and every digit was a 9 (for example [9,9,9]), create a new array with a leading 1 followed by zeros. This solution directly manipulates the array and avoids unnecessary conversions, making it the optimal approach for problems involving digit operations in math and array manipulation.

Approach 2: Convert Array to Number Approach (Time: O(n), Space: O(n))

This method first converts the array of digits into a numeric value or string representation, increments the number, and then converts the result back into an array of digits. In languages with arbitrary precision integers (like Python), this can be implemented in just a few lines.

The drawback is scalability. For very large arrays, converting the digits to a number may exceed integer limits in some languages or introduce unnecessary overhead. Additional memory is also required to rebuild the resulting array. While this approach works for small inputs and quick scripting tasks, it does not demonstrate control over digit-level operations.

Recommended for interviews: The iterative carry propagation approach is what interviewers expect. It demonstrates understanding of digit arithmetic, in-place array traversal, and edge cases such as sequences of trailing 9s. Mentioning the conversion approach shows awareness of simpler alternatives, but implementing the in-place carry logic proves stronger algorithmic thinking.