The O(n) Club: Multiply Strings Without Overflow (LeetCode 43 Edition)

The O(n) Club: Multiply Strings Without Overflow (LeetCode 43 Edition)

⚡ TL;DR

Stop trying to turn strings into integers—the numbers are too big, your int is too small, and frankly, Java called to ask why you hate its type system. If you want to multiply two massive numbers handed to you as strings, just channel your inner elementary schooler: do digit-by-digit multiplication in reverse, stack all those partial products, and babysit your carries like they’re toddlers at a birthday party.

// Not for production, but you get the idea.
String multiply(String num1, String num2) {
    if ("0".equals(num1) || "0".equals(num2)) return "0";
    int[] res = new int[num1.length() + num2.length()];
    for (int i = num1.length() - 1; i >= 0; i--)
        for (int j = num2.length() - 1; j >= 0; j--)
            res[i + j + 1] += (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
    for (int k = res.length - 1; k > 0; k--) {
        res[k - 1] += res[k] / 10;
        res[k] %= 10;
    }
    StringBuilder sb = new StringBuilder();
    int p = res[0] == 0 ? 1 : 0;
    while (p < res.length) sb.append(res[p++]);
    return sb.toString();
}

🧠 How Devs Usually Mess This Up

Nothing says “algorithmic panic” like seeing two string numbers and muttering “Oh, just parse them—what’s the worst that could happen?” The worst: a NumberFormatException when the input is longer than your LinkedIn connections. Or, you try to be clever, multiply digits but slip up on carry handling or index placement, and your result looks less like multiplication and more like a ransom note.

🔍 What’s Actually Going On

This is just schoolroom multiplication, minus the smell of dry-erase markers. Visualize numbers on lined paper, multiply every digit of num1 by every digit of num2 (last to first), and keep adding at the right shifted place. But since we’re not allowed to use mega-integers or real objects, we use an array to hold all partial sums. At the end, you add up carries properly—because leaking values to the wrong index is basically the quantum tunneling of coding mistakes.

🛠️ PseudoCode

• Step 1: Return “0” if You See a Zero
  

  if (num1.equals("0") || num2.equals("0")) return "0";

  If either number is zero, your answer is always zero. No need to break a sweat.
• Step 2: Pre-allocate Your Result Array
  

  int[] result = new int[num1.length() + num2.length()];

  Make room for the biggest possible answer—because 999 x 99 doesn’t fit neatly into 3 digits, trust me.
• Step 3: Do the Multiply-and-Dump
  

  for (int i = num1.length() - 1; i >= 0; i--)
      for (int j = num2.length() - 1; j >= 0; j--)
          result[i + j + 1] += (num1.charAt(i) - '0') * (num2.charAt(j) - '0');

  Reverse traverse each string. Pair up digits. The answer lands in result[i + j + 1]—because elementary math is zero-indexed now.
• Step 4: Handle Carries Like an Adult
  

  for (int k = result.length - 1; k > 0; k--) {
      result[k - 1] += result[k] / 10;
      result[k] %= 10;
  }

  No digit can be bigger than 9, unless you want an unsolvable Sudoku. Move overflow left with modular compassion.
• Step 5: Build That Result String
  

  StringBuilder sb = new StringBuilder();
  int p = result[0] == 0 ? 1 : 0;
  while (p < result.length) sb.append(result[p++]);
  return sb.toString();

  Always skip leading zeros—unless you like prepping mysterious bug reports for QA.

💻 The Code

public String multiply(String num1, String num2) {
    if ("0".equals(num1) || "0".equals(num2)) return "0";
    int m = num1.length(), n = num2.length();
    int[] res = new int[m + n];
    for (int i = m - 1; i >= 0; i--) {
        int d1 = num1.charAt(i) - '0';
        for (int j = n - 1; j >= 0; j--) {
            int d2 = num2.charAt(j) - '0';
            res[i + j + 1] += d1 * d2;
        }
    }
    // Carry pass
    for (int k = res.length - 1; k > 0; k--) {
        res[k - 1] += res[k] / 10;
        res[k] %= 10;
    }
    // Build output
    StringBuilder sb = new StringBuilder();
    int p = res[0] == 0 ? 1 : 0;
    while (p < res.length) sb.append(res[p++]);
    return sb.toString();
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Forgot the zero check? Congrats, you’ll be debugging a mysterious string of zeros for hours.
• Misaligning digits? The magical i + j + 1 is not optional. Get it wrong, and you’ll invent your own broken calculator.
• Carry gone wild? If you only handle this for one index, you’re about to launch a collection of silent bugs into production.
• Space and time? O(m*n) for both. You’d save more by not multiplying at all.

🧠 Interviewer Brain-Tattoo

If you can juggle digit indices and wrangle carries without BigInteger, you’re basically qualified to run a hardware wallet—or at least, not freak out the next time you see a “size constraint” in bold.