Skip to content

Volume ITechnology

4.28.7 — Multiply Strings ​

LeetCode 43 · Medium

The problem ​

Multiply two non-negative numbers given as strings, and return the product as a string. You may not convert them to integers or use a big-integer library.

Restating the Problem: You are given two numbers represented as strings. You must multiply them and return the result as a string. The catch is that you cannot just convert them to int and multiply them directly, because in the real world (or languages without arbitrary precision), these numbers would overflow standard data types.

  • Constraints to note: Both strings consist only of digits and can be up to 200 characters long.
  • Edge cases: Multiplying by "0" should yield exactly "0", avoiding "000".
"2", "3"       →  "6"
"123", "456"   →  "56088"

Up to 200 digits each.

The brute force, and where it wastes work ​

The "brute force" here isn't an algorithm, but rather the cheating approach: return str(int(num1) * int(num2)). This works natively in Python because Python automatically handles arbitrarily large integers. However, this violates the spirit of the question. The intended naive approach is simulating repeated addition (adding num1 to itself num2 times), but that would take O(10^{\text{len}(num2)}) operations, which is astronomically slow. We must simulate long multiplication.

The pattern ​

Long multiplication, as taught in school — but instead of writing down partial products and adding them up, accumulate everything into one array.

The index formula is the whole problem:

Multiplying digit i of num1 by digit j of num2 contributes to positions i + j and i + j + 1 of the result.

Both indices count from the left, and the result array has length m + n.

Why i + j and i + j + 1. Digit i from the left of an m-digit number has place value 10^{m-1-i}. Multiplying two such digits gives place value 10^{(m-1-i) + (n-1-j)} = 10^{(m+n-2) - (i+j)} — which is position i + j + 1 in an array of length m + n, counting from the left. The carry goes one position further left, at i + j.

Check it on the smallest case rather than trusting the algebra. "12" × "34": the last digits are i = 1 and j = 1, giving i + j + 1 = 3 — the final position of a 4-length array ✓.

The maximum product length ​

Two numbers of m and n digits multiply to at most m + n digits, and at least m + n − 1. So allocate m + n and strip at most one leading zero at the end.

99 × 99 = 9801 — four digits from two twos. 10 × 10 = 100 — three digits, so one leading zero to strip.

The solution ​

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

        m, n = len(num1), len(num2)
        result = [0] * (m + n)  # (2)

        for i in range(m - 1, -1, -1):                    # (3) right to left
            for j in range(n - 1, -1, -1):  # (4)
                product = int(num1[i]) * int(num2[j])  # (5)
                total = product + result[i + j + 1]       # (6) add what is already there

                result[i + j + 1] = total % 10            # (7) keep the units digit
                result[i + j] += total # (8) 10              # carry left

        # strip a single leading zero if present
        start = 1 if result[0] == 0 else 0  # (9)
        return ''.join(map(str, result[start:]))
ts
function multiply(num1: string, num2: string): string {
  if (num1 === "0" || num2 === "0") return "0";  // (1)

  const m = num1.length, n = num2.length;
  const result = new Array(m + n).fill(0);  // (2)

  for (let i = m - 1; i >= 0; i--) {  // (3)
    for (let j = n - 1; j >= 0; j--) {  // (4)
      const product = Number(num1[i]) * Number(num2[j]);  // (5)
      const total = product + result[i + j + 1];  // (6)

      result[i + j + 1] = total % 10;  // (7)
      result[i + j] += Math.floor(total / 10);  // (8)
    }
  }

  const start = result[0] === 0 ? 1 : 0;  // (9)
  return result.slice(start).join('');
}

Line by line ​

This is long multiplication from school, done digit by digit, with every partial result added into one row of answer digits.

(1) Anything times zero is zero. Return "0" directly. Otherwise the answer would come out as a row of zeros like "000".

(2) The answer has at most m + n digits. For example, 99 \times 99 = 9801: two digits times two digits gives four. Each slot will hold one digit of the answer.

(3) Take each digit of num1, from the right, and

(4) multiply it by each digit of num2, from the right.

(5) Multiply the two single digits. int(num1[i]) turns the character '7' into the number 7.

(6) Add whatever is already in the slot this product belongs in. The digit at position i of num1 times the digit at position j of num2 lands in slot i + j + 1. Counting from the left, that is exactly the place value the two digits create together.

(7) Keep only the ones digit in that slot.

(8) Carry the tens part one slot to the left. That slot may now hold 10 or more for a moment. That is fine, because it will be tidied when a later step adds into it and keeps only its ones digit.

(9) The first slot may be an unused 0, as when 12 \times 12 = 144 uses only three of four slots. Skip it, then join the digits into a string.

Trace ​

"12" × "34", result of length 4.

ijdigitsproductpositionafter
112 × 48result[3][0,0,0,8]
102 × 36result[2][0,0,6,8]
011 × 44result[2] → 10[0,1,0,8] — carry to result[1]
001 × 33, plus the 1 already there = 4result[1][0,4,0,8]

Strip the leading zero → "408" ✓ (12 × 34 = 408).

Notice step 3: the 10 was split into a 0 in place and a 1 carried left, and step 4 then added to that carry. That is why += is required.

Edge cases ​

  • A zero input. Line (1) returns "0".
  • "1" times anything. The other number comes back unchanged.
  • The answer fills every slot, like 99 \times 99 = 9801. No leading zero to skip.

Complexity ​

O(mn) time — every pair of digits is multiplied once. O(m + n) space.

  • Time Complexity: O(mn). We have two nested loops, one iterating m times and the other n times. Each inner step does O(1) arithmetic operations.
  • Space Complexity: O(m + n). We allocate a result array of size m + n to store the intermediate digits.

Faster algorithms exist, and naming one is a good finish:

  • Karatsuba — O(n^{1.585}), by reducing four half-size multiplications to three. It is the standard example of divide-and-conquer beating the obvious bound, and 4.12 derives it.
  • Fast Fourier Transform based methods — O(n \log n), used by real big-integer libraries for very large numbers.

Python switches to Karatsuba above a few thousand digits. At 200 digits the schoolbook method wins on constants, which is why this is the right algorithm here.

Where this goes next ​

  • Add Strings, Add Binary — the same carry discipline in one dimension.
  • Plus One — the simplest case. 4.28.5.
  • Big-integer libraries — every one of them is this loop, in a base like 2^{32} rather than 10, because a larger base means fewer digits and fewer carries.

What the interviewer will push on ​

"Derive the index formula." Place values multiply, so the exponents add — and check it on "12" × "34".

"How long can the result be?" m + n at most, m + n − 1 at least, hence a single leading zero to strip.

"Why += and not =?" Several pairs land on the same position, and carries accumulate.

"Why does the carry not need normalising immediately?" The right-to-left order means that position is visited later, and it normalises then.

"Can you do better than O(mn)?" Karatsuba, then FFT. Say why they do not help at 200 digits.

One thing to volunteer: verify the index formula on a two-by-two example out loud before writing the loops. It is the only part of this problem that can be wrong, and checking it costs ten seconds.

Next: 4.28.8 Detect Squares — geometry with a counting map, and the last problem in this group.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet