150NeetCode 150

142.Multiply Strings

MediumMath & Geometry · 7/8
LeetCode #43Video

Problem

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

You must not use any built-in big-integer library and must not convert the inputs to integers directly — the numbers can be up to 200 digits long, far beyond long.

Examples

Input:  num1 = "2", num2 = "3"
Output: "6"
Input:  num1 = "123", num2 = "456"
Output: "56088"
Input:  num1 = "9133", num2 = "0"
Output: "0"

Constraints

  • 1 <= num1.length, num2.length <= 200
  • num1 and num2 consist of digits only.
  • Neither number has leading zeros, except the number 0 itself.

💡 Key Insight

In long multiplication, digit num1[i] times digit num2[j] contributes to positions i + j and i + j + 1 of the product (indexing from the left, product length m + n). So you can accumulate every digit product directly into one int[m + n] array and handle carries as you go — no intermediate strings, no string additions.

Schoolbook with String Addition (Brute Force)

TimeO(n · (m + n))SpaceO(m + n)

Intuition

Exactly what you do on paper: multiply num1 by each digit of num2 to get a partial product, shift it left by appending zeros according to the digit's place, and add all partial products together with a string-addition helper.

Algorithm

  1. If either number is "0", return "0".
  2. For each digit d of num2 from the right (place k = 0, 1, ...):
    • partial = num1 × d (single-digit multiplication with carry), followed by k zeros.
    • result = addStrings(result, partial).
  3. Return result.

Visualization

      1 2 3
    x 4 5 6
    -------
      7 3 8      123 x 6
    6 1 5 0      123 x 5, shifted by 1
  4 9 2 0 0      123 x 4, shifted by 2
  ---------
  5 6 0 8 8

Code

java
class Solution {
    public String multiply(String num1, String num2) {
        if (num1.equals("0") || num2.equals("0")) return "0";
        String result = "0";
        for (int k = 0; k < num2.length(); k++) {
            int d = num2.charAt(num2.length() - 1 - k) - '0';
            StringBuilder partial = new StringBuilder();
            for (int z = 0; z < k; z++) partial.append('0'); // place-value shift
            int carry = 0;
            for (int i = num1.length() - 1; i >= 0; i--) {
                int prod = (num1.charAt(i) - '0') * d + carry;
                partial.append(prod % 10);
                carry = prod / 10;
            }
            if (carry > 0) partial.append(carry);
            result = addStrings(result, partial.reverse().toString());
        }
        return result;
    }

    private String addStrings(String a, String b) {
        StringBuilder sb = new StringBuilder();
        int i = a.length() - 1, j = b.length() - 1, carry = 0;
        while (i >= 0 || j >= 0 || carry > 0) {
            int sum = carry;
            if (i >= 0) sum += a.charAt(i--) - '0';
            if (j >= 0) sum += b.charAt(j--) - '0';
            sb.append(sum % 10);
            carry = sum / 10;
        }
        return sb.reverse().toString();
    }
}

Complexity

  • Time: O(n · (m + n)) — n partial products, each built and added in O(m + n).
  • Space: O(m + n) — the current partial product and running sum.

Complexity Comparison

Approach Time Space
Schoolbook + String Addition O(n · (m + n)) O(m + n)
Position Array O(m · n) O(m + n)

Common Pitfalls

  • Converting to long or BigInteger — overflow, and explicitly disallowed.
  • Forgetting the zero case: without it the position-array method skips every digit and returns "".
  • Writing pos[i + j] = sum / 10 instead of += — that discards an earlier carry already stored there.
  • Assuming the product always has m + n digits — it may have m + n - 1, which is why exactly one leading zero may need skipping.