Log inSign up
mediumleetcodeNot Started

Multiply Strings

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Strings
Solve on leetcode
Lesson

Problem Statement

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.

Note: You must not use any built-in BigInteger library or convert the inputs to integer directly.

Example 1 · Example:

Input: num1 = "2", num2 = "3"
Output: "6"
Explanation: 2 * 3 = 6.

Example 2 · Example:

Input: num1 = "123", num2 = "456"
Output: "56088"
Explanation: 123 * 456 = 56088.

Constraints:

  • 1 <= num1.length, num2.length <= 200
  • num1 and num2 consist of digits only.
  • Both num1 and num2 do not contain any leading zero, except the number 0 itself.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Simulate long multiplication on digit strings.
  • Map digit product positions directly onto a 1D result array.
  • Strip leading zeros cleanly and handle all boundary conditions.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Multiplying arbitrary-precision integers without BigInteger libraries.
  • String arithmetic and digit simulation problems.

Algorithmic Decision Tree:

  • Grade School Multiplication Simulation
  • Digit Array Arithmetic

Connected Patterns:

Add StringsAdd BinaryPlus One

1. Iterative Row Multiplication and Addition

Intuition

For each digit in num2 from right to left, multiply num1 by that single digit to get an intermediate string, append appropriate number of trailing zeros, and add it to a running total string using a helper addStrings() function.

When to apply: When building directly on top of the Add Strings problem.

Algorithm

  1. If num1 == "0" or num2 == "0", return "0".
  2. Initialize total = "0".
  3. Loop j from num2.length - 1 down to 0:
  4. Multiply num1 by num2[j] with carry -> row.
  5. Append (num2.length - 1 - j) zeros to row.
  6. total = addStrings(total, row).
  7. Return total.

Iterative Row Multiplication and Addition

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [1, 2, |, 3, 4]
Current operationSTEP 1 OF 6
Observation: In traditional paper multiplication, multiply the top number num1 = '12' by each digit of num2
Visual state
Values and pointers at this exact step
array
S
1
2
|
3
4
0
1
2
3
4
↑ ROW 1: num2[1]='4'
Variables at this step
d2
4
row1
48
shift
0
Check / comparison
Multiply num1 ('12') by units digit of num2 ('4').
Decision / next transition
12 * 4 = 48. Row 1 partial product = '48'.
Why this step matters

Observation: In traditional paper multiplication, multiply the top number num1 = '12' by each digit of num2.

Decision: Multiply by units digit 4: 12 × 4 = 48. Store first row as '48'.

Invariant: Each row represents num1 × d_2 × 10k.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4#include <algorithm>
5
6class Solution {
7 std::string addStrings(std::string num1, std::string num2) {
8 std::string res = "";
9 int i = num1.size() - 1, j = num2.size() - 1, carry = 0;
10 while (i >= 0 || j >= 0 || carry) {
11 int sum = carry;
12 if (i >= 0) sum += num1[i--] - '0';
13 if (j >= 0) sum += num2[j--] - '0';
14 carry = sum / 10;
15 res.push_back((sum % 10) + '0');
16 }
17 std::reverse(res.begin(), res.end());
18 return res;
19 }
20public:
21 std::string multiply(std::string num1, std::string num2) {
22 if (num1 == "0" || num2 == "0") return "0";
23 int n = num1.size(), m = num2.size();
24 std::string total = "0";
25
26 for (int j = m - 1; j >= 0; --j) {
27 std::string row = "";
28 int carry = 0, d2 = num2[j] - '0';
29 for (int i = n - 1; i >= 0; --i) {
30 int prod = (num1[i] - '0') * d2 + carry;
31 carry = prod / 10;
32 row.push_back((prod % 10) + '0');
33 }
34 if (carry) row.push_back(carry + '0');
35 std::reverse(row.begin(), row.end());
36 row.append(m - 1 - j, '0');
37 total = addStrings(total, row);
38 }
39 return total;
40 }
41};
42
43int main() {
44 Solution sol;
45 std::cout << sol.multiply("123", "456") << std::endl; // 56088
46 return 0;
47}

