Multiply Strings LeetCode 43 Guide

LeetCode 43 Multiply Strings gives you two non-negative integers num1 and num2 represented as strings and asks you to return their product, also as a string. The key constraint: you must not use any built-in BigInteger library or convert the inputs directly to integers. The numbers can be extremely large — up to 200 digits each — far exceeding what any native 64-bit integer can hold.

This problem is the multiplication analogue of Add Binary and Plus One: instead of adding two numbers, you multiply them using the same digit-by-digit approach taught in elementary school. The challenge is organizing the partial products correctly so they accumulate at the right positions in the result without overflow.

Understanding the position mapping — which positions in the result a product digit contributes to — is the entire key to the solution. Once you internalize the index formula, the rest is mechanical: a nested loop for products, a carry pass, and a leading-zero strip.

Grade-school multiplication works by multiplying each digit of one number by each digit of the other, shifting the partial products by the appropriate power of ten, and summing all partial products. For two numbers with m and n digits respectively, this produces up to m*n individual digit products, each contributing to a specific position in the result.

The critical insight is the position mapping: when you multiply the digit at index i of num1 (from the left) by the digit at index j of num2, the resulting value contributes to positions i+j and i+j+1 in a result array of size m+n. The lower-order contribution lands at i+j+1 and the higher-order carry lands at i+j.

Rather than computing and shifting separate partial products as you do on paper, you accumulate all contributions directly into a single result array. This avoids the intermediate addition step entirely and makes the algorithm both elegant and efficient.

The product of an m-digit number and an n-digit number has at most m+n digits. This is because the maximum m-digit number is 10^m - 1 and the maximum n-digit number is 10^n - 1, and their product is less than 10^(m+n). Allocating a result array of exactly size m+n guarantees it can hold any possible product without overflow.

Initialize the result array with all zeros. As you iterate over every pair of digit indices (i, j), compute the product of the two digits and add it to result[i+j+1]. You do not process carries during this accumulation phase — you simply let the values at each position grow as large as they need to. After all pairs are processed, a single right-to-left pass handles all the carries at once.

This two-phase approach — accumulate first, carry later — is what makes the algorithm clean. It decouples the product computation from carry propagation, eliminating any risk of a carry at one position cascading and corrupting a position you have not yet accumulated into.

During the accumulation phase, result[i+j+1] can grow well beyond 9. For example, if both digits are 9, their product is 81 — but the slot may have received contributions from many other digit pairs as well. A result slot can hold a value up to 9*9*min(m,n) before the carry pass. This is fine; the carry pass normalizes everything afterward.

After accumulating all products, iterate the result array from right to left (from index m+n-1 down to index 1). At each index k, compute carry = result[k] / 10 (integer division) and remainder = result[k] % 10. Set result[k] = remainder and add carry to result[k-1]. This single pass is sufficient because carries can only propagate left, and we are already moving left.

After the carry pass, result[0] may still be 0 (if the total product requires fewer than m+n digits). Strip any leading zeros from the front. The only special case: if all remaining digits are 0, the result should be "0" not "" — ensure at least one digit remains after stripping.

After the carry pass, the result array may begin with one or more zeros. This happens whenever the product requires fewer than m+n digits — for example, 12 * 34 = 408 has 3 digits, not 4. The result array of size 4 will have a leading zero at index 0 after the carry pass. Strip these leading zeros before joining.

The stripping logic: find the first non-zero index in the result array and slice from there. In Python: "".join(str(d) for d in result).lstrip("0") or "0". In Java: use a StringBuilder, skip leading zeros, then append remaining digits. If the entire array is zeros, return "0".

A special case worth testing: "0" * anything = "0". After the accumulation and carry pass, the result array will be all zeros. The stripping logic must return "0" rather than an empty string. Most implementations handle this naturally by using "0" as the fallback when stripping removes all digits.

Python solution: def multiply(num1, num2): m, n = len(num1), len(num2); res = [0] * (m + n); for i in range(m - 1, -1, -1): for j in range(n - 1, -1, -1): p = (ord(num1[i]) - ord("0")) * (ord(num2[j]) - ord("0")); res[i+j+1] += p; for k in range(m+n-1, 0, -1): res[k-1] += res[k] // 10; res[k] %= 10; return "".join(map(str, res)).lstrip("0") or "0". The nested loop iterates from the end of both strings since digits at higher indices are less significant.

Java solution: public String multiply(String num1, String num2) { int m = num1.length(), n = num2.length(); int[] res = new int[m + n]; for (int i = m - 1; i >= 0; i--) { for (int j = n - 1; j >= 0; j--) { int p = (num1.charAt(i) - '0') * (num2.charAt(j) - '0'); res[i+j+1] += p; } } for (int k = m+n-1; k > 0; k--) { res[k-1] += res[k] / 10; res[k] %= 10; } StringBuilder sb = new StringBuilder(); for (int d : res) if (sb.length() > 0 || d != 0) sb.append(d); return sb.length() == 0 ? "0" : sb.toString(); }

Time complexity: O(m*n) for the nested product loop, where m and n are the lengths of the two strings. The carry pass and string join are both O(m+n). Space complexity: O(m+n) for the result array. Both solutions are clean, handle all edge cases including zero inputs, and require no BigInteger or integer conversion.

Plus One (LeetCode 66) is the simplest member of this family: add 1 to a digit array with right-to-left carry propagation. Add Binary (LeetCode 67) adds two binary strings with the same backward iteration and carry pattern, but in base 2. Add Strings (LeetCode 415) adds two decimal digit strings, which is essentially a generalization of Plus One to two operands — directly analogous to what Multiply Strings does for multiplication.

Pow(x, n) (LeetCode 50) uses fast exponentiation rather than digit arithmetic, but shares the theme of implementing a math primitive without relying on built-in arbitrary-precision support. Happy Number (LeetCode 202) repeatedly sums squares of digits, combining digit extraction with cycle detection. Both problems require comfort with digit-level math operations.

The string arithmetic family — Plus One, Add Binary, Add Strings, Multiply Strings — forms a coherent progression of difficulty. Mastering the position-based accumulation pattern in Multiply Strings gives you the mental model for handling any grade-school arithmetic operation on large numbers represented as strings or digit arrays, which appears in competitive programming and system design interviews alike.