43. Multiply Strings

Problem Statement

Given two non-negative integers represented as strings num1 and num2, return their product as a string. You cannot convert the inputs to integers directly (numbers can be very large).

Examples

Example 1:

Input: num1 = "2", num2 = "3"
Output: "6"

Example 2:

Input: num1 = "123", num2 = "456"
Output: "56088"

Constraints

  • 1 <= num1.length, num2.length <= 200
  • num1 and num2 consist of digits only
  • Neither contains leading zeros (except "0" itself)

Clarification Questions

  1. Direct conversion: Can we use int()? (Assumption: No — numbers can exceed int range.)
  2. Leading zeros: Should output have leading zeros? (Assumption: No — return canonical form.)
  3. Zero product: “0” × anything = “0”? (Assumption: Yes.)
  4. Digits only: Only ‘0’-‘9’? (Assumption: Yes.)

Interview Deduction Process (20 minutes)

Step 1: Grade-school multiplication (5 min) — Multiply each digit of num1 by each digit of num2; add into result at the right position. Result length at most len(num1) + len(num2).

Step 2: Index mapping (7 min) — num1[i] * num2[j] contributes to result at index i + j and i + j + 1. Use an array of length n + m; accumulate then strip leading zeros.

Step 3: Optimized (8 min) — Single pass: for each (i, j), add digit product to res[i+j+1] and carry to res[i+j]. Then convert to string and strip leading zeros. Handle “0” explicitly.

Solution Approach

This is big integer multiplication – simulate digit-by-digit multiplication exactly like grade school arithmetic.

Key Insights

If num1 has length n and num2 has length m:

  • The product has at most n + m digits
  • Allocate a result array of size n + m

Index Formula

When multiplying num1[i] * num2[j], the contribution goes to:

\(\text{result}[i + j + 1] \quad \text{(ones place)}\) \(\text{result}[i + j] \quad \text{(carry)}\)

This is because position i from the end of num1 and position j from the end of num2 together shift the product by (n-1-i) + (m-1-j) places, which maps to index i + j + 1 in the result array.

Walk-Through: 123 × 45

         1  2  3
       ×    4  5
      -----------
  positions: result[0..4]

  3×5 = 15 → result[4] += 15  → result[4]=5, carry 1 to result[3]
  2×5 = 10 → result[3] += 10+1 = 11 → result[3]=1, carry 1 to result[2]
  1×5 =  5 → result[2] += 5+1 = 6

  3×4 = 12 → result[3] += 12  → result[3]=3, carry 1 to result[2]
  2×4 =  8 → result[2] += 8+1 = 15 → result[2]=5, carry 1 to result[1]
  1×4 =  4 → result[1] += 4+1 = 5

  result = [0, 5, 5, 3, 5] → "05535" → skip leading zero → "5535"

Wait – 123 × 45 = 5535. Correct!

Approach: Grade School Multiplication – $O(nm)$

Multiply each digit pair, accumulate into a result array with carry propagation.

class Solution:
def multiply(self, num1, num2):
    if (num1 == "0"  or  num2 == "0") return "0"
    n = len(num1)
    m = len(num2)
    list[int> result(n + m, 0)
    for (i = n - 1 i >= 0 i -= 1) :
    for (j = m - 1 j >= 0 j -= 1) :
    mul = (num1[i] - '0')  (num2[j] - '0')
    sum = mul + result[i + j + 1]
    result[i + j + 1] = sum % 10
    result[i + j] += sum / 10
str ans
for num in result:
    if not (not ans  and  num == 0):
    ans += to_string(num)
("0" if         return not ans  else ans)

Time: $O(n \times m)$ Space: $O(n + m)$ for the result array

Common Mistakes

  • Forgetting the early return for "0" inputs (otherwise you get "000...")
  • Off-by-one on the index formula (i + j vs i + j + 1)
  • Not handling leading zeros when converting the result array to a string

Key Takeaways

  • Big integer multiplication follows the same algorithm you learned in school
  • The index formula result[i + j + 1] is the core insight – memorize it
  • Always allocate n + m digits for the result
  • Faster algorithms exist (Karatsuba $O(n^{1.58})$, FFT $O(n \log n)$) but are overkill for interview constraints

Template Reference