Multiply Strings: Grade-School Multiplication

Multiply Strings is LeetCode 43. Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string. You must not use any built-in BigInteger library or convert the inputs to integer directly.

A few examples:

• "2" times "3" gives "6"
• "123" times "456" gives "56088"

The constraint against converting to integers is the entire point. The numbers can be up to 200 digits long. You need to multiply them the same way you did on paper in grade school: digit by digit, tracking position and carry.

The approach

Think back to how you multiply two numbers by hand. You take each digit of the bottom number, multiply it by every digit of the top number, and write each partial product in the right column. Then you add everything up.

The algorithm does exactly that, but instead of writing out partial products on separate lines and adding them at the end, you accumulate directly into a single result array.

Here is the key insight. If you multiply num1[i] by num2[j], the product lands at positions i + j and i + j + 1 in the result array. Position i + j + 1 gets the ones digit, and position i + j gets the tens digit (the carry). This positional rule holds for every pair of digits, no matter how long the numbers are.

The result array has length m + n where m and n are the lengths of num1 and num2. The product of an m-digit number and an n-digit number has at most m + n digits (for example, 99 * 99 = 9801, which is 4 digits from two 2-digit numbers).

The algorithm:

1. Create a result array of size m + n, initialized to all zeros
2. Iterate i from m - 1 down to 0 (right to left through num1)
3. For each i, iterate j from n - 1 down to 0 (right to left through num2)
4. Compute mul = digit1 * digit2
5. Add mul to result[i + j + 1] (which may already hold accumulated values)
6. Set result[i + j + 1] = total % 10 and add total // 10 to result[i + j]
7. After all pairs, convert the result array to a string and strip leading zeros

Visual walkthrough

Here is the full trace of multiplying "123" by "456". Watch how each digit pair contributes to specific positions in the result array, and how carries propagate naturally through the accumulation.

Notice the pattern. Each step does the same thing: multiply two digits, add the product to result[i+j+1], split off the carry into result[i+j]. The positions i + j and i + j + 1 shift as i and j change, but the logic is identical every time.

Python solution

def multiply(num1, num2):
    m, n = len(num1), len(num2)
    result = [0] * (m + n)

    for i in range(m - 1, -1, -1):
        for j in range(n - 1, -1, -1):
            mul = int(num1[i]) * int(num2[j])
            p1, p2 = i + j, i + j + 1
            total = mul + result[p2]

            result[p2] = total % 10
            result[p1] += total // 10

    result_str = "".join(map(str, result)).lstrip("0")
    return result_str or "0"

Let's break this down:

1. Result array size. m + n slots guarantee enough room for the largest possible product. For "999" * "999" = "998001", that is 3 + 3 = 6 digits.
2. Right-to-left iteration. Starting from the last digit of each string mirrors grade-school multiplication, where you start with the ones column.
3. Positional indexing. p1 = i + j and p2 = i + j + 1 are the two positions affected by each single-digit multiplication. The ones digit goes to p2, the carry goes to p1.
4. Accumulation. total = mul + result[p2] adds the new product to whatever was already accumulated at that position from earlier digit pairs.
5. Carry propagation. result[p2] = total % 10 keeps only the ones digit. result[p1] += total // 10 pushes the carry left. Because you process right to left, carries flow naturally into positions that will be visited (or accumulated into) by later iterations.
6. Leading zero removal. lstrip("0") removes any leading zeros from the result string. The or "0" handles the edge case where the entire result is zero.

Complexity analysis

Time: O(m * n) where m is the length of num1 and n is the length of num2. The nested loop visits every pair of digits exactly once. Each iteration does constant work (one multiplication, one addition, one modulo, one division).

Space: O(m + n) for the result array. No other data structures are used. The output string is also O(m + n) in length.

This is optimal for the grade-school approach. There are faster multiplication algorithms (Karatsuba at O(n^1.585), FFT-based at O(n log n)), but for interview purposes, the O(m * n) solution is what is expected.

Building blocks

This problem is built from two core building blocks that appear across many string and math problems.

Digit-by-digit multiplication

Converting a character to its numeric value with int(char), multiplying two single digits, and splitting the result into a ones digit and a tens digit with % 10 and // 10. This is the same modular arithmetic you see in Add Two Numbers (carry propagation), Reverse Integer (digit extraction), and any problem that processes numbers one digit at a time.

Positional accumulation

The insight that num1[i] * num2[j] contributes to result[i + j] and result[i + j + 1] is the core trick. Instead of building separate partial products and adding them together (which would require extra space and a separate addition pass), you accumulate directly into the final result array. This same idea of "know which position a computation affects and write there directly" appears in polynomial multiplication and convolution problems.

Edge cases

Multiply by zero. If either input is "0", the result must be "0", not an empty string or "000". The lstrip("0") call would produce an empty string for "000", so the or "0" fallback handles this.

Single-digit inputs. "2" * "3" = "6". The result array has length 2, and after stripping the leading zero from [0, 6], you get "6". Works without special casing.

Leading zeros in the result. The product of two numbers never has meaningful leading zeros (except for the number 0 itself). But the result array may start with a zero because m + n slots is one more than needed for most products. For example, "12" * "34" = "408", which fits in 3 digits but the result array has 4 slots: [0, 4, 0, 8].

Very large inputs. Two 200-digit numbers produce a result with at most 400 digits. The algorithm handles this correctly since it does not rely on integer types for the overall value, only for single-digit arithmetic (products up to 9 * 9 = 81).

Both inputs are "1". "1" * "1" = "1". The inner loop runs once, producing [0, 1], which strips to "1".

From understanding to recall

You can understand this algorithm by reading through it once. The grade-school analogy makes it intuitive. But reconstructing it from memory during an interview is a different skill. The tricky parts are:

• Remembering that the result array has length m + n
• Getting the positional formula right: p1 = i + j, p2 = i + j + 1
• Remembering to add mul to the existing value at result[p2] before splitting
• The lstrip("0") or "0" cleanup at the end

These details are small but easy to mix up. The positional accumulation pattern is the one brick worth drilling. If you can write the inner loop body from scratch (mul, total, % 10, // 10), the rest of the function is just setup and cleanup.

Related posts

• Add Two Numbers - The same digit-by-digit arithmetic with carry propagation, applied to linked list addition instead of string multiplication
• Reverse Integer - Uses the same % 10 and // 10 digit extraction loop, the fundamental building block for processing numbers one digit at a time