LeetCode 43 - Multiply Strings

LeetCode Problem 43

Difficulty: 🟡 Medium
Topics: Math, String, Simulation

Solution

Problem Understanding

The problem asks us to multiply two non-negative integers where each integer is provided as a string instead of a numeric type. The result must also be returned as a string. The important restriction is that we cannot directly convert the strings into integers or use any built-in big integer library.

In other words, we must manually simulate the multiplication process exactly the way humans perform multiplication on paper.

The inputs num1 and num2 are strings containing only digit characters from '0' to '9'. Their lengths can be as large as 200 characters, which means the represented numbers can be far larger than what standard integer types can safely store. For example, a 200-digit number cannot fit inside normal 64-bit integer types in Python, Go, Java, or C++.

The output should be the exact decimal representation of the product, without leading zeros unless the answer itself is "0".

The constraints tell us several important things:

• We cannot rely on integer conversion because the numbers may exceed standard numeric limits.
• Since each string can contain up to 200 digits, an algorithm with quadratic complexity is acceptable because 200 × 200 = 40,000 operations is manageable.
• The input is guaranteed to contain only valid digits.
• The input will not contain leading zeros except for the special case "0".

There are several edge cases that can easily cause bugs in a naive implementation.

If either input is "0", the answer must immediately be "0". Forgetting this can produce outputs like "0000".

Carry handling is another common source of mistakes. During multiplication, intermediate values can exceed 9, so carries must propagate correctly across positions.

Leading zeros in the result array can also create issues. Since the multiplication process often produces unused leading positions, we must strip them before building the final string.

Finally, different digit pairs can contribute to the same position in the result. A correct implementation must accumulate these values properly instead of overwriting them.

Approaches

Brute Force Approach

A straightforward brute-force solution would simulate grade-school multiplication very literally. For every digit in num1, we multiply it with every digit in num2, create a partial product string, append the appropriate number of trailing zeros based on position, and then repeatedly add these partial products together using a custom string addition function.

This approach is correct because it mirrors traditional multiplication exactly. Each digit contributes its weighted value, and summing all partial products produces the final answer.

However, this method is inefficient because repeated string additions become expensive. Every partial product may require traversing large portions of previously accumulated results. As the numbers grow larger, the repeated construction and addition of strings creates unnecessary overhead.

Optimal Approach

The key insight is that we do not actually need to build separate partial products. Instead, we can directly accumulate multiplication contributions into a result array.

When multiplying two numbers of lengths m and n, the maximum possible number of digits in the product is m + n. For example:

• 99 × 99 = 9801, which has 2 + 2 = 4 digits
• 123 × 456 = 56088, which has at most 3 + 3 = 6 digits

We can therefore allocate an array of size m + n to store digit contributions directly.

If digits at positions i and j are multiplied, their contribution belongs near position i + j + 1 in the result array. This mirrors how place values work in manual multiplication.

Instead of building temporary strings, we continuously accumulate values and propagate carries in-place. This avoids repeated string addition and gives a clean quadratic-time solution.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(m × n + n additions)	O(m + n)	Builds partial products and repeatedly adds strings
Optimal	O(m × n)	O(m + n)	Directly accumulates products into a result array

Algorithm Walkthrough

1. First, handle the special case where either input is "0". In that situation, the product is immediately "0".
2. Let m be the length of num1 and n be the length of num2. Create a result array of size m + n, initialized with zeros. This array will store individual digits of the final product.
3. Traverse both strings from right to left. We process digits from least significant to most significant because multiplication naturally propagates carries toward more significant positions.
4. For each pair of digits:

• Convert the character digits into integers.
• Multiply them together.
• Determine where this product contributes in the result array.

If the indices are i and j, then:

• The ones place goes to position i + j + 1
• The carry goes to position i + j

