Skip to main content
Talentd

Multiply Two Polynomials - Solution & Explanation

HardPremiumFree on FleetCodeArrayMath11 min read
Practice this problem

Problem Statement

You are given two integer arrays poly1 and poly2, where the element at index i in each array represents the coefficient of xi in a polynomial.

Let A(x) and B(x) be the polynomials represented by poly1 and poly2, respectively.

Return an integer array result of length (poly1.length + poly2.length - 1) representing the coefficients of the product polynomial R(x) = A(x) * B(x), where result[i] denotes the coefficient of xi in R(x).

 

Example 1:

Input: poly1 = [3,2,5], poly2 = [1,4]

Output: [3,14,13,20]

Explanation:

  • A(x) = 3 + 2x + 5x2 and B(x) = 1 + 4x
  • R(x) = (3 + 2x + 5x2) * (1 + 4x)
  • R(x) = 3 * 1 + (3 * 4 + 2 * 1)x + (2 * 4 + 5 * 1)x2 + (5 * 4)x3
  • R(x) = 3 + 14x + 13x2 + 20x3
  • Thus, result = [3, 14, 13, 20].

Example 2:

Input: poly1 = [1,0,-2], poly2 = [-1]

Output: [-1,0,2]

Explanation:

  • A(x) = 1 + 0x - 2x2 and B(x) = -1
  • R(x) = (1 + 0x - 2x2) * (-1)
  • R(x) = -1 + 0x + 2x2
  • Thus, result = [-1, 0, 2].

Example 3:

Input: poly1 = [1,5,-3], poly2 = [-4,2,0]

Output: [-4,-18,22,-6,0]

Explanation:

  • A(x) = 1 + 5x - 3x2 and B(x) = -4 + 2x + 0x2
  • R(x) = (1 + 5x - 3x2) * (-4 + 2x + 0x2)
  • R(x) = 1 * -4 + (1 * 2 + 5 * -4)x + (5 * 2 + -3 * -4)x2 + (-3 * 2)x3 + 0x4
  • R(x) = -4 -18x + 22x2 -6x3 + 0x4
  • Thus, result = [-4, -18, 22, -6, 0].

 

Constraints:

  • 1 <= poly1.length, poly2.length <= 5 * 104
  • -103 <= poly1[i], poly2[i] <= 103
  • poly1 and poly2 contain at least one non-zero coefficient.

Approach Overview

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.

Solution

We can use the Fast Fourier Transform (FFT) to efficiently compute the product of two polynomials. FFT is an efficient algorithm that can compute the product of polynomials in O(n log n) time complexity.

The specific steps are as follows:

  1. Padding the length Let the result length be m = |A|+|B|-1, and round it up to the nearest power of 2, n, to facilitate divide-and-conquer FFT.
  2. FFT transformation Perform the forward FFT (with invert=False) on both coefficient sequences.
  3. Pointwise multiplication Multiply the corresponding elements in the frequency domain.
  4. Inverse FFT Perform the inverse FFT (with invert=True) on the product sequence, and round the real parts to the nearest integer to obtain the final coefficients.

The time complexity is O(n log n), and the space complexity is O(n), where n is the length of the polynomials.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Naive ConvolutionO(n*m)O(n+m)Small polynomial sizes or quick verification of correctness
FFT-Based MultiplicationO(n log n)O(n)Large polynomials where quadratic multiplication becomes too slow

Video Solution

Python Scripts: 2 Multiply two polynomials • Afiz • 4,325 views views

Frequently Asked Questions

Is Multiply Two Polynomials easy or hard?
Multiply Two Polynomials is typically considered a hard problem because the optimal solution requires understanding the Fast Fourier Transform. While the naive O(n*m) method is straightforward, achieving O(n log n) complexity demands deeper algorithm knowledge.
Multiply Two Polynomials Python/Java solution
Most implementations rely on FFT libraries or custom implementations. Python commonly uses complex-number arrays with recursive or iterative FFT, while Java and C++ solutions implement iterative Cooley–Tuk FFT or use numeric libraries. The core idea remains convolution via FFT.
How to solve Multiply Two Polynomials in O(n log n)?
Use Fast Fourier Transform (FFT). Pad both coefficient arrays to the same power-of-two length, compute their FFTs, multiply the transformed values element-wise, and apply the inverse FFT to recover the resulting coefficients. This converts polynomial multiplication into fast convolution.
What is the best approach for Multiply Two Polynomials?
FFT-based convolution is the most efficient approach. It converts coefficient arrays into frequency space using the Fast Fourier Transform, performs element-wise multiplication, and applies an inverse transform. This reduces the time complexity to O(n log n), making it suitable for very large polynomials.
Is Multiply Two Polynomials asked at Google/Amazon/Meta?
Polynomial multiplication with FFT appears in advanced algorithm interviews and competitive programming problems. Variants show up in companies like Google or Meta when evaluating strong algorithmic fundamentals, especially in roles requiring knowledge of numerical algorithms and signal-processing style techniques.
What data structure is used in Multiply Two Polynomials?
The problem primarily uses arrays to store polynomial coefficients. In the optimized solution, arrays also store complex numbers during FFT transformations. Efficient array manipulation and indexing are key to implementing convolution correctly.
What is the time complexity of Multiply Two Polynomials?
The naive double-loop approach runs in O(n*m) time because every coefficient pair is multiplied. Using the Fast Fourier Transform reduces the complexity to O(n log n) by transforming the multiplication into a convolution in frequency space.

Ready to solve this problem?

Practice Multiply Two Polynomials with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays