43. Multiply Strings (Medium)

Problem

Given two non-negative integers num1 and num2 represented as strings, return their product as a string. You must not convert to integers directly (simulate the arithmetic).

Example

• num1 = "2", num2 = "3" → "6"
• num1 = "123", num2 = "456" → "56088"

LeetCode 43 · Link · Medium

Try it yourself

Python

▶ Run Python ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Big-integer via int() (cheating)

Not permitted by the problem, but shown for contrast.

Python

def multiply(num1, num2):
    return str(int(num1) * int(num2))

TypeScript

function multiply(num1: string, num2: string): string {
    return String(BigInt(num1) * BigInt(num2));
}

Go

import "strconv"

func multiply(num1 string, num2 string) string {
    n1, _ := strconv.ParseInt(num1, 10, 64)
    n2, _ := strconv.ParseInt(num2, 10, 64)
    return strconv.FormatInt(n1*n2, 10)
}

Swift

final class Solution {
    func multiply(_ num1: String, _ num2: String) -> String {
        guard let left = Int(num1), let right = Int(num2) else { return "" }
        return String(left * right)
    }
}

Complexity

• Time: $O(n · m)$ ish.
• Space: $O(n + m)$.

Approach 2: Schoolbook multiplication on digit arrays (canonical)

result[i + j + 1] accumulates num1[i] * num2[j] with carries propagated at the end.

Python

def multiply(num1, num2):
    if num1 == "0" or num2 == "0":              # L1: O(1) early exit
        return "0"
    n, m = len(num1), len(num2)                 # L2: O(1)
    result = [0] * (n + m)                      # L3: O(n + m)
    for i in range(n - 1, -1, -1):              # L4: outer loop, n iterations
        for j in range(m - 1, -1, -1):          # L5: inner loop, m iterations
            prod = int(num1[i]) * int(num2[j])  # L6: O(1)
            p1, p2 = i + j, i + j + 1          # L7: O(1)
            total = prod + result[p2]           # L8: O(1)
            result[p2] = total % 10             # L9: O(1)
            result[p1] += total // 10           # L10: O(1)

    # Strip leading zeros
    start = 0
    while start < len(result) and result[start] == 0:
        start += 1                              # L11: O(n + m)
    return "".join(map(str, result[start:]))    # L12: O(n + m)

TypeScript

function multiply(num1: string, num2: string): string {
    if (num1 === '0' || num2 === '0') return '0';          // L1: O(1) early exit
    const n = num1.length, m = num2.length;                // L2: O(1)
    const result = new Array(n + m).fill(0);               // L3: O(n + m)
    for (let i = n - 1; i >= 0; i--) {                    // L4: outer loop, n iterations
        for (let j = m - 1; j >= 0; j--) {                // L5: inner loop, m iterations
            const prod = +num1[i] * +num2[j];              // L6: O(1)
            const p1 = i + j, p2 = i + j + 1;             // L7: O(1)
            const total = prod + result[p2];               // L8: O(1)
            result[p2] = total % 10;                       // L9: O(1)
            result[p1] += Math.floor(total / 10);          // L10: O(1)
        }
    }
    let start = 0;
    while (start < result.length && result[start] === 0) start++;  // L11: O(n + m)
    return result.slice(start).join('') || '0';            // L12: O(n + m)
}

Go

import "strconv"

func multiply(num1 string, num2 string) string {
    if num1 == "0" || num2 == "0" {              // L1: O(1) early exit
        return "0"
    }
    n, m := len(num1), len(num2)                 // L2: O(1)
    result := make([]int, n+m)                   // L3: O(n + m)
    for i := n - 1; i >= 0; i-- {               // L4: outer loop, n iterations
        for j := m - 1; j >= 0; j-- {           // L5: inner loop, m iterations
            prod := int(num1[i]-'0') * int(num2[j]-'0')  // L6: O(1)
            p1, p2 := i+j, i+j+1                // L7: O(1)
            total := prod + result[p2]           // L8: O(1)
            result[p2] = total % 10              // L9: O(1)
            result[p1] += total / 10             // L10: O(1)
        }
    }
    start := 0
    for start < len(result) && result[start] == 0 {
        start++                                  // L11: O(n + m)
    }
    out := ""
    for _, d := range result[start:] {
        out += strconv.Itoa(d)                   // L12: O(n + m)
    }
    return out
}

Swift

final class Solution {
    func multiply(_ num1: String, _ num2: String) -> String {
        if num1 == "0" || num2 == "0" { return "0" }
        let left = Array(num1.utf8).map { Int($0 - 48) }
        let right = Array(num2.utf8).map { Int($0 - 48) }
        var digits = Array(repeating: 0, count: left.count + right.count)

        for i in left.indices.reversed() {
            for j in right.indices.reversed() {
                let position = i + j + 1
                let total = left[i] * right[j] + digits[position]
                digits[position] = total % 10
                digits[position - 1] += total / 10
            }
        }

        let first = digits.firstIndex(where: { $0 != 0 }) ?? digits.count - 1
        return digits[first...].map(String.init).joined()
    }
}

