Multiply Strings - Solution & Explanation

Problem Overview: You receive two non‑negative integers as strings and must return their product as a string. Built‑in big integer libraries are not allowed, so the multiplication must be simulated digit by digit the same way manual multiplication works.

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

This approach directly simulates how you multiply numbers on paper. Iterate from the last digit of each string, multiply digits, and place the result in a result array sized m + n. The key observation is that multiplying digits at positions i and j contributes to indices i + j and i + j + 1 in the result array. Each product adds to the current value, and the carry is propagated to the previous position. After processing all digit pairs, convert the array into a string while skipping leading zeros. This approach works well because multiplication of each digit pair is independent and fits perfectly with array accumulation.

The algorithm relies mostly on careful index management and carry handling. You iterate from right to left through both strings, compute (num1[i] - '0') * (num2[j] - '0'), and update the result array. Time complexity is O(m*n) since every digit pair is processed once, and space complexity is O(m+n) for the result storage. The logic is straightforward and commonly expected in interviews involving Math and String manipulation.

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

This version keeps the same multiplication principle but structures the computation to reduce intermediate conversions and simplify carry propagation. Instead of repeatedly converting characters to integers and performing multiple string operations, the digits are processed using preallocated arrays and controlled carry updates. Each digit multiplication immediately contributes to the correct position in the result buffer, minimizing temporary values and string concatenation overhead.

The improvement mainly affects implementation efficiency rather than asymptotic complexity. Time complexity remains O(m*n), and space complexity stays O(m+n). The code becomes cleaner when the result array is built first and converted to a string only once at the end. This approach is often described as a simulation of manual multiplication and is a common pattern in Simulation problems where arithmetic operations must be implemented explicitly.

Recommended for interviews: Interviewers expect the schoolbook multiplication simulation using a m + n sized result array. It demonstrates that you understand how digit positions interact during multiplication and how to manage carries correctly. A brute force string‑concatenation style solution shows basic reasoning, but the array‑based simulation demonstrates stronger control over indexing and space usage.