Multiply Strings

Treat the product as a fixed array of decimal positions. Every digit pair has a predictable destination; carry normalization keeps those positions valid.

The trap is to think of this as string manipulation. It is arithmetic performed over string digits. The useful model is long multiplication:

1. Pair every digit from num1 with every digit from num2.
2. Add each product to its decimal position.
3. Normalize that position to one digit.
4. Move the carry one position left.
5. Serialize the resulting digit array.

This gives a direct O(mn) solution without converting either complete input to an integer.

The solution shape

Let:

• m = len(num1)
• n = len(num2)

The product of an m-digit number and an n-digit number has at most m + n digits. Allocate that many positions:

result = [0] * (m + n)

Then process every pair of input digits. A single carry variable cannot represent the problem because each digit in num1 interacts with every digit in num2, and several pairs can contribute to the same output position.

The restriction against integer conversion applies to the complete strings. Converting one character such as '7' into the digit 7 is allowed. The algorithm never constructs an integer representing all of num1 or num2.

The implementation has six obligations:

• Convert characters individually into digits.
• Visit all m * n digit pairs.
• Map each pair to the correct output position.
• Add to existing values instead of overwriting overlap.
• Normalize each visited position and propagate its carry.
• Remove unused leading zero slots while preserving "0".

Derive the destination index

Let i index a digit in num1, and j index a digit in num2.

The digit at num1[i] has place value:

[ 10^{m - 1 - i} ]

The digit at num2[j] has place value:

[ 10^{n - 1 - j} ]

Their product belongs at:

[ 10^{(m - 1 - i) + (n - 1 - j)} = 10^{m + n - 2 - i - j} ]

Now map that exponent to the result array. Index m + n - 1 represents the units position, so index k represents:

[ 10^{(m+n-1)-k} ]

Set that equal to the exponent above:

[ (m+n-1)-k = m+n-2-i-j ]

Solving for k gives:

[ k = i + j + 1 ]

Therefore, the pair num1[i] * num2[j] belongs at:

position = i + j + 1

That + 1 is worth deriving. Memorizing it is an invitation to make an off-by-one error under interview pressure.

For "123" and "45":

• 3 * 5 contributes to the units position.
• 3 * 4 contributes to the tens position.
• 2 * 5 also contributes to the tens position.

Those last two products overlap, so the second contribution must be added to the first.

Normalize each position

For a pair of digits, first read the value already stored at its destination:

total = result[position] + digit1 * digit2

Then split total into:

digit = total % 10
carry = total // 10

Store the normalized digit in the current position:

result[position] = total % 10

Move the carry to the next more significant position:

result[position - 1] += total // 10

The carry goes to position - 1 because moving one place left multiplies the value by ten.

Accumulator invariant: After each pair update, the processed contributions have the same numeric value as the accumulator. The current position contains one normalized decimal digit; positions to its right are closed, while the current position and positions to its left may still receive later contributions.

That temporal detail matters. A position can be normalized now and revisited later by another digit pair. Normalized does not necessarily mean final.

The += operation is essential:

result[position - 1] += carry

A more significant position may already contain a product or an earlier carry. Assignment would destroy that contribution.

Derive the algorithm before coding

The long multiplication process becomes:

if either input is "0":
    return "0"

result = array of m + n zeroes

for i from m - 1 down to 0:
    for j from n - 1 down to 0:
        digit1 = value of num1[i]
        digit2 = value of num2[j]

        position = i + j + 1
        total = result[position] + digit1 * digit2

        result[position] = total % 10
        result[position - 1] += total // 10

skip leading zero slots

return the remaining digits joined together

There are simpler-looking approaches that do not satisfy the same contract:

• Repeated addition depends on the numeric value of an input, not its string length.
• Whole-string integer conversion violates the problem constraint.
• Building shifted partial-product strings works, but creates more temporary representation and hides the overlap that the accumulator makes explicit.

The accumulator is the better interview representation because every update has a visible destination and a visible preservation rule.

Dry-run: 123 × 45

Use:

num1 = "123"
num2 = "45"

The accumulator has 3 + 2 = 5 positions:

result = [0, 0, 0, 0, 0]

Process both inputs from right to left. The table exposes every state needed to verify the code:

Pair	position	Existing value	Product	total	New digit	Carry added left	Accumulator
3 × 5	4	0	15	15	5	1 to index 3	[0, 0, 0, 1, 5]
3 × 4	3	1	12	13	3	1 to index 2	[0, 0, 1, 3, 5]
2 × 5	3	3	10	13	3	1 to index 2	[0, 0, 2, 3, 5]
2 × 4	2	2	8	10	0	1 to index 1	[0, 1, 0, 3, 5]
1 × 5	2	0	5	5	5	0	[0, 1, 5, 3, 5]
1 × 4	1	1	4	5	5	0	[0, 5, 5, 3, 5]

