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.

Description Hints 1 Solution Video 2:16

3549. Multiply Two Polynomials

Hard59.2% acceptancePremium elsewhere, free here

You are given two integer arrays poly1 and poly2, where the element at index i in each array represents the coefficient of xⁱ 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 xⁱ in R(x).

Example 1:

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

Output: [3,14,13,20]

Explanation:

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

Example 2:

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

Output: [-1,0,2]

Explanation:

A(x) = 1 + 0x - 2x² and B(x) = -1
R(x) = (1 + 0x - 2x²) * (-1)
R(x) = -1 + 0x + 2x²
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 - 3x² and B(x) = -4 + 2x + 0x²
R(x) = (1 + 5x - 3x²) * (-4 + 2x + 0x²)
R(x) = 1 * -4 + (1 * 2 + 5 * -4)x + (5 * 2 + -3 * -4)x² + (-3 * 2)x³ + 0x⁴
R(x) = -4 -18x + 22x² -6x³ + 0x⁴
Thus, result = [-4, -18, 22, -6, 0].

Constraints:

1 <= poly1.length, poly2.length <= 5 * 10⁴
-10³ <= poly1[i], poly2[i] <= 10³
poly1 and poly2 contain at least one non-zero coefficient.

Topics

Array Math

Hints open one at a time

Hint 1

Use Fast Fourier Transform (FFT)

2:16

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
  def solve(self):
      pass


Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

[3,2,5]
[1,4]

Input

[1,0,-2]
[-1]

Input

[1,5,-3]
[-4,2,0]

Your code is saved on this device.Solution