Add to Array-Form of Integer

How it works

We can avoid the explicit reverse operation by inserting digits at the front of our result as we compute them. Using a deque (double-ended queue) or linked list allows O(1) insertion at the front.

The logic remains the same: process from right to left, compute each digit with the carry, and build the result. The difference is just in how we construct the output to avoid a final reversal step.

Steps

1. Initialize a deque or linked list for the result, and set carry = 0.
2. Start from the last index of num and the last digit of k.
3. While there are digits remaining in num, digits remaining in k, or carry > 0:
   • Compute sum = carry + num[i] (if valid) + k % 10.
   • Insert sum % 10 at the front of the result.
   • Update carry = sum / 10.
   • Move to the next digit: decrement i and divide k by 10.
4. Return the result as a list.

Complexity

• Time complexity: O(max(n, m))
• Space complexity: O(n)

Where n is the size of the array num and m is the number of digits in k.

Things to watch for

Forgetting the Final Carry

After processing all digits of the array and k, there may still be a remaining carry. Forgetting to handle this results in incorrect answers for cases like [9,9,9] + 1 = [1,0,0,0].

Processing Digits in Wrong Order

The array stores the most significant digit first, but addition needs to start from the least significant digit. Forgetting to process from right to left (or reverse the array) produces wrong results.

from typing import List

class Solution:
    def addToArrayForm(self, num: List[int], k: int) -> List[int]:
        from collections import deque
        result = deque()
        i = len(num) - 1
        carry = 0

        while i >= 0 or k > 0 or carry > 0:
            digit = k % 10
            sum_val = carry + (num[i] if i >= 0 else 0) + digit

            result.appendleft(sum_val % 10)
            carry = sum_val // 10

            k //= 10
            i -= 1

        return list(result)

class Solution {
public:
    vector<int> addToArrayForm(vector<int>& num, int k) {
        list<int> result;
        int carry = 0, i = num.size() - 1;

        while (i >= 0 || k > 0 || carry > 0) {
            int digit = k % 10;
            int sum = carry + (i >= 0 ? num[i] : 0) + digit;

            result.push_front(sum % 10);
            carry = sum / 10;

            k /= 10;
            i--;
        }

        return vector<int>(result.begin(), result.end());
    }
};