Multiply Strings (LeetCode 43)

The problem

You get two non-negative integers as strings, num1 and num2. Return their product, also as a string. You may not convert the whole strings to integers or use a big-integer library: the numbers can be up to 200 digits long.

Input:  num1 = "12", num2 = "34"
Output: "408"

12 × 34 = 408. (A bigger check: "123" × "456" gives "56088".)

How to think about it

Start with what’s banned. str(int(num1) * int(num2)) is a one-liner in Python, but the problem forbids it, and in Java or C++ a 200-digit number fits in no built-in type. So you must multiply digit by digit, the way you learned at school.

The school method, done naively. Multiply num1 by each digit of num2 to get a partial product, shift each one by its place, and add all the partial products as strings. That is correct and O(m·n), but it creates many intermediate strings and needs a separate string-addition routine.

The key insight: you know exactly where each digit product lands. A number with m digits times one with n digits has at most m + n digits, so allocate an array res of that size. With 0-indexed positions from the left, num1[i] × num2[j] contributes to position i + j + 1 (its ones digit) and carries into position i + j (its tens digit). So you never build partial products. For each pair of digits, add the product to res[i+j+1], keep the last digit there, and push the carry into res[i+j].

Why going right to left works. Looping i and j from the right means lower positions are finished before higher ones receive their carries. A position may temporarily hold a value of 10 or more after a carry lands, but it is normalised the next time it is used as p2. The tell for this pattern is “arithmetic on numbers stored as strings or arrays”: simulate the paper algorithm with explicit positions.

Approach

1. If either number is "0", return "0".
2. Create res = [0] * (len(num1) + len(num2)).
3. For i from the last digit of num1 down to 0, and j from the last digit of num2 down to 0:
   • compute mul = digit × digit;
   • total = mul + res[i+j+1];
   • set res[i+j+1] = total % 10 and add total // 10 to res[i+j].
4. Join res into a string and strip leading zeros. Return "0" if nothing is left.

Solution

def multiply(num1, num2):
    if num1 == "0" or num2 == "0":
        return "0"
    res = [0] * (len(num1) + len(num2))              # product has at most m+n digits
    for i in range(len(num1) - 1, -1, -1):
        for j in range(len(num2) - 1, -1, -1):
            mul = (ord(num1[i]) - 48) * (ord(num2[j]) - 48)   # char -> digit
            p1, p2 = i + j, i + j + 1                # tens go to p1, ones to p2
            total = mul + res[p2]
            res[p2] = total % 10; res[p1] += total // 10
    s = "".join(map(str, res)).lstrip('0')
    return s or "0"
# multiply("123", "456") -> "56088"

Dry run

On num1 = "12", num2 = "34", so res has 4 slots:

Joining gives "0408", and stripping the leading zero gives “408”.

Complexity

• Time: O(m·n). Every digit of num1 meets every digit of num2 once, with O(1) work per pair.
• Space: O(m + n). The res array and the output string.

Edge cases and pitfalls

• A zero operand would leave res all zeros and lstrip would return an empty string. The early "0" check (and the s or "0" fallback) handles it.
• Leading zeros in res are normal: the product often has m + n - 1 digits, not m + n. Strip them.
• Off-by-one in positions. The ones digit goes to i + j + 1, not i + j. Check it on 2-digit numbers before coding.
• Carries above 9. res[p1] can briefly exceed 9; that is fine because it is fixed when it later becomes a p2, or it is position 0 where the maths guarantees a single digit.
• Converting with int() is the banned shortcut; say why you are not using it.

Related problems

• Add Two Numbers (LeetCode 2): digit-by-digit addition with carries, on linked lists.
• Plus One (LeetCode 66): the simplest carry problem on a digit array.
• Pow(x, n) (LeetCode 50): another basic operation you implement yourself, here with repeated squaring.