5. Add the multiplication result to the current value already stored at result[i + j + 1]. This is important because multiple digit pairs may contribute to the same position.
6. Store the ones digit at result[i + j + 1] using modulo 10.
7. Add the carry value to result[i + j] using integer division by 10.
8. After processing all digit pairs, the result array contains the complete number, but it may begin with leading zeros.
9. Skip all leading zeros while building the final string.
10. Convert the remaining digits into characters and join them into the final answer string.

Why it works

The algorithm works because it exactly models positional decimal multiplication.

When multiplying two digits from positions i and j, their contribution belongs at decimal position i + j + 1 relative to the final result. Every multiplication contribution is accumulated into the correct location, and carries are propagated immediately.

Since every pair of digits is processed exactly once and all carries are preserved, the final array represents the correct decimal expansion of the product.

Python Solution

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):
            for j in range(n - 1, -1, -1):
                digit1 = ord(num1[i]) - ord('0')
                digit2 = ord(num2[j]) - ord('0')

                product = digit1 * digit2

                position_low = i + j + 1
                position_high = i + j

                total = product + result[position_low]

                result[position_low] = total % 10
                result[position_high] += total // 10

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

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

The implementation begins with the important zero check. This avoids unnecessary work and guarantees correct formatting for cases like "0" × "52".

The result array is allocated with size m + n because the maximum number of digits in the product cannot exceed this value.

The nested loops iterate from right to left so that multiplication proceeds from least significant digits toward more significant digits, exactly like manual arithmetic.

For every digit pair, the code computes the multiplication result and determines the correct positions in the result array. The current value already stored at the target position is included because previous multiplications may have contributed there earlier.

The modulo operation extracts the current digit, while integer division computes the carry. The carry is accumulated into the next higher position.

Finally, leading zeros are skipped before constructing the final string.

Go Solution

func multiply(num1 string, num2 string) string {
    if num1 == "0" || num2 == "0" {
        return "0"
    }

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

    result := make([]int, m+n)

    for i := m - 1; i >= 0; i-- {
        for j := n - 1; j >= 0; j-- {
            digit1 := int(num1[i] - '0')
            digit2 := int(num2[j] - '0')

            product := digit1 * digit2

            positionLow := i + j + 1
            positionHigh := i + j

            total := product + result[positionLow]

            result[positionLow] = total % 10
            result[positionHigh] += total / 10
        }
    }

    start := 0
    for start < len(result) && result[start] == 0 {
        start++
    }

    bytes := make([]byte, 0)

    for i := start; i < len(result); i++ {
        bytes = append(bytes, byte(result[i]+'0'))
    }

    return string(bytes)
}

The Go implementation follows the same logic as the Python version, but there are some language-specific differences.

Go strings are byte slices internally, so digit extraction uses expressions like num1[i] - '0'.

Instead of Python lists, Go uses integer slices created with make([]int, m+n).

Since Go does not have a direct equivalent of Python's string join on integer collections, the solution constructs a byte slice and converts it into a string at the end.

Go integers are sufficient here because the largest intermediate multiplication is only 9 × 9 + carry, which easily fits within standard integer ranges.

Worked Examples

Example 1

Input:

num1 = "2"
num2 = "3"

Initial result array:

Index	0	1
Value	0	0

Process digits:

i	j	digit1	digit2	product	total	result array
0	0	2	3	6	6	[0, 6]

After removing leading zeros:

"6"

Example 2

Input:

num1 = "123"
num2 = "456"

Initial result array:

Index	0	1	2	3	4	5
Value	0	0	0	0	0	0

Process multiplications step by step.

Multiply 3 × 6

Operation	Value
product	18
positions	high=4, low=5
updated array	[0, 0, 0, 0, 1, 8]

Multiply 3 × 5

Operation	Value
product	15
positions	high=3, low=4
total	16
updated array	[0, 0, 0, 1, 6, 8]

Multiply 3 × 4

Operation	Value
product	12
positions	high=2, low=3
total	13
updated array	[0, 0, 1, 3, 6, 8]

