43. Multiply Strings

MediumRandomization, Math and Miscellaneous (FAANG add-on)Digit array with carry propagationSchoolbook grid multiplication

Multiply Strings

Given two non-negative integers num1 and num2 represented as strings, return their product also as a string. You must not convert the inputs to integers directly or use any big-integer library.

Open official problem prompt ↗

In plain English

Compute the exact product of two arbitrarily large integers given as text, without relying on the language's native integer arithmetic.

Picture it like this

It is the long-multiplication you did on paper: multiply each digit pair, place it in the right column, and carry overflow leftward.

Example

Input: num1 = "123", num2 = "456"
Output: "56088"
Why: 123 * 456 = 56088, computed digit by digit without native integer conversion.

Constraints

1 <= num1.length, num2.length <= 200num1 and num2 consist of digits onlyNeither has a leading zero, except the number 0 itself

Pattern lesson

See the pattern, then code

Schoolbook grid multiplication

↗

Randomization, Math and Miscellaneous (FAANG add-on)

Uniform random selection, sampling streams, number theory, or precision-heavy parsing.. The digit num1[i] times num2[j] lands in result positions i+j (carry) and i+j+1 (units); summing all pairwise products into a length m+n buffer reproduces grade-school multiplication.

New words, made simpleKnow these before the algorithm

Carry: The tens portion of a two-digit intermediate result that must be added to the next-higher column.
Digit buffer: An integer array that accumulates column sums before final normalization.
Position index: For digits at i and j, their product contributes to buffer slots i+j and i+j+1.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Convert to int and multiply

Explicitly forbidden by the problem and defeats the point in languages without big integers.

Parse both strings to int, multiply, stringify.

Time O(n*m)Space O(n+m)

Best choiceDigit-array long multiplication

Works for any length, uses only single-digit arithmetic, and is the intended solution.

Accumulate every pairwise digit product into a fixed-size buffer, then normalize carries.

Time O(n*m)Space O(n+m)

The rule we keep true

Invariant

After processing digit pair (i, j), res[i+j+1] holds the correct units contribution modulo 10 and any overflow has been added into res[i+j].

Why this is correct

Reasoning

Every product of a digit at power 10^(n-1-i) and a digit at power 10^(m-1-j) contributes to decimal place (n+m-2-i-j), which maps exactly to buffer index i+j+1; summing all contributions and normalizing carries reconstructs the true product.

The algorithm in three movesSay these aloud before coding

1Allocate a result array of length len(num1)+len(num2) filled with zeros

res length = 3+3 = 6

2For each pair of digits from the back, add the product into positions p1=i+j and p2=i+j+1

3*6=18 -> res[5]=8, carry 1 to res[4]

3Push the tens part of each cell into the cell to its left as carry

final digits 0 5 6 0 8 8 -> strip -> 56088

4Join the digits and strip leading zeros

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Readnum1="123", num2="456"

2 · AskHow big is the buffer?

3 · Update stateres=[0,0,0,0,0,0]

4 · ResultLength 6 = 3+3.

Key takeaway

Multiplying 123 by 456 using a six-cell digit buffer with carry.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 3-4Zero shortcut
If either factor is zero the product is zero, avoiding a stray leading-zero string.
2
Lines 6-7Allocate buffer
A product of an n-digit and m-digit number has at most n+m digits.
3
Lines 8-14Accumulate products
Each digit pair adds into p2 (units) and carries the tens into p1.
4
Lines 15-16Finalize
Concatenate the normalized digits and drop leading zeros, guarding the all-zero case.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

Either operand is "0" -> return "0"
Single-digit operands
Products whose length is less than n+m (leading zero must be stripped)
Very long 200-digit inputs

Common beginner mistakes

Forgetting to strip the leading zero when the top buffer cell stays 0
Adding the product only to p2 without carrying into p1
Converting to int, which the prompt forbids
Off-by-one when mapping (i, j) to buffer positions

Check your understanding

Why is the result buffer exactly len(num1)+len(num2) long?

PyPython 3 · solution.py

Optimal

1class Solution:2    def multiply(self, num1: str, num2: str) -> str:3        if num1 == "0" or num2 == "0":4            return "0"5        n, m = len(num1), len(num2)6        res = [0] * (n + m)7        for i in range(n - 1, -1, -1):8            for j in range(m - 1, -1, -1):9                mul = (ord(num1[i]) - 48) * (ord(num2[j]) - 48)10                p1, p2 = i + j, i + j + 111                total = mul + res[p2]12                res[p2] = total % 1013                res[p1] += total // 1014        result = ''.join(map(str, res)).lstrip('0')15        return result if result else "0"

Time complexityO(n*m)Optimized

Space complexityO(n+m)Explained

Interview rehearsal

Explain before you code

25:00

Restate constraints and edge cases
Explain brute force and its bottleneck
State the invariant and complexity

Seen at

MetaAmazonMicrosoft

Multiply Strings

Multiply Strings

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Randomization, Math and Miscellaneous (FAANG add-on)