Generated by Codex with GPT-5

Quick facts

Problem gist

Given two non-negative integers as strings, return their product as a string. The catch is that the inputs may be too large for normal integer conversion, so the solution has to work with characters and digits directly.

This is the same multiplication taught on paper: multiply every digit in the first number by every digit in the second number, add each partial result into the correct place value, and carry when a position reaches 10 or more.

The practical challenge is indexing. If num1[i] and num2[j] are multiplied, their ones-place contribution lands at result index i + j + 1, and their carry lands one slot to the left at i + j. Once that rule is clear, the implementation is short and reliable.

Core idea

Allocate an array of len(num1) + len(num2) digits. That is the maximum possible length of the product: for example, a three-digit number times a two-digit number can have at most five digits.

Then walk both strings from right to left:

  1. Convert the current characters into digit values.
  2. Multiply the two digits.
  3. Add the product into the lower result position, i + j + 1.
  4. Keep the lower position modulo 10.
  5. Push the carry into the higher result position, i + j.

The array stores digits, not a numeric value. After all digit pairs are processed, skip leading zeroes and join the remaining digits into the answer string.

The important derivation is the index formula. A digit at num1[i] is len(num1) - 1 - i places from the right. A digit at num2[j] is len(num2) - 1 - j places from the right. Their product belongs at the sum of those place values, which maps back to result index i + j + 1.

Python solution

from typing import List


class Solution:
    def multiply(self, num1: str, num2: str) -> str:
        if self._is_zero(num1) or self._is_zero(num2):
            return "0"

        result_digits = [0] * (len(num1) + len(num2))

        for first_index in range(len(num1) - 1, -1, -1):
            first_digit = self._to_digit(num1[first_index])

            for second_index in range(len(num2) - 1, -1, -1):
                second_digit = self._to_digit(num2[second_index])
                product = first_digit * second_digit

                low_position = first_index + second_index + 1
                high_position = first_index + second_index

                # Add into the current place and push any overflow left.
                total = result_digits[low_position] + product
                result_digits[low_position] = total % 10
                result_digits[high_position] += total // 10

        return self._digits_to_string(result_digits)

    def _is_zero(self, value: str) -> bool:
        return all(character == "0" for character in value)

    def _to_digit(self, character: str) -> int:
        return ord(character) - ord("0")

    def _digits_to_string(self, digits: List[int]) -> str:
        first_non_zero = 0
        while first_non_zero < len(digits) and digits[first_non_zero] == 0:
            first_non_zero += 1

        if first_non_zero == len(digits):
            return "0"

        return "".join(str(digit) for digit in digits[first_non_zero:])

Why it works

Every pair of input digits contributes exactly one one-digit product to exactly one place value in the final answer. The nested loops enumerate all of those pairs, so no contribution is missed.

The result array acts like the columns in hand multiplication. Whenever a product is added to a column, the code leaves the column’s final digit in place with % 10 and carries the overflow to the column on the left. That is exactly how base-10 addition works.

The maximum result length is also covered. If both inputs have lengths m and n, their product can have at most m + n digits, so the array has enough room for every carry. Removing leading zeroes at the end turns the fixed-size array back into the normal product representation.

Complexity

Let m = len(num1) and n = len(num2).

The runtime is O(mn) because every digit in num1 is multiplied by every digit in num2. The extra space is O(m + n) for the result array, excluding the returned string.

Interview follow-ups

Why does the product of num1[i] and num2[j] go to i + j + 1?

Work from the right side of the strings. If num1 has length m, digit i represents the 10^(m - 1 - i) place. If num2 has length n, digit j represents the 10^(n - 1 - j) place. Multiplying them gives place 10^((m - 1 - i) + (n - 1 - j)).

The result array has length m + n, so its last index is m + n - 1. Mapping that place value back into a left-to-right array gives index i + j + 1. Any carry from that column belongs one position to the left, which is i + j.

Can this be done by building partial strings and adding them?

Yes. For each digit in one number, create a shifted partial product string, then add all partial products as strings. This mirrors paper multiplication even more directly.

It works, but it is usually more code and more memory. Each partial string can be length O(m + n), and repeatedly adding strings can add avoidable overhead. The single result array is cleaner because it accumulates all partial products in place while keeping the same O(mn) time complexity.

What changes if the inputs may contain signs or leading zeroes?

Normalize first. Strip leading zeroes from the absolute-value portion of each input, remember whether exactly one input is negative, and run the same multiplication on the cleaned non-negative strings.

The multiplication logic does not change because sign handling is separate from digit-place arithmetic. At the end, return "0" if the product is zero; otherwise prepend "-" when the signs differ. The complexity remains O(mn).

Is there a faster algorithm for extremely large strings?

For very large inputs, algorithms like Karatsuba multiplication, Toom-Cook, or FFT-based multiplication can beat the O(mn) grade-school method. They reduce the number of digit-level operations by splitting the numbers into chunks and combining intermediate products more efficiently.

In interviews, the grade-school array is usually the expected solution because it is simple, deterministic, and easy to reason about. Faster algorithms have better asymptotic behavior but much higher implementation complexity and larger constant factors.

How would you adapt this to another base, such as base 1,000 or base 1,000,000?

Split each input into chunks instead of single decimal digits, then run the same array-based multiplication where each cell stores a chunk. The carry base becomes the chunk base instead of 10.

This reduces the number of loop iterations because each array element represents several decimal digits. The tradeoff is output formatting: after the most significant chunk, every remaining chunk must be padded with leading zeroes to the fixed chunk width.