LeetCode 43 – Multiply Strings

Multiply Strings is long multiplication, done the way you learned it at school and then forgot. The whole problem hinges on one piece of index arithmetic — where does the product of digit i and digit j land? — and once you have that, the rest is carrying.

The problem

Given two non-negative integers as strings, return their product as a string. You may not convert the inputs to integers or use a big-integer library.

"2" × "3"     -> "6"
"123" × "456" -> "56088"
"0" × "52"    -> "0"      not "000"

The ban on integer conversion is the point. Inputs run to 200 digits, so a long overflows immediately — this is a question about implementing arithmetic, not calling it.

Two facts to establish first

The result needs at most m + n digits. An m-digit number is under 10m and an n-digit number under 10n, so the product is under 10m+n. Allocate exactly that and you never resize. (It is sometimes m + n - 1 — 11 × 11 = 121 — which is why leading zeros get stripped at the end.)

Digit i of the first number times digit j of the second lands at positions i + j and i + j + 1. This is the line to derive rather than memorise. Working right-to-left, digit i carries place value 10m-1-i and digit j carries 10n-1-j, so the product sits at 10(m+n-2-i-j) — which in an array of length m + n indexed from the left is position i + j + 1, with the tens digit spilling into i + j.

    "123" × "456", digits[] has 3 + 3 = 6 slots

         i=2 ('3') × j=2 ('6') = 18
         lands at index i+j+1 = 5, carrying into index i+j = 4

    idx:  0    1    2    3    4    5
        [ .    .    .    .   +1    8 ]

Multiply everything, carry as you go

Two nested loops from the right. At each step add the product into the low slot, keep sum % 10 there, and push sum / 10 into the slot to its left.

The slot on the left may temporarily exceed 9, which looks alarming and is fine: it is always visited as a *low* slot later in the iteration order, where the % 10 normalises it and its own carry moves left again. The only index never revisited is 0, and it can only receive a carry from the very last multiplication, which is at most (81 + 9) / 10 = 9. So the array is fully normalised by the time the loops finish.

Java

class Solution {
    public String multiply(String num1, String num2) {
        if (num1.equals("0") || num2.equals("0")) {
            return "0";     // otherwise this returns a string of zeros
        }

        int m = num1.length(), n = num2.length();
        int[] digits = new int[m + n];

        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                int product = (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
                int low = i + j + 1, high = i + j;

                int sum = product + digits[low];
                digits[low] = sum % 10;
                digits[high] += sum / 10;   // may exceed 9; normalised when visited as `low`
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int d : digits) {
            if (sb.length() > 0 || d != 0) {    // skip leading zeros, keep interior ones
                sb.append((char) ('0' + d));
            }
        }

        return sb.toString();
    }
}

The zero check at the top is not an optimisation. Without it, "0" × "52" leaves the array all zeros, the leading-zero skip drops every one of them, and you return the empty string.

The skip condition is sb.length() > 0 || d != 0, not d != 0. Once anything has been appended, a zero is an interior digit and must be kept — "101" depends on it.

Python

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

        m, n = len(num1), len(num2)
        digits = [0] * (m + n)

        for i in range(m - 1, -1, -1):
            for j in range(n - 1, -1, -1):
                product = int(num1[i]) * int(num2[j])
                low, high = i + j + 1, i + j

                total = product + digits[low]
                digits[low] = total % 10
                digits[high] += total // 10

        out = "".join(str(d) for d in digits).lstrip("0")
        return out

Python's arbitrary-precision integers mean str(int(num1) * int(num2)) genuinely works and is one line. That is exactly why the problem forbids it — say you know, then write the loops. The lstrip("0") is safe here only because the zero case already returned; "0".lstrip("0") is "".

Complexity

O(m · n) time — every pair of digits is multiplied exactly once — and O(m + n) space for the digit array. This is schoolbook multiplication, and it is what is expected here.

Faster algorithms exist and are worth a sentence: Karatsuba reaches O(n1.585) by replacing one of four recursive multiplications with additions, and FFT-based methods get near O(n log n). Both only pay off at thousands of digits, which is why every standard library uses schoolbook below a threshold and switches above it. Nobody expects you to write either.

What the interviewer is checking

• That you derive the i + j / i + j + 1 placement instead of guessing and adjusting until the tests pass.
• That you size the array m + n, and can justify it.
• The zero case — the input that returns "" without a guard.
• Leading zeros stripped, interior zeros kept.
• That you did not quietly parse the strings to numbers.
• That you can explain why an intermediate slot going above 9 is harmless.