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.
Intuition
Think about how you multiply on paper: each digit of one number multiplies each digit of the other, and the partial product lands at a specific position determined by the positions of the two digits. If digit i (from the right, 0-indexed) of num1 multiplies digit j of num2, the result contributes to positions i + j and i + j + 1 in the output. You can accumulate all these partial products into a result array and propagate carries at the end — or even as you go. The result of multiplying an m-digit number by an n-digit number has at most m + n digits.
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
Allocate a result array of length `m + n`
The product of an m-digit number and an n-digit number has at most m + n digits (e.g., 99 * 99 = 9801, 2 + 2 = 4 digits). Create an integer array of that size, initialized to zero. Each cell will accumulate partial products before carries are resolved.
Multiply each pair of digits and place the result at the right position
Iterate i from the end of num1 and j from the end of num2. Multiply the two digits, add to the current value at position i + j + 1 in the result array (the ones place of this partial product). Then propagate any carry to position i + j immediately: result[i + j] += result[i + j + 1] // 10 and result[i + j + 1] %= 10. Doing the carry inline keeps each cell as a single digit.
Convert the result array to a string, stripping leading zeros
Join the digits into a string. Strip leading zeros with lstrip('0'). If the entire result is zeros (the product is zero), return "0". Time is O(m * n) for the nested multiplication. Space is O(m + n) for the result array.
Solution
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.