Multiply 2 × 6

Operation	Value
product	12
positions	high=3, low=4
total	18
updated array	[0, 0, 1, 4, 8, 8]

Multiply 2 × 5

Operation	Value
product	10
positions	high=2, low=3
total	14
updated array	[0, 0, 2, 4, 8, 8]

Multiply 2 × 4

Operation	Value
product	8
positions	high=1, low=2
total	10
updated array	[0, 1, 0, 4, 8, 8]

Multiply 1 × 6

Operation	Value
product	6
positions	high=2, low=3
total	10
updated array	[0, 1, 1, 0, 8, 8]

Multiply 1 × 5

Operation	Value
product	5
positions	high=1, low=2
total	6
updated array	[0, 1, 6, 0, 8, 8]

Multiply 1 × 4

Operation	Value
product	4
positions	high=0, low=1
total	5
updated array	[0, 5, 6, 0, 8, 8]

Final answer after trimming leading zero:

"56088"

Complexity Analysis

Measure	Complexity	Explanation
Time	O(m × n)	Every digit in num1 is multiplied with every digit in num2
Space	O(m + n)	The result array stores at most m + n digits

The nested loops dominate the runtime because each digit pair is processed exactly once. Since the maximum lengths are only 200, this quadratic complexity is efficient enough.

The extra space comes entirely from the result array, which stores the final digits before conversion into a string.

Test Cases

solution = Solution()

assert solution.multiply("2", "3") == "6"  # basic single-digit multiplication

assert solution.multiply("123", "456") == "56088"  # standard multi-digit case

assert solution.multiply("0", "52") == "0"  # left operand is zero

assert solution.multiply("52", "0") == "0"  # right operand is zero

assert solution.multiply("1", "999") == "999"  # multiplication by one

assert solution.multiply("9", "9") == "81"  # single-digit carry generation

assert solution.multiply("99", "99") == "9801"  # multiple carries

assert solution.multiply("123456789", "1") == "123456789"  # identity multiplication

assert solution.multiply("500", "20") == "10000"  # trailing zeros in result

assert solution.multiply("999", "999") == "998001"  # large carry propagation

assert solution.multiply("123456789", "987654321") == "121932631112635269"  # large numbers

assert solution.multiply("1000", "1000") == "1000000"  # powers of ten

assert solution.multiply("25", "4") == "100"  # exact carry into new digit

Test	Why
"2" × "3"	Simplest valid multiplication
"123" × "456"	Standard multi-digit example
"0" × "52"	Verifies zero handling
"52" × "0"	Verifies symmetric zero handling
"1" × "999"	Identity multiplication
"9" × "9"	Single carry generation
"99" × "99"	Multiple carry propagation
"123456789" × "1"	Large identity case
"500" × "20"	Handles trailing zeros correctly
"999" × "999"	Stress test for cascading carries
"123456789" × "987654321"	Large realistic multiplication
"1000" × "1000"	Leading/trailing zero placement
"25" × "4"	Carry creating a new leading digit

Edge Cases

One important edge case occurs when either input is "0". Without a special check, the algorithm could produce outputs like "0000" after processing the result array. The implementation avoids this by immediately returning "0" before performing any multiplication.

Another tricky case involves cascading carries, such as multiplying "999" by "999". Intermediate positions can temporarily exceed 9 multiple times. A buggy implementation may overwrite values instead of accumulating them correctly. This solution always adds into the existing position value before splitting into digit and carry components, ensuring carry propagation remains correct.

Leading zeros in the result array are another common source of bugs. Since the array size is fixed at m + n, the most significant position is not always used. For example, "12" × "12" produces "144", but the array initially has space for four digits. The implementation correctly skips unused leading zeros before constructing the final answer string.

A final subtle case involves products that increase the digit count, such as "25" × "4" = "100". Incorrect carry handling may produce "00" or "0100". The algorithm handles this correctly because carries are propagated into higher positions during every multiplication step.