Multiply Strings - Solution & Explanation

Problem Overview: You are given two non‑negative integers as strings. The task is to multiply them and return the product as a string. Built‑in big integer libraries are not allowed, so you must simulate multiplication the same way humans do on paper.

Approach 1: Elementary Schoolbook Multiplication (O(m*n) time, O(m+n) space)

This approach directly simulates the multiplication method taught in elementary school. Iterate from the last digit of each string (least significant digit). For every pair of digits num1[i] and num2[j], compute their product and add it to a result array at position i + j + 1. The carry goes to i + j. Using an integer array of size m + n ensures every intermediate digit lands in the correct place value. After processing all digit pairs, convert the array to a string while skipping leading zeros.

This works because multiplying digits at indices i and j always contributes to positions based on their place values. Instead of constructing partial strings and shifting them, the algorithm writes the result directly into the correct slots. The algorithm uses basic math operations and digit manipulation with a time complexity of O(m*n) and space complexity of O(m+n). This is the most common and reliable approach used in interviews.

Approach 2: Optimized Schoolbook Multiplication with String Manipulation (O(m*n) time, O(m+n) space)

This variation still follows the schoolbook multiplication idea but focuses on cleaner digit handling and string construction. Instead of repeatedly converting characters during multiplication, digits are processed in a structured way while building partial results. Each digit of the second string multiplies the entire first string, producing a partial product that is shifted according to its position.

Instead of storing everything in a single array immediately, you accumulate intermediate results as strings or arrays and merge them using carry-aware addition. This approach emphasizes string manipulation and careful carry propagation. While the asymptotic complexity remains O(m*n), some implementations can be easier to reason about during debugging because each step mirrors the manual multiplication process.

This method also highlights the idea of simulation problems where you replicate a real-world process step by step. You explicitly model partial products, offsets, and carries, which helps reinforce how positional arithmetic works under the hood.

Recommended for interviews: The array-based schoolbook multiplication is the approach interviewers expect. It demonstrates understanding of place-value arithmetic, efficient carry handling, and avoiding expensive string concatenations. Showing the naive simulation first can communicate your reasoning, but implementing the optimized array solution proves you can translate mathematical insight into efficient code.