Multiply Strings

PracticeNeetCode ↗LeetCode ↗

Given two non-negative integers num1 and num2 represented as strings, return their product, also as a string — without converting either input directly to an integer.

Example

Key Pointers

• Simulate grade-school long multiplication: multiplying an m-digit number by an n-digit number produces at most m+n digits.
• Digit i of num1 times digit j of num2 contributes to result positions i+j and i+j+1 — that index mapping is the key trick.
• Accumulate into an integer array first (letting values exceed 9 mid-computation), then do a single carry-propagation pass at the end, rather than carrying after every multiplication.

Step-by-Step Analysis

1. If either input is "0", return "0" immediately.
2. Create a result array of zeros with length len(num1) + len(num2).
3. For every digit pair (i, j), multiply them and add the product into result[i+j+1], carrying the overflow into result[i+j].
4. After all multiplications, sweep once from the end of result, carrying any digit ≥ 10 into the position to its left.
5. Join the digits into a string, strip leading zeros, and return it.

Complexity

Time: O(m · n) — Space: O(m + n)

Code

def multiply(num1: str, num2: str) -> str:
    if num1 == "0" or num2 == "0":
        return "0"

    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 if result_str else "0"

Code Explanation

How the solution above works, piece by piece.

1. If either number is "0", the answer is "0".
2. result has m + n slots, enough for any product.
3. For each digit pair from the right, num1[i] × num2[j] belongs at positions i + j and i + j + 1.
4. Add the existing value at p2, keep the units digit there, and push the carry into p1.
5. Join the digits and strip leading zeros. O(m × n) time.

Visual Walkthrough

Running it on num1 = "123", num2 = "456":

Video Explanation

NeetCode — LeetCode 43