Time & Space Complexity

  • Time complexity: O(N * M + M^2) — Performs M multiplications of size N and M string additions of increasing lengths.
  • Space complexity: O(N + M)

Why Brute Force Doesn't Scale:

Single pre-allocated array of size N + M eliminates intermediate string allocations.

Direct in-place carry propagation avoids separate addition routines.

2. Index Mapping Array with Delayed Carry Propagation

Intuition

Allocate an integer array pos of size N + M. Loop i from 0 to N - 1 and j from 0 to M - 1, adding (num1[i] - '0') * (num2[j] - '0') directly to pos[i + j + 1]. Then perform a single right-to-left sweep across pos: set pos[k - 1] += pos[k] / 10 and pos[k] %= 10. Finally, skip leading zeros and build the string.

When to apply: Clean alternative separating arithmetic multiplication from carry resolution.

Algorithm

  1. If num1 == '0' or num2 == '0', return '0'.
  2. Create array pos of size n + m.
  3. Loop i from 0 to n - 1:
  4. Loop j from 0 to m - 1:
  5. pos[i + j + 1] += (num1[i] - '0') * (num2[j] - '0')
  6. Loop k from n + m - 1 down to 1:
  7. pos[k - 1] += pos[k] / 10
  8. pos[k] %= 10
  9. Construct result string skipping leading zeros.
  10. Return result.

Index Mapping Array with Delayed Carry Propagation

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [0, 0, 0, 0]
Current operationSTEP 1 OF 6
Observation: Allocate integer array pos = [0, 0, 0, 0]
Visual state
Values and pointers at this exact step
array
S
0
0
0
0
0
1
2
3
↑ BUFFER pos[4]
Variables at this step
pos
[0,0,0,0]
Check / comparison
Allocate pos array of size m + n = 2 + 2 = 4.
Decision / next transition
Accumulate digit products into pos[i + j + 1] without immediate carrying.
Why this step matters

Observation: Allocate integer array pos = [0, 0, 0, 0].

Decision: Digits multiply and accumulate directly into the buffer. Carries are resolved in a single trailing pass.

Invariant: A product of m and n digits never exceeds m + n digits.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4
5class Solution {
6public:
7 std::string multiply(std::string num1, std::string num2) {
8 if (num1 == "0" || num2 == "0") return "0";
9 int n = num1.size(), m = num2.size();
10 std::vector<int> pos(n + m, 0);
11
12 for (int i = 0; i < n; ++i) {
13 for (int j = 0; j < m; ++j) {
14 pos[i + j + 1] += (num1[i] - '0') * (num2[j] - '0');
15 }
16 }
17
18 for (int k = n + m - 1; k > 0; --k) {
19 pos[k - 1] += pos[k] / 10;
20 pos[k] %= 10;
21 }
22
23 std::string res = "";
24 int idx = 0;
25 while (idx < n + m && pos[idx] == 0) idx++;
26 while (idx < n + m) res += std::to_string(pos[idx++]);
27 return res.empty() ? "0" : res;
28 }
29};
30
31int main() {
32 Solution sol;
33 std::cout << sol.multiply("123", "456") << std::endl; // 56088
34 return 0;
35}

Time & Space Complexity

  • Time complexity: O(N * M) — N * M multiplication additions followed by a single linear pass of length N + M for carries.
  • Space complexity: O(N + M)

3. Direct Position Product with Instant Carry (Optimal)

Intuition

Initialize an array pos of size n + m. Traverse i from n - 1 down to 0 and j from m - 1 down to 0: let mul = (num1[i] - '0') * (num2[j] - '0') + pos[i + j + 1]. Update pos[i + j + 1] = mul % 10 and add the carry pos[i + j] += mul / 10. Build the result string by skipping leading zeros.

