Multiply Two Polynomials - Solution & Explanation

Problem Overview: You are given two polynomials represented as arrays of coefficients. The task is to multiply them and return the resulting polynomial. If A[i] represents the coefficient of x^i in the first polynomial and B[j] represents the coefficient of x^j in the second, the product requires computing coefficients for every power x^(i+j).

Approach 1: Naive Convolution (O(n*m) time, O(n+m) space)

The direct approach mirrors the mathematical definition of polynomial multiplication. Iterate through every coefficient in the first array and multiply it with every coefficient in the second array. Each product contributes to index i + j in the result array. This approach uses two nested loops and accumulates results into a result array of size n + m - 1. Time complexity is O(n*m) because every pair of coefficients is processed. Space complexity is O(n+m) for the output polynomial. This works well for small inputs and is often the first implementation you write to verify correctness.

Approach 2: Fast Fourier Transform (FFT) Convolution (O(n log n) time, O(n) space)

Polynomial multiplication can be transformed into a convolution problem. Instead of computing every pair of coefficients directly, convert both coefficient arrays into point-value form using the Fast Fourier Transform. Once transformed, multiplication becomes element-wise: multiply corresponding complex values from both transforms. Then apply the inverse FFT to convert the result back to coefficient form. Padding both arrays to the next power of two ensures efficient FFT computation and avoids cyclic convolution artifacts.

This approach reduces the complexity from quadratic to O(n log n), which is critical when polynomial degrees reach tens or hundreds of thousands. The algorithm relies heavily on numerical operations and array manipulation, making it closely related to problems involving arrays and numerical algorithms in math. Most competitive programming libraries and scientific computing packages provide optimized FFT implementations, so the main task is structuring the convolution pipeline correctly.

Recommended for interviews: Start by explaining the naive convolution to demonstrate you understand how polynomial multiplication works. Then transition to the FFT optimization and explain why convolution in frequency space reduces complexity. Interviewers usually expect awareness of FFT for large-scale polynomial multiplication because it shows strong algorithmic background beyond basic array manipulation.