Multiply Strings

Medium Arrays & Hashing Right to Left Traversal Original on LeetCode

Multiply Strings is a medium arrays & hashing problem solved with the right to left traversal pattern. The best approach, optimal (position array), runs in O(n · m) time and O(n + m) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (schoolbook with string additions) up.

Problem

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

You may not use a built-in big-number library or convert either input to an integer directly; compute the product digit by digit.

Examples

Example 1

Input
num1 = "12", num2 = "34"
Output
"408"
Why
12 × 34 = 408.

Example 2

Input
num1 = "999", num2 = "99"
Output
"98901"
Why
Carries ripple through every column of the product.

Example 3

Input
num1 = "5021", num2 = "0"
Output
"0"
Why
Anything times zero is "0", with no extra leading zeros.

Constraints

  • 1 <= num1.length, num2.length <= 200
  • Both strings contain only digits and have no leading zeros, except the number 0 itself.
  • Do not convert the inputs to built-in big-integer types or parse them as whole numbers.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 13 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (schoolbook with string additions)O(m · (n + m))O(n + m)
Optimal (position array)O(n · m)O(n + m)

1Brute force (schoolbook with string additions)

TimeO(m · (n + m))Each of the m digits of num2 builds a partial product and adds it to a total of length up to n + m.
SpaceO(n + m)The partial product and the running total.

Multiply num1 by each digit of num2 separately, producing a partial product string, pad it with zeros for its place value, and add it into a running total using digit-by-digit string addition.

  1. If either input is "0", return "0".
  2. For each digit d of num2 from the right (place k = 0, 1, …): partial = num1 × d (single-digit multiply with carry) followed by k zeros.
  3. total = addStrings(total, partial).
  4. Return total.
class Solution {
    public String multiply(String num1, String num2) {
        if (num1.equals("0") || num2.equals("0")) return "0";
        String total = "0";
        for (int k = 0; k < num2.length(); k++) {
            int d = num2.charAt(num2.length() - 1 - k) - '0';
            StringBuilder partial = new StringBuilder();
            int carry = 0;
            for (int i = num1.length() - 1; i >= 0; i--) {
                int p = (num1.charAt(i) - '0') * d + carry;
                partial.append(p % 10);
                carry = p / 10;
            }
            if (carry > 0) partial.append(carry);
            partial.reverse();
            for (int z = 0; z < k; z++) partial.append('0');
            total = add(total, partial.toString());
        }
        return total;
    }

    private String add(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 s = carry;
            if (i >= 0) s += a.charAt(i--) - '0';
            if (j >= 0) s += b.charAt(j--) - '0';
            sb.append(s % 10);
            carry = s / 10;
        }
        return sb.reverse().toString();
    }
}

2Optimal (position array)

TimeO(n · m)Every pair of digits is multiplied exactly once.
SpaceO(n + m)The result array of n + m digits.

The product of an n-digit and an m-digit number has at most n + m digits. Digit num1[i] times digit num2[j] contributes to positions i + j (tens) and i + j + 1 (units) of the result. Add every such product into an int array, carrying as you go from the right, then read the array skipping leading zeros.

  1. If either input is "0", return "0".
  2. pos = int[n + m].
  3. For i from n - 1 down to 0, for j from m - 1 down to 0: sum = d1 × d2 + pos[i + j + 1]; pos[i + j + 1] = sum % 10; pos[i + j] += sum / 10.
  4. Build the string from pos, skipping leading zeros.
class Solution {
    public String multiply(String num1, String num2) {
        if (num1.equals("0") || num2.equals("0")) return "0";
        int n = num1.length(), m = num2.length();
        int[] pos = new int[n + m];
        for (int i = n - 1; i >= 0; i--) {
            for (int j = m - 1; j >= 0; j--) {
                int sum = (num1.charAt(i) - '0') * (num2.charAt(j) - '0') + pos[i + j + 1];
                pos[i + j + 1] = sum % 10;
                pos[i + j] += sum / 10;
            }
        }
        StringBuilder sb = new StringBuilder();
        for (int d : pos) {
            if (sb.length() == 0 && d == 0) continue;
            sb.append(d);
        }
        return sb.toString();
    }
}

Edge cases to test

  • One factor is "0": the answer is exactly "0"
  • Single-digit factors, like "9" × "9"
  • Long inputs (200 digits) whose product does not fit any primitive type
  • Products where every column carries, like 999 × 999

Hints

Hint 1

Do it the way you learned on paper: multiply by one digit at a time, shift, and add.

Hint 2

Digit i of num1 times digit j of num2 always lands in positions i + j and i + j + 1 of the result (indexing from the left).

Hint 3

Accumulate all products into an int array of length m + n, push carries, then skip leading zeros.

FAQ

What is the best time complexity for Multiply Strings?

Optimal (position array) runs in O(n · m) time and O(n + m) extra space. Every pair of digits is multiplied exactly once.

Which pattern does Multiply Strings use?

It is a arrays & hashing problem that uses the right to left traversal pattern. Other problems with the same pattern: Array Leaders, Product of Array Except Self, Next Permutation.

Is there a brute force solution for Multiply Strings?

Yes. Brute force (schoolbook with string additions) takes O(m · (n + m)) time and O(n + m) space. Multiply num1 by each digit of num2 separately, producing a partial product string, pad it with zeros for its place value, and add it into a running total using digit-by-digit string addition.

Which edge cases should I test for Multiply Strings?

One factor is "0": the answer is exactly "0"; Single-digit factors, like "9" × "9"; Long inputs (200 digits) whose product does not fit any primitive type; Products where every column carries, like 999 × 999.