Where the time goes, line by line

Variables: n = len(num1), m = len(num2).

Line	Per-call cost	Times executed	Contribution
L3 (init result)	$O(1)$	n + m	$O(n + m)$
L4, L5 (nested loops)	$O(1)$	n * m	$O(n · m)$ ← dominates
L6-L10 (digit multiply + carry)	$O(1)$	n * m	$O(n · m)$
L11-L12 (strip + join)	$O(1)$	n + m	$O(n + m)$

Every pair of digit positions (i, j) is visited exactly once; there are n * m such pairs.

Complexity

• Time: $O(n · m)$, driven by L4/L5/L6-L10 (the nested digit-multiply loop).
• Space: $O(n + m)$ for the result array.

Why p1, p2 = i + j, i + j + 1 works

In schoolbook multiplication, the product of two digits at positions i (from num1) and j (from num2) contributes to positions i + j (carry) and i + j + 1 (units) of the result. Carries propagate leftward during accumulation.

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Approach 3: Karatsuba (divide and conquer)

$O(n^{log₂3})$ ≈ $O(n^{1.585})$. Rarely worth the code in an interview but known as “the first better-than-quadratic integer multiplication.”

The trick: split each number in half (x = x_hi · 10^m + x_lo, similarly for y). Schoolbook would do four multiplications:

xy = x_hi y_hi · 10^(2m) + (x_hi y_lo + x_lo y_hi) · 10^m + x_lo y_lo

Karatsuba does three by computing M = (x_hi + x_lo)(y_hi + y_lo) and recovering the cross terms as M - x_hi y_hi - x_lo y_lo.

Python

def multiply(num1, num2):
    if num1 == "0" or num2 == "0":
        return "0"

    def add_strs(a, b):
        i, j, carry, out = len(a) - 1, len(b) - 1, 0, []
        while i >= 0 or j >= 0 or carry:
            x = int(a[i]) if i >= 0 else 0
            y = int(b[j]) if j >= 0 else 0
            total = x + y + carry
            out.append(str(total % 10)); carry = total // 10
            i -= 1; j -= 1
        return "".join(reversed(out))

    def sub_strs(a, b):                          # a >= b
        i, j, borrow, out = len(a) - 1, len(b) - 1, 0, []
        while i >= 0:
            x = int(a[i]) - borrow
            y = int(b[j]) if j >= 0 else 0
            if x < y: x += 10; borrow = 1
            else:     borrow = 0
            out.append(str(x - y))
            i -= 1; j -= 1
        return "".join(reversed(out)).lstrip("0") or "0"

    def shift(s, n):
        return s + "0" * n if s != "0" else "0"

    def kar(x, y):
        if len(x) == 1 and len(y) == 1:
            return str(int(x) * int(y))
        if x == "0" or y == "0":
            return "0"
        n = max(len(x), len(y))
        m = n // 2
        x_hi = x[:-m] if len(x) > m else "0"
        x_lo = x[-m:].lstrip("0") or "0"
        y_hi = y[:-m] if len(y) > m else "0"
        y_lo = y[-m:].lstrip("0") or "0"
        z2 = kar(x_hi, y_hi)                                                      # x_hi · y_hi
        z0 = kar(x_lo, y_lo)                                                      # x_lo · y_lo
        z1 = sub_strs(kar(add_strs(x_hi, x_lo), add_strs(y_hi, y_lo)),
                      add_strs(z2, z0))                                            # cross term
        result = add_strs(shift(z2, 2 * m), shift(z1, m))
        result = add_strs(result, z0)
        return result.lstrip("0") or "0"

    return kar(num1, num2)

Swift

final class Solution {
    func multiply(_ num1: String, _ num2: String) -> String {
        karatsuba(normalize(num1), normalize(num2))
    }

    private func karatsuba(_ x: String, _ y: String) -> String {
        if x == "0" || y == "0" { return "0" }
        if x.count == 1 && y.count == 1 {
            let a = Int(x.utf8.first.map { $0 - 48 } ?? 0)
            let b = Int(y.utf8.first.map { $0 - 48 } ?? 0)
            return String(a * b)
        }

        let width = max(x.count, y.count)
        let split = width / 2
        let (xHigh, xLow) = parts(x, lowWidth: split)
        let (yHigh, yLow) = parts(y, lowWidth: split)
        let high = karatsuba(xHigh, yHigh)
        let low = karatsuba(xLow, yLow)
        let sums = karatsuba(add(xHigh, xLow), add(yHigh, yLow))
        let cross = subtract(subtract(sums, high), low)
        return add(add(shift(high, by: 2 * split), shift(cross, by: split)), low)
    }

