Multiply Strings

For each digit of num2 (from the right), multiply it across all of num1 to form one partial product, append the right number of trailing zeros for its place value, and add that partial product into a running total using string addition (also implemented digit-by-digit, since built-in integer conversion is off-limits).

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

        def add_strs(a: str, b: str) -> str:
            i, j, carry = len(a) - 1, len(b) - 1, 0
            digits = []
            while i >= 0 or j >= 0 or carry:
                d1 = int(a[i]) if i >= 0 else 0
                d2 = int(b[j]) if j >= 0 else 0
                total = d1 + d2 + carry
                digits.append(str(total % 10))
                carry = total // 10
                i -= 1
                j -= 1
            return ''.join(reversed(digits))

        result = "0"
        for i in range(len(num2) - 1, -1, -1):
            d2 = int(num2[i])
            carry = 0
            partial = []
            for j in range(len(num1) - 1, -1, -1):
                prod = int(num1[j]) * d2 + carry
                partial.append(str(prod % 10))
                carry = prod // 10
            if carry:
                partial.append(str(carry))
            shifted = ''.join(reversed(partial)) + '0' * (len(num2) - 1 - i)
            result = add_strs(result, shifted)
        return result

Tracing num1 = "123", num2 = "456": multiplying 123 by 6 gives partial product 738; by 5 (shifted one place) gives 6150; by 4 (shifted two places) gives 49200. Summing 738 + 6150 + 49200 = 56088 — matching the expected output.

Complexity: there are n partial products (one per digit of num2), each taking O(m) to compute and O(m+n) to add into the running total → O(m·n) time. The result and partial strings are each at most O(m+n) digits long → O(m + n) space.

The product of num1[i] and num2[j] (each a single digit) always lands at output positions i + j (its carry digit) and i + j + 1 (its ones digit) in the final answer, regardless of what any other digit pair contributes — this is just the place-value rule of multiplication. So instead of building and re-adding separate partial products, accumulate every digit-pair’s contribution straight into a shared result array of size m + n, and let carries resolve naturally as later, smaller-index pairs add into the same cells.

class Solution:
    def multiply(self, num1: str, num2: str) -> str:
        if num1 == "0" or num2 == "0":
            return "0"
        m, n = len(num1), len(num2)
        result = [0] * (m + n)
        for i in range(m - 1, -1, -1):
            for j in range(n - 1, -1, -1):
                mul = int(num1[i]) * int(num2[j])
                p_low, p_high = i + j + 1, i + j
                total = mul + result[p_low]
                result[p_low] = total % 10
                result[p_high] += total // 10
        start = 0
        while start < len(result) - 1 and result[start] == 0:
            start += 1
        return ''.join(map(str, result[start:]))

Tracing num1 = "123", num2 = "456" — watch where each digit-pair product lands: pair (i, j) folds its ones digit into slot i + j + 1 and pushes any carry one slot left, into i + j:

After all nine pairs the array holds [0, 5, 6, 0, 8, 8]. Slot 0 is only padding, so the leading-zero trim drops it and the remaining slots read "56088" — the expected output. Notice there is no separate carry pass: every slot’s last write is a mod-10 write, so the array is already clean when the loops end.

Complexity: every one of the m * n digit pairs is processed once with O(1) work → O(m·n) time. The result array holds at most m + n digits → O(m + n) space — asymptotically the same as the row-by-row version, but with a smaller constant factor since no intermediate partial-product strings or repeated string additions are built.