How do you solve Multiply Strings?

Initialize an array of zeros with length equal to the sum of the input lengths. Reverse both input strings. For each digit in num1, multiply by each digit in num2, add the product to the corresponding position in the result array, and propagate carry to the next position. After processing all pairs, reverse the result array, skip leading zeros, and join the digits into the final string.

What pattern does Multiply Strings use?

The Pattern: Simulation (Manual Digit-by-Digit Multiplication) The Heuristic: When direct numeric conversion is disallowed, simulate arithmetic operations by processing digits in reverse order, accumulating partial results in an array, and carefully managing carry propagation to build the final result.

Multiply Strings — Simulation

Q: What is the time complexity of Multiply Strings?

O(m * n). The algorithm performs a nested loop over the digits of num1 and num2, each of length m and n respectively, resulting in O(m * n) multiplications and additions.

Problem

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string without using built-in big integer libraries or direct integer conversion.

1 ≤ num1.length, num2.length ≤ 200
num1 and num2 consist of digits only.
Both num1 and num2 do not contain leading zeros, except the number 0 itself.

Example

Input: num1 = "123", num2 = "456"

Output: "56088"

A brute-force approach would convert the strings to integers and multiply directly, but this is disallowed. Instead, the algorithm simulates the multiplication process digit by digit, similar to how multiplication is done by hand. For example, multiplying '3' by '6' yields 18, which is split into a carry and a remainder. These partial products are accumulated in an array representing the final number in reverse order. After processing all digit pairs, the array is reversed and leading zeros are trimmed to produce the final string result.

Approach

Straightforward Solution

A naive approach would convert the entire strings to integers and multiply, but this is not allowed due to input size and problem constraints.

Core Observation

Multiplying two numbers digit by digit produces partial products that align according to their place values. Each digit multiplication affects two positions in the result array: the current position and the next higher position due to carry-over.

Path to Optimal

Preview

The key insight is to simulate the multiplication process manually by reversing the input strings to align least significant digits, multiply each digit pair, accumulate the results in a fixed-size array, and handle carry propagation immediately…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Initialize an array of zeros with length equal to the sum of the input lengths. Reverse both input strings…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(m * n)

The algorithm performs a nested loop over the digits of num1 and num2, each of length m and n respectively, resulting in O(m * n) multiplications and additions.

Space

O(m + n)

The result array has length m + n to hold the maximum possible number of digits in the product. This auxiliary space is necessary to store intermediate and final results.

Solution

Python

1class Solution:
  def multiply(self, num1: str, num2: str) -> str:
      if "0" in [num1, num2]:
          return "0"
      
      res = [0] * (len(num1) + len(num2))
      num1, num2 = num1[::-1], num2[::-1]
8
      for i1 in range(len(num1)):
          for i2 in range(len(num2)):
              digit = int(num1[i1]) * int(num2[i2])
              res[i1 + i2] += digit
              res[i1 + i2 + 1] += (res[i1 + i2] // 10)
              res[i1 + i2] = res[i1 + i2] % 10
      
      res, beg = res[::-1], 0
      while beg < len(res) and res[beg] == 0:
          beg += 1
      
      res = map(str, res[beg:])
      return "".join(res)

Step-by-Step Solution

1

Handle Zero Edge Case and Initialize Result Array

3if "0" in [num1, num2]:
4    return "0"
6res = [0] * (len(num1) + len(num2))

Objective

To quickly return '0' if either input is zero and prepare an array to accumulate digit-wise multiplication results.

Key Insight

If either number is '0', the product is trivially '0', so an early return avoids unnecessary computation. Initializing an array of length equal to the sum of input lengths guarantees enough space to hold the maximum possible digits of the product, preventing overflow and simplifying carry management.

Interview Quick-Check

Core Logic

Early return on zero inputs prevents unnecessary processing and handles a common edge case efficiently.

Core Logic

Allocating a result array of length len(num1) + len(num2) ensures space for the largest possible product.

Common Pitfalls & Bugs

Forgetting to handle the zero input case leads to incorrect results or extra computation.

2

Reverse Inputs to Align Least Significant Digits

To reverse both input strings so that digit indices correspond to increasing place values, simplifying multiplication and carry handling.

3

Multiply Digits and Accumulate Partial Products with Carry Propagation

To perform digit-by-digit multiplication, accumulate partial sums in the result array, and propagate carries immediately to maintain correct digit values.

4

Finalize Result by Removing Leading Zeros and Constructing Output String

To reverse the accumulated result array back to normal order, skip leading zeros, and convert digits to a string for the final output.

3 more steps with full analysis available on Pro.

Line Analysis

This solution has 2 Critical lines interviewers watch for.

Line 3 Critical

if "0" in [num1, num2]:

Check if either input string is '0' and return '0' immediately.

This early exit handles the trivial multiplication case where the product is zero, avoiding unnecessary computation and ensuring correctness for zero inputs.

Line 13 Critical

res[i1 + i2 + 1] += (res[i1 + i2] // 10)

Add carry-over to the next position in the result array.

Propagating carry immediately ensures each position holds a single digit, maintaining the correctness of the intermediate state and avoiding extra passes.

Full line-by-line criticality + rationale for all 15 lines available on Pro.

Test Your Understanding

Why is it necessary to reverse the input strings and accumulate results in a fixed-size array rather than directly building the result string?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Multiply Strings from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Multiply Strings drill

or drill a free problem

1	`class Solution:`
2	`def multiply(self, num1: str, num2: str) -> str:`
3	`if "0" in [num1, num2]:`
4	`return "0"`
5
6	`res = [0] * (len(num1) + len(num2))`
7	`num1, num2 = num1[::-1], num2[::-1]`
8
9	`for i1 in range(len(num1)):`
10	`for i2 in range(len(num2)):`
11	`digit = int(num1[i1]) * int(num2[i2])`
12	`res[i1 + i2] += digit`
13	`res[i1 + i2 + 1] += (res[i1 + i2] // 10)`
14	`res[i1 + i2] = res[i1 + i2] % 10`
15
16	`res, beg = res[::-1], 0`
17	`while beg < len(res) and res[beg] == 0:`
18	`beg += 1`
19
20	`res = map(str, res[beg:])`
21	`return "".join(res)`