Multiply Strings
Multiply Strings: given two non-negative integers represented as strings num1 and num2, return their product as a string without using any built-in big-integer multiplication.
- 1 <= num1.length, num2.length <= 200
- num1 and num2 consist of digits only.
- Both num1 and num2 do not contain any leading zero, except the number 0 itself.
Intuition
Multiply strings multiplies two non-negative integers given as strings, without converting them to integers. The numbers can reach 200 digits, which overflows every built-in type — so the conversion ban is a genuine constraint rather than an artificial one.
The method is schoolbook long multiplication, and one observation makes the bookkeeping easy:
- Digit i of one number times digit j of the other always contributes to positions i + j and i + j + 1 of the result.
That indexing removes any need to track shifts or pad partial products. Allocate a result array of length m + n — the maximum possible digit count — and accumulate directly into it.
Working from the least significant digits, multiply each pair and add the product to position i + j + 1. Then carry: the value at that position modulo 10 stays, and the tens digit is added to position i + j.
Adding rather than assigning is what makes the accumulation correct, since many digit pairs land on the same position.
Indexing from the right of each string, or reversing them first, keeps the arithmetic aligned with the array positions.
Two details finish it. Leading zeros must be stripped from the result array, since m + n positions are allocated but the product may be shorter. And if either input is "0", the answer is "0" — stripping zeros from an all-zero array would otherwise leave an empty string.
The cost is O(m × n) time and O(m + n) space, which is optimal for schoolbook multiplication.
When a problem says 'multiply two numbers given as strings' and forbids big-integer libraries, the shape is grade-school multiplication. The key mechanical detail is the positional formula: digit i from the right times digit j from the right contributes to position i + j + 1 (and carry to i + j). The same positional thinking applies to polynomial multiplication and convolution.
Approach
Before reading on: price up what the direct approach costs here, then ask what pattern in the numbers removes the loop entirely. Aim for O(m * n) time and O(m + n) space.
Understand why conversion is banned
The inputs reach 200 digits and overflow every built-in integer type, so digit-wise arithmetic is required rather than merely requested.
Allocate m + n positions
The product has at most m + n digits. A result array of that size holds every partial contribution with no resizing.
Use the index identity
Digits i and j contribute to positions i + j and i + j + 1. This removes all shift tracking and partial-product padding.
Accumulate, then carry
Add each product into position i + j + 1, keep that value modulo 10, and add the tens digit to position i + j. Adding, not assigning — many pairs share a position.
Strip leading zeros
The allocated length exceeds the actual product, so remove leading zeros from the result array before building the string.
Handle the zero input
If either input is "0", return "0". Stripping zeros from an all-zero array leaves an empty string otherwise.
Cost of the multiplication
Every digit pair is multiplied once, giving O(m × n) time and O(m + n) space — optimal for the schoolbook method.
Solution & live demo
Common pitfalls
Placing the partial product at position i + j instead of i + j + 1
result[i + j] += d1 * d2
result[i + j + 1] += d1 * d2
Position i + j + 1 is the ones place of the partial product; position i + j is the tens (carry) place. Placing at i + j shifts every partial product one position too high, making the result 10x too large.
Iterating digits from the left instead of the right
for i in range(len(num1)):
for j in range(len(num2)):for i in range(len(num1) - 1, -1, -1):
for j in range(len(num2) - 1, -1, -1):The positional formula assumes i and j are counted from the right (least significant). Iterating from the left without adjusting the index maps digits to wrong positions.
Returning an empty string when the product is zero
return ''.join(str(d) for d in result).lstrip('0')s = ''.join(str(d) for d in result).lstrip('0')
return s if s else '0'lstrip('0') on "0000" produces an empty string. The product of "0" and anything is "0", not "".
Edge cases
"0"Every partial product is zero, so the result array is all zeros. The leading-zero strip removes everything, and we return "0".
"1"Each digit of the other number multiplies by 1 and lands in the correct position. The result is the other number itself.
The algorithm is O(m n) with no integer overflow because each cell stores at most a two-digit intermediate (99 + carry = 81 + 9 = 90) before the carry propagates.