Skip to content

172 — Multiply Strings

Jump to bottom
rebeloper edited this page Jul 14, 2026 · 4 revisions

172 — Multiply Strings

LeetCode 43 · Medium. Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also as a string. You may not convert either input directly to a native integer type.

🍽️ Intuition

This is grade-school long multiplication, the kind you did on paper before calculators — except the numbers can be too long to fit in any fixed-width integer, so you have to actually carry out the digit-by-digit process instead of leaning on hardware multiplication. Recall how it works on paper: you multiply the bottom number's rightmost digit against every digit of the top number, write that partial row down (shifted appropriately), then move to the next digit of the bottom number and repeat, shifting one more place left each time, and finally add up all the partial rows. The key shortcut that makes this fast in code: instead of generating and adding a whole separate partial row per digit, you can go straight to the point — multiplying digit i of one number by digit j of the other always contributes to position i + j (and possibly carries into i + j + 1) in the final result, so a single result array indexed by digit position can accumulate every digit-pair's contribution directly.

   1 2                digit positions (from the right), 0-indexed:
 x  3 4               num1 = "12" -> digits [2,1]  (reversed)
 -----                num2 = "34" -> digits [4,3]  (reversed)
   4 8    (12 x 4)
 3 6      (12 x 3, shifted one place left)
 -----
 4 0 8

 pair (i=0,j=0): 2*4=8  -> lands at position 0
 pair (i=0,j=1): 2*3=6  -> lands at position 1
 pair (i=1,j=0): 1*4=4  -> lands at position 1 (adds to the 6 already there, carries)
 pair (i=1,j=1): 1*3=3  -> lands at position 2

🚩 Pattern-Recognition Cue

"Multiply two numbers given as strings, without converting to a native integer" is the digit-array long-multiplication signal: treat each string as a reversed array of single digits, and note that multiplying digit at index i by digit at index j always contributes to result position i + j — this index arithmetic is what replaces "align and add" from the paper method.

🐢 Brute Force

The naive instinct is to just parse both strings as numbers, multiply directly, and format the result back as a string. This works — but only as long as both numbers are small enough to fit in a native Int; it breaks the moment either input string represents a number longer than about 18-19 digits.

func multiplyBruteForce(_ num1: String, _ num2: String) -> String {
    guard let a = Int(num1), let b = Int(num2) else {
        return "0"   // one of the inputs overflowed native Int -- this is exactly the failure mode
    }                //  that motivates the digit-by-digit optimal approach below
    return String(a * b)
}

// smoke test
print(multiplyBruteForce("2", "3"))          // "6"
print(multiplyBruteForce("123", "456"))      // "56088"
print(multiplyBruteForce("0", "52"))         // "0"

Big-O: O(n + m) time to parse both strings into native integers (n, m = digit counts), plus one hardware multiplication — but with a hard ceiling: it silently fails (or would overflow/trap) once num1 * num2 no longer fits in Int. O(1) extra space.

🚀 Optimal

Convert each string to a reversed array of digits, and accumulate every digit-pair's product directly into a result array indexed by i + j, propagating carries as you go — exactly grade-school long multiplication, done with index arithmetic instead of writing out shifted partial rows.

func multiply(_ num1: String, _ num2: String) -> String {
    if num1 == "0" || num2 == "0" { return "0" }

    let digits1 = Array(num1).reversed().map { Int(String($0))! }
    let digits2 = Array(num2).reversed().map { Int(String($0))! }
    var result = [Int](repeating: 0, count: digits1.count + digits2.count)

    for i in 0..<digits1.count {
        for j in 0..<digits2.count {
            let product = digits1[i] * digits2[j]
            let lowIndex = i + j
            let highIndex = i + j + 1

            let total = product + result[lowIndex]
            result[lowIndex] = total % 10
            result[highIndex] += total / 10
        }
    }

    while result.count > 1 && result.last == 0 {
        result.removeLast()
    }

    return result.reversed().map { String($0) }.joined()
}

// smoke test — same cases as the brute force
print(multiply("2", "3"))       // "6"
print(multiply("123", "456"))   // "56088"
print(multiply("0", "52"))      // "0"
print(multiply("999", "999"))   // "998001"

Big-O: O(n * m) time — every digit of num1 is paired against every digit of num2 exactly once. O(n + m) space for the result array.

🔑 The Key Insight

The brute force's parse-multiply-format shortcut is only a shortcut because it offloads the real work onto hardware integer multiplication — which has a fixed width and therefore a ceiling. Grade-school long multiplication has no such ceiling because it never needs the whole product to exist as one machine value at once; it only ever needs to know, for one digit-pair at a time, where that pair's contribution lands (i + j) and how much of it overflows into the next position (the carry). Indexing the result array by i + j instead of literally writing out and adding shifted partial rows is what turns the paper method's "generate n rows, then add them all" into a single accumulation pass.

🔗 Related Chapters

  • Arrays and Strings — both input digit arrays (reversed from the original strings) and the result accumulator array are the direct data structure this solution operates on.
  • Matrix Traversal — disclosed as a loose fit, not a strong one: there's no 2-D grid in this problem. The only echo is structural — the nested loop over indices i (from num1's digits) and j (from num2's digits), placing each pair's result at offset i + j, resembles walking an implicit 2-D grid of digit-pair products indexed by two coordinates, the way this chapter's traversals are indexed by row and column. It's a shape resemblance, not a genuine grid-traversal problem.

🧸 Memory Sentence

Multiply Strings is grade-school long multiplication without a calculator — every digit pair's product lands at position i + j in a result array, carries and all, instead of writing out and adding shifted rows by hand.

✅ Check Your Understanding

  1. Why does multiplying digits1[i] by digits2[j] always contribute to result[i + j], regardless of what i and j actually are?
  2. Walk through why result[highIndex] += total / 10 uses += rather than = — what could already be sitting in result[highIndex] before this line runs?
  3. Why is the while result.count > 1 && result.last == 0 cleanup loop necessary at the end, and why does it stop at result.count > 1 rather than being allowed to strip every digit down to an empty array?
  4. The brute force's failure mode is described as breaking once the product overflows Int. At roughly what combined digit-length of num1 and num2 would you expect that to start happening, and why does the optimal approach have no equivalent limit?

⬅️ Previous: Pow(x, n) · Next: Detect Squares ➡️

Clone this wiki locally