    private func parts(_ value: String, lowWidth: Int) -> (String, String) {
        let bytes = Array(value.utf8)
        let cut = max(0, bytes.count - lowWidth)
        let high = cut == 0 ? "0" : String(decoding: bytes[..<cut], as: UTF8.self)
        let low = String(decoding: bytes[cut...], as: UTF8.self)
        return (normalize(high), normalize(low))
    }

    private func add(_ a: String, _ b: String) -> String {
        let left = Array(a.utf8), right = Array(b.utf8)
        var i = left.count - 1, j = right.count - 1, carry = 0
        var output: [UInt8] = []
        while i >= 0 || j >= 0 || carry > 0 {
            let x = i >= 0 ? Int(left[i] - 48) : 0
            let y = j >= 0 ? Int(right[j] - 48) : 0
            let total = x + y + carry
            output.append(UInt8(total % 10 + 48))
            carry = total / 10
            i -= 1
            j -= 1
        }
        return String(decoding: output.reversed(), as: UTF8.self)
    }

    private func subtract(_ a: String, _ b: String) -> String {
        let left = Array(a.utf8), right = Array(b.utf8)
        var i = left.count - 1, j = right.count - 1, borrow = 0
        var output: [UInt8] = []
        while i >= 0 {
            var digit = Int(left[i] - 48) - borrow
            let other = j >= 0 ? Int(right[j] - 48) : 0
            if digit < other { digit += 10; borrow = 1 } else { borrow = 0 }
            output.append(UInt8(digit - other + 48))
            i -= 1
            j -= 1
        }
        return normalize(String(decoding: output.reversed(), as: UTF8.self))
    }

    private func shift(_ value: String, by places: Int) -> String {
        value == "0" ? "0" : value + String(repeating: "0", count: places)
    }

    private func normalize(_ value: String) -> String {
        let trimmed = value.drop(while: { $0 == "0" })
        return trimmed.isEmpty ? "0" : String(trimmed)
    }
}

The recursion does T(n) = 3T(n/2) + $O(n)$, which solves to $O(n^{log₂3})$. Helpers do string-level addition and subtraction so we never cast the full input to int.

Complexity

• Time: $O(n^{1.585})$.
• Space: $O(n)$ for the recursion stack and intermediate string results.

Summary

Approach	Time	Space
Cast to int	$O(n + m)$	$O(n + m)$
Schoolbook	$O(n · m)$	$O(n + m)$
Karatsuba	$O(n^{1.585})$	$O(n)$

Schoolbook is the canonical interview answer. Know the i + j + 1 positional index.

Test cases

Python

# Quick smoke tests, paste into a REPL or save as test_043.py and run.
# Uses the canonical implementation (Approach 2: schoolbook multiplication).

def multiply(num1, num2):
    if num1 == "0" or num2 == "0":
        return "0"
    n, m = len(num1), len(num2)
    result = [0] * (n + m)
    for i in range(n - 1, -1, -1):
        for j in range(m - 1, -1, -1):
            prod = int(num1[i]) * int(num2[j])
            p1, p2 = i + j, i + j + 1
            total = prod + result[p2]
            result[p2] = total % 10
            result[p1] += total // 10
    start = 0
    while start < len(result) and result[start] == 0:
        start += 1
    return "".join(map(str, result[start:]))

def _run_tests():
    assert multiply("2", "3") == "6"
    assert multiply("123", "456") == "56088"
    assert multiply("0", "12345") == "0"
    assert multiply("99", "99") == "9801"
    assert multiply("1", "1") == "1"
    assert multiply("9999", "9999") == "99980001"
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

TypeScript

function multiply(num1: string, num2: string): string {
    if (num1 === '0' || num2 === '0') return '0';
    const n = num1.length, m = num2.length;
    const result = new Array(n + m).fill(0);
    for (let i = n - 1; i >= 0; i--) {
        for (let j = m - 1; j >= 0; j--) {
            const prod = +num1[i] * +num2[j];
            const p1 = i + j, p2 = i + j + 1;
            const total = prod + result[p2];
            result[p2] = total % 10;
            result[p1] += Math.floor(total / 10);
        }
    }
    let start = 0;
    while (start < result.length && result[start] === 0) start++;
    return result.slice(start).join('') || '0';
}

console.assert(multiply('2', '3') === '6');
console.assert(multiply('123', '456') === '56088');
console.assert(multiply('0', '12345') === '0');
console.assert(multiply('99', '99') === '9801');
console.assert(multiply('1', '1') === '1');
console.assert(multiply('9999', '9999') === '99980001');
console.log('all tests pass');

Related data structures

• Strings, digit strings
• Arrays, result accumulator

Related concepts

• Math and Number Theory, the arithmetic invariant behind digits, divisibility, modulo behavior, and identities.
• Simulation, the explicit state model for executing rules exactly while keeping cases organized.