When to apply: The standard gold standard solution recommended in all interviews.

Algorithm

  1. If num1 == '0' or num2 == '0', return '0'.
  2. Create pos array of size n + m initialized to 0.
  3. Loop i from n - 1 down to 0:
  4. Loop j from m - 1 down to 0:
  5. mul = (num1[i] - '0') * (num2[j] - '0') + pos[i + j + 1]
  6. pos[i + j + 1] = mul % 10
  7. pos[i + j] += mul / 10
  8. Convert pos to string, ignoring leading zeros.
  9. Return result.

Positional Index Array Multiplication Lattice

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [0, 0, 0, 0]
Current operationSTEP 1 OF 6
Observation: Lengths are m = 2 and n = 2
Visual state
Values and pointers at this exact step
array
S
0
0
0
0
0
1
2
3
↑ pos[i+j+1] = pos[3]
Variables at this step
m
2
n
2
posArrayLen
4
pos
[0,0,0,0]
action
Initialize product buffer
Why this step matters

Observation: Lengths are m = 2 and n = 2. Product can occupy at most m + n = 4 digits.

Decision: Allocate integer buffer pos = [0, 0, 0, 0]. Digits num1[i] * num2[j] will accumulate into indices i + j and i + j + 1.

Invariant: Maximum possible product 99 * 99 = 9801 fits in 4 digits.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4
5class Solution {
6public:
7 std::string multiply(std::string num1, std::string num2) {
8 if (num1 == "0" || num2 == "0") return "0";
9 int n = num1.size(), m = num2.size();
10 std::vector<int> pos(n + m, 0);
11
12 for (int i = n - 1; i >= 0; --i) {
13 for (int j = m - 1; j >= 0; --j) {
14 int mul = (num1[i] - '0') * (num2[j] - '0');
15 int p1 = i + j, p2 = i + j + 1;
16 int sum = mul + pos[p2];
17
18 pos[p2] = sum % 10;
19 pos[p1] += sum / 10;
20 }
21 }
22
23 std::string res = "";
24 for (int p : pos) {
25 if (!(res.empty() && p == 0)) {
26 res.push_back(p + '0');
27 }
28 }
29 return res.empty() ? "0" : res;
30 }
31};
32
33int main() {
34 Solution sol;
35 std::cout << sol.multiply("2", "3") << std::endl; // 6
36 std::cout << sol.multiply("123", "456") << std::endl; // 56088
37 return 0;
38}

Time & Space Complexity

  • Time complexity: O(N * M) — Computes all N * M digit products with O(1) instantaneous carry updates.
  • Space complexity: O(N + M)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Iterative Row Addition (Grade School with Add Strings)O(N * M + M^2)O(N + M)Direct imitation of multi-line addition.Requires implementing both multiply-by-digit and add-strings helper functions.
2.Direct Index Product Accumulator (Optimal)O(N * M)O(N + M)Single array of size N + M, no helper functions, handles carry propagation on the fly.Requires understanding the index mapping (i + j, i + j + 1).
3.Karatsuba MultiplicationOptimalO(N^1.58)O(N log N)Asymptotically faster for millions of digits.High constant factor, completely unnecessary for N <= 200.

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Not initializing product accumulator at pos[p2] before computing sum.

Pitfall 2:

Returning empty string when answer is zero without early return.

Crucial Edge Cases to Validate:

  • Either number is "0" (e.g. num1="0", num2="1234"): Handled upfront by early return 0.
  • Single digit multiplication (num1=2, num2=3): pos is [0, 6], zero trimmer produces 6.
  • Large numbers with maximum digits (200 digits each): Fits in 400-element integer array without numeric overflow.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Clarify that BigInt libraries are disallowed and demonstrate clean manual positional arithmetic.
  2. Walk through the index mapping (i + j, i + j + 1) clearly on the whiteboard.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does the product of digit num1[i] and num2[j] map to indices [i + j] and [i + j + 1]?

Back to DSA Sheet