Two details deserve attention.

First, 2 × 5 targets the same position as 3 × 4. It starts with the existing value 3, producing:

total = 3 + 10 = 13

That is why the algorithm must accumulate instead of overwrite.

Second, 1 × 5 later revisits position 2. That position was previously changed from 2 to 0 when 2 × 4 produced a carry:

total = 2 + 8 = 10

The position is normalized again when the later contribution arrives. The current digit is clean; the surrounding ledger is still active.

After all pairs:

result = [0, 5, 5, 3, 5]

The leading zero is unused capacity, so the output is:

"5535"

The classic destination mistake is:

result[i + j]

instead of:

result[i + j + 1]

Derive the place value first. Then the index is translation, not guesswork.

Python implementation

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

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

        for i in range(m - 1, -1, -1):
            digit1 = ord(num1[i]) - ord("0")

            for j in range(n - 1, -1, -1):
                digit2 = ord(num2[j]) - ord("0")

                position = i + j + 1
                total = result[position] + digit1 * digit2

                result[position] = total % 10
                result[position - 1] += total // 10

        start = 0
        while start < len(result) - 1 and result[start] == 0:
            start += 1

        return "".join(str(digit) for digit in result[start:])

The code maps directly to the derivation:

• position = i + j + 1 is the place-value destination.
• result[position] is the existing accumulated contribution.
• total % 10 keeps the current position as one decimal digit.
• total // 10 is added to position - 1, the next more significant position.

The character conversion is local:

ord("7") - ord("0") == 7

Using int(num1[i]) would also be valid. Neither approach converts the complete input string.

The early zero check is not required for correctness, but it makes the output rule explicit and avoids unnecessary pair processing. The final scan removes leading capacity slots while preserving one slot for a zero result.

Correctness and failure modes

The correctness argument follows the accumulator invariant.

1. Every pair of input digits is visited exactly once.
2. The place-value derivation sends each pair to result[i + j + 1].
3. Adding to the existing value preserves all overlapping contributions.
4. Replacing total with total % 10 and adding total // 10 one position left preserves the numeric value of that column.
5. After all pairs are processed, the accumulator represents the complete product.
6. Removing unused leading zero slots changes only the representation, not the numeric value.

The array has m + n slots because that is the maximum possible product length. Products with fewer digits leave one or more leading slots unused.

Test cases should attack the state model, not just easy arithmetic:

Inputs	Expected result	What it checks
"0", "12345"	"0"	Zero handling
"1", "987"	"987"	Identity behavior
"7", "8"	"56"	Single-digit multiplication
"10", "20"	"200"	Internal zeroes and carry
"99", "99"	"9801"	Overlapping carries
"123", "45"	"5535"	Destination mapping
Two inputs whose product uses all capacity slots	Full-length product	Leading-slot capacity

Common bugs are mechanical:

• Wrong destination: using i + j shifts every product left.
• Overwriting overlap: assigning the product discards existing contributions.
• Dropping carry: keeping only total % 10 loses higher place values.
• Skipping normalization: leaving total in a slot creates a non-digit entry.
• Removing every zero: a zero product must return "0", not an empty string.
• Resetting the accumulator: recreating result inside a loop loses earlier work.
• Assuming every slot is used: the allocated array may contain leading zero capacity.

A useful debugging habit is to print the accumulator after each pair for "123" and "45". Read the state, trace the update, and compare it with the table. The failure usually reveals whether the bug is destination, overlap, or carry.

Complexity

The nested loops process every pair of digits once:

[ O(mn) ]

The result array has m + n entries, and the output has at most that many digits:

[ O(m+n) ]

auxiliary space.

The work depends on the lengths of the strings, not on the numeric magnitude of the values they represent.

The reusable reasoning move

The durable lesson is narrower than “use an array for multiplication”:

When many local interactions contribute to predictable positions, derive each destination, accumulate overlap there, and normalize the state without changing its numeric meaning.

Before coding, write down:

1. The destination formula for one pair of input elements.
2. The exact meaning of one accumulator slot.
3. The operation that preserves that meaning after each update.

Then dry-run an example where two pairs collide in the same position. If you can predict the accumulator before writing the nested loops, the implementation is translation. If you cannot, the code is still guesswork.