Multiply Strings
Multiply two numbers given as strings without converting them, using grade-school multiplication into an array of m + n digit positions.
Problem Understanding
Multiply Strings: given two non-negative integers num1 and num2 as strings, return their product as a string. You may not use a big-integer library or convert the inputs to integers directly.
Examples: "2" × "3" = "6", and "123" × "456" = "56088".
The Intuition: Every Digit Pair Has a Fixed Place
Long multiplication on paper multiplies every digit of one number by every digit of the other and adds the results in the right columns. Do the same with an array:
- The answer has at most
m + ndigits, so allocateposof that length. num1[i] × num2[j]belongs atpos[i + j + 1], with its tens carried topos[i + j].- Walk both strings from the right, so carries flow left into positions that are visited later.
Two indices sweeping a pair of strings from the end is the same shape as adding two numbers digit by digit, a cousin of the two pointers pattern. Leading zeros only appear at the front, as in Remove K Digits.
Interactive Walkthrough
num1 and num2 sit right-aligned above pos, the way you write long multiplication. Each step multiplies digits i and j; the ones position is solid and the carry position is tinted. Try All nines to see every position used.
Dry Run Table
Input: num1 = "123", num2 = "456", so pos has 6 places.
| i, j | Digits | Product + pos[i+j+1] | pos after |
|---|---|---|---|
| 2, 2 | 3 × 6 | 18 + 0 = 18 | 0 0 0 0 1 8 |
| 2, 1 | 3 × 5 | 15 + 1 = 16 | 0 0 0 1 6 8 |
| 2, 0 | 3 × 4 | 12 + 1 = 13 | 0 0 1 3 6 8 |
| 1, 2 | 2 × 6 | 12 + 6 = 18 | 0 0 1 4 8 8 |
| 1, 1 | 2 × 5 | 10 + 4 = 14 | 0 0 2 4 8 8 |
| 1, 0 | 2 × 4 | 8 + 2 = 10 | 0 1 0 4 8 8 |
| 0, 2 | 1 × 6 | 6 + 4 = 10 | 0 1 1 0 8 8 |
| 0, 1 | 1 × 5 | 5 + 1 = 6 | 0 1 6 0 8 8 |
| 0, 0 | 1 × 4 | 4 + 1 = 5 | 0 5 6 0 8 8 |
Answer: 056088 without its leading zero: "56088".
The Solution Template
One position array, filled from the right. A position can briefly hold more than 9; it is settled when the loop next uses it as the ones place.
Multiply Strings Code
1var multiply = function(num1, num2) {2 const m = num1.length, n = num2.length;3 const pos = Array(m + n).fill(0);4 for (let i = m - 1; i >= 0; i--) {5 for (let j = n - 1; j >= 0; j--) {6 const mul = Number(num1[i]) * Number(num2[j]);7 const total = mul + pos[i + j + 1];8 pos[i + j + 1] = total % 10;9 pos[i + j] += Math.floor(total / 10);10 }11 }12 const result = pos.join('').replace(/^0+/, '');13 return result || '0';14};
Edge Cases & Common Mistakes
- A zero input: every position stays 0; return
"0", not an empty string. - Leading zeros: the product may have
m + n - 1digits; strip the front zero. - Off-by-one positions: the ones digit goes to
i + j + 1, the carry toi + j. - Converting to int or long: overflows for long inputs and is not allowed.
- Building the result by repeated string addition: correct but slower and far more code than the position array.
Summary
Allocate m + n positions. For every digit pair from the right, add the product to pos[i + j + 1], keep the last digit there and carry the rest to pos[i + j]. Join, strip leading zeros, and return "0" if nothing is left. O(m · n) time, O(m + n) space.
More practice: DSA interview questions with answers · patterns cheat sheet