Multiply Strings — Solution

Problem

Given two non-negative integers written as strings, return their product also as a string — without converting the inputs to integers or using any big-number library. Think of it as implementing the multiplication you learned in grade school, one digit at a time.

• Input: num1 = "123", num2 = "456"
• Output: "56088"
• Explanation: 123 × 456 = 56,088, returned as the string "56088"

Intuition

When you multiply two numbers by hand, the digit at position i in num1 (from the left) and the digit at position j in num2 always contribute to position i + j + 1 in the result, with any carry going to i + j. That position mapping lets us skip the usual row-by-row addition: accumulate every digit product directly into a result array, then make a single right-to-left pass to fix up the carries.

Solution — Digit Accumulator

Build a result array of size m + n (the maximum digits the product can have). For every pair of digits, add their product to the correct position. Once all pairs are processed, propagate carries from the least significant position outward.

1. Return "0" immediately if either input is "0" to avoid stripping issues later.
2. Allocate a partialProducts array of size m + n, initialized to zero.
3. Iterate over every digit pair (i, j): add digit1 × digit2 to partialProducts[i + j + 1].
4. Walk partialProducts from right to left, carrying the overflow of each cell one position left.
5. Skip partialProducts[0] if it is zero (the product fit in fewer than m + n digits), then join to a string.

1def multiply(num1: str, num2: str) -> str:
2    if num1 == "0" or num2 == "0":
3        return "0"
4
5    m, n = len(num1), len(num2)
6    partial_products = [0] * (m + n)
7
8    for i in range(m - 1, -1, -1):
9        for j in range(n - 1, -1, -1):
10            # digit at i in num1 × digit at j in num2 lands at position i+j+1
11            partial_products[i + j + 1] += int(num1[i]) * int(num2[j])
12
13    for pos in range(m + n - 1, 0, -1):
14        # carry must flow toward more significant digits, so iterate right-to-left
15        partial_products[pos - 1] += partial_products[pos] // 10
16        partial_products[pos] %= 10
17
18    return "".join(str(d) for d in partial_products).lstrip("0")

Time: O(m × n) — every digit pair is visited exactly once.
Space: O(m + n) — the accumulator array, which also becomes the output.

Complexity Summary

| Approach | Time | Space | When to use | |---|---|---| ---| | Digit accumulator | O(m × n) | O(m + n) | Any input size; this is the standard interview answer |

Common Mistakes

• Using i + j instead of i + j + 1 — The product of the two ones digits (num1[-1] × num2[-1]) belongs at the last position (index m + n - 1), which equals (m-1) + (n-1) + 1. Using i + j shifts every digit one place left, corrupting the entire result.
• Propagating carries left-to-right — Carries always move toward more significant (lower-index) digits. Iterating from index 0 upward processes a cell before its carry from the right has arrived, so the carry gets silently dropped.
• Skipping the "0" early return — If either input is "0", the accumulator stays all zeros and lstrip("0") returns an empty string instead of "0".
• Assuming the result always has exactly m + n digits — "9" × "9" = "81" (2 digits, equals m+n=2), but "1" × "1" = "1" (1 digit, less than m+n=2). The leading cell partialProducts[0] is zero in the common case; forgetting to strip it produces "01" instead of "1".
• Building partial rows and adding them as strings — The schoolbook row-by-row approach (multiply num2 by each digit of num1, shift, then add) requires repeated string addition, each costing O(m + n), making the overall complexity O(m × n²) and the code significantly more error-prone.

Related Problems

• Add Two Numbers — linked-list arithmetic with the same right-to-left carry propagation
• Add Binary — binary string addition using the same digit-accumulator pattern
• Plus One — single-pass carry propagation on a digit array
• Reverse Integer — digit extraction and reconstruction without string conversion
• Largest Number — custom digit-level comparison on string representations of integers