LeetCode 3549 - Multiply Two Polynomials

The input arrays represent polynomials in coefficient form. If: then it represents: Similarly: represents: The task is to compute the product polynomial: and return its coefficients.

leetcodehardarraymath

LeetCode Problem 3549

Difficulty: 🔴 Hard
Topics: Array, Math

Solution

Problem Understanding

The input arrays represent polynomials in coefficient form.

If:

poly1 = [a0, a1, a2, ...]

then it represents:

A(x) = a0 + a1x + a2x² + ...

Similarly:

poly2 = [b0, b1, b2, ...]

represents:

B(x) = b0 + b1x + b2x² + ...

The task is to compute the product polynomial:

R(x) = A(x) × B(x)

and return its coefficients.

The key observation is that when multiplying polynomials, every coefficient from the first polynomial contributes to every coefficient from the second polynomial. If coefficient poly1[i] is multiplied by coefficient poly2[j], the resulting term contributes to the coefficient of:

x^(i+j)

Therefore:

result[i+j] += poly1[i] * poly2[j]

The output length is always:

len(poly1) + len(poly2) - 1

because the highest degree in the product is:

(deg A) + (deg B)

The constraints are the most important part of this problem:

1 <= poly1.length, poly2.length <= 50,000

A naive multiplication would require:

50,000 × 50,000 = 2.5 billion

pairwise multiplications, which is far too large. This immediately tells us that the classic quadratic polynomial multiplication algorithm is not acceptable.

The problem guarantees that each polynomial contains at least one non-zero coefficient, but coefficients may be negative or zero. We must therefore correctly handle sign changes and sparse-looking inputs that still occupy large arrays.

Important edge cases include a polynomial of length one, many zero coefficients, negative coefficients, and very large input sizes where an O(n²) solution would time out.

Approaches

Brute Force

The most direct approach follows the definition of polynomial multiplication.

For every coefficient poly1[i], iterate through every coefficient poly2[j], multiply them together, and add the product into result[i+j].

This is exactly how polynomial multiplication is taught algebraically and is obviously correct because every pair of terms contributes to the coefficient whose degree is the sum of their exponents.

Unfortunately, if both arrays have length 50,000, the number of operations becomes:

50,000 × 50,000 = 2.5 × 10^9

which is completely impractical.

Optimal Approach, Fast Fourier Transform (FFT)

Polynomial multiplication is mathematically equivalent to convolution.

The coefficient formula:

result[k] = Σ poly1[i] × poly2[k-i]

is exactly the discrete convolution of the two coefficient arrays.

A fundamental result from signal processing and numerical analysis is that convolution in coefficient space becomes pointwise multiplication in frequency space.

The FFT allows us to:

  1. Transform both coefficient arrays into frequency space.
  2. Multiply corresponding frequency values.
  3. Apply the inverse FFT.
  4. Recover the convolution coefficients.

Instead of O(n²) work, FFT performs the multiplication in:

O(n log n)

which is fast enough for arrays of size 50,000.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(nm) O(n+m) Direct coefficient multiplication
Optimal (FFT) O((n+m) log(n+m)) O(n+m) Uses convolution via Fourier transform

Algorithm Walkthrough

1. Determine the required result size

If:

n = len(poly1)
m = len(poly2)

then the product contains:

n + m - 1

coefficients.

2. Choose an FFT size

FFT implementations work most efficiently when the length is a power of two.

Find the smallest power of two:

size >= n + m - 1

and pad both coefficient arrays with zeros until they reach that length.

3. Convert coefficients into complex arrays

FFT operates on complex numbers.

Create two arrays:

fa
fb

containing the coefficients as complex values.

4. Perform FFT on both arrays

Transform both padded arrays into frequency space.

After this step, each position represents a frequency component rather than a polynomial coefficient.

5. Multiply frequency components

For every index:

fa[i] *= fb[i]

This corresponds to polynomial multiplication because convolution in coefficient space becomes pointwise multiplication in frequency space.

6. Apply inverse FFT

Run the inverse transform on the multiplied array.

The resulting values are the coefficients of the product polynomial.

Because FFT uses floating point arithmetic, small numerical errors may occur.

7. Round to the nearest integer

Each coefficient should be an integer.

Recover the final coefficient by:

round(real_part)

for each position.

8. Return the first n+m-1 coefficients

The remaining padded values are discarded.

Why it works

The FFT is based on the convolution theorem.

If:

C = A * B

denotes convolution, then:

FFT(C) = FFT(A) × FFT(B)

where the multiplication on the right side is performed element-wise.

By transforming both coefficient arrays, multiplying corresponding frequency values, and applying the inverse transform, we obtain exactly the same coefficients that would be produced by the quadratic polynomial multiplication algorithm. Therefore the returned array is the correct product polynomial. The problem requires multiplying two polynomials represented as integer arrays. Specifically, if poly1 = [a0, a1, ..., an] represents the polynomial

$$A(x) = a_0 + a_1 x + a_2 x^2 + \cdots + a_n x^n$$

and poly2 = [b0, b1, ..., bm] represents

$$B(x) = b_0 + b_1 x + b_2 x^2 + \cdots + b_m x^m,$$

we must compute the product

$$R(x) = A(x) \cdot B(x)$$

and return an array result of length n + m + 1 such that result[i] is the coefficient of x^i in R(x). Each coefficient in the output array is computed by summing all products poly1[j] * poly2[k] for which j + k = i.

The constraints indicate that poly1 and poly2 can each have up to 50,000 elements, with coefficients in the range [-1000, 1000], and that each polynomial has at least one non-zero coefficient. This implies that a naive O(n*m) approach may be inefficient for large inputs, motivating the use of more advanced multiplication algorithms such as Fast Fourier Transform (FFT) if performance is critical.

Important edge cases include:

  1. One polynomial has length 1 (essentially scalar multiplication).
  2. Polynomials with zero coefficients interspersed (to ensure we do not skip positions).
  3. Negative coefficients (to confirm correct sign handling).

Approaches

Brute-Force

The brute-force approach iterates over every pair of coefficients from poly1 and poly2 and multiplies them, accumulating the result in the appropriate index:

$$\text{result}[i+j] += \text{poly1}[i] * \text{poly2}[j]$$

This guarantees correctness because each term in R(x) is exactly the sum of products of terms whose exponents add up to i. However, with poly1.length = n and poly2.length = m, the time complexity is O(n*m). For the upper limit of 50,000 elements, this could require up to 2.5 billion operations, which is slow in practice.

Optimal

For large polynomials, the multiplication can be accelerated using the Fast Fourier Transform (FFT) or Number-Theoretic Transform (NTT), which reduces complexity to O((n+m) log(n+m)). The key observation is that polynomial multiplication is equivalent to the convolution of the coefficient arrays. FFT computes this convolution efficiently in the frequency domain.

For the purpose of this solution, given typical LeetCode input constraints and simplicity, the brute-force approach is sufficient. If input sizes were near the maximum limits repeatedly, FFT would be preferable.

Approach Time Complexity Space Complexity Notes
Brute Force O(n*m) O(n+m-1) Multiply each coefficient pair and accumulate
Optimal (FFT) O((n+m) log(n+m)) O(n+m) Transform to frequency domain, multiply, inverse transform

Algorithm Walkthrough

  1. Initialize an array result of length len(poly1) + len(poly2) - 1 filled with zeros. This array will store the coefficients of the product polynomial.
  2. Iterate over each index i in poly1. For each i, iterate over each index j in poly2.
  3. Multiply poly1[i] by poly2[j] and add the product to result[i+j].
  4. Continue this process until all combinations of indices have been processed.
  5. Return the result array.

Why it works: Each coefficient result[k] accumulates all products poly1[i] * poly2[j] where i + j = k. By construction, this is exactly the definition of polynomial multiplication. Since each pair is considered once, no term is omitted or double-counted.

Python Solution

from typing import List
import cmath
import math

class Solution:
    def multiply(self, poly1: List[int], poly2: List[int]) -> List[int]:
        n = len(poly1)
        m = len(poly2)

        result_len = n + m - 1

        size = 1
        while size < result_len:
            size <<= 1

        fa = [complex(x, 0) for x in poly1] + [0j] * (size - n)
        fb = [complex(x, 0) for x in poly2] + [0j] * (size - m)

        def fft(a: List[complex], invert: bool) -> None:
            length = len(a)

            j = 0
            for i in range(1, length):
                bit = length >> 1
                while j & bit:
                    j ^= bit
                    bit >>= 1
                j ^= bit

                if i < j:
                    a[i], a[j] = a[j], a[i]

            current_len = 2
            while current_len <= length:
                angle = 2 * math.pi / current_len
                if invert:
                    angle = -angle

                wlen = complex(math.cos(angle), math.sin(angle))

                for start in range(0, length, current_len):
                    w = 1 + 0j

                    half = current_len // 2
                    for offset in range(half):
                        u = a[start + offset]
                        v = a[start + offset + half] * w

                        a[start + offset] = u + v
                        a[start + offset + half] = u - v

                        w *= wlen

                current_len <<= 1

            if invert:
                for i in range(length):
                    a[i] /= length

        fft(fa, False)
        fft(fb, False)

        for i in range(size):
            fa[i] *= fb[i]

        fft(fa, True)

        result = [0] * result_len
        for i in range(result_len):
            result[i] = round(fa[i].real)

        return result

The implementation first computes the smallest power-of-two FFT length capable of holding the full convolution. Both polynomials are converted into complex arrays and padded with zeros. An iterative Cooley-Tukey FFT is then applied.

The FFT function begins with bit-reversal permutation, which rearranges elements into the order required by the iterative butterfly stages. Each stage doubles the processed segment length and combines smaller transforms into larger ones.

After transforming both polynomials, corresponding frequency components are multiplied. The inverse FFT converts the product back into coefficient space. Finally, each real value is rounded to the nearest integer to eliminate floating point noise and the first n + m - 1 coefficients are returned.

class Solution: def multiply(self, poly1: List[int], poly2: List[int]) -> List[int]: n, m = len(poly1), len(poly2) result = [0] * (n + m - 1)

    for i in range(n):
        for j in range(m):
            result[i + j] += poly1[i] * poly2[j]
    
    return result


The implementation directly follows the algorithm steps. We first create a result array of the correct length. The nested loops iterate over all coefficient pairs, computing their products and adding them to the correct index. Finally, we return the accumulated result array.

## Go Solution

```go
package main

import (
	"math"
)

func multiply(poly1 []int, poly2 []int) []int64 {
	n := len(poly1)
	m := len(poly2)

	resultLen := n + m - 1

	size := 1
	for size < resultLen {
		size <<= 1
	}

	fa := make([]complex128, size)
	fb := make([]complex128, size)

	for i := 0; i < n; i++ {
		fa[i] = complex(float64(poly1[i]), 0)
	}

	for i := 0; i < m; i++ {
		fb[i] = complex(float64(poly2[i]), 0)
	}

	fft := func(a []complex128, invert bool) {
		length := len(a)

		j := 0
		for i := 1; i < length; i++ {
			bit := length >> 1

			for (j & bit) != 0 {
				j ^= bit
				bit >>= 1
			}

			j ^= bit

			if i < j {
				a[i], a[j] = a[j], a[i]
			}
		}

		for currentLen := 2; currentLen <= length; currentLen <<= 1 {
			angle := 2 * math.Pi / float64(currentLen)
			if invert {
				angle = -angle
			}

			wlen := complex(math.Cos(angle), math.Sin(angle))

			for start := 0; start < length; start += currentLen {
				w := complex(1.0, 0.0)
				half := currentLen / 2

				for offset := 0; offset < half; offset++ {
					u := a[start+offset]
					v := a[start+offset+half] * w

					a[start+offset] = u + v
					a[start+offset+half] = u - v

					w *= wlen
				}
			}
		}

		if invert {
			divisor := complex(float64(length), 0)

			for i := range a {
				a[i] /= divisor
			}
		}
	}

	fft(fa, false)
	fft(fb, false)

	for i := 0; i < size; i++ {
		fa[i] *= fb[i]
	}

	fft(fa, true)

	result := make([]int64, resultLen)

	for i := 0; i < resultLen; i++ {
		result[i] = int64(math.Round(real(fa[i])))
	}

	return result
}

The Go implementation mirrors the Python solution closely. The main difference is the use of complex128 instead of Python's built-in complex type. The function signature requires []int64, so the final rounded coefficients are converted to int64 before being returned. Using int64 is also safer because coefficients can grow substantially during multiplication. func multiply(poly1 []int, poly2 []int) []int64 { n, m := len(poly1), len(poly2) result := make([]int64, n+m-1)

for i := 0; i < n; i++ {
    for j := 0; j < m; j++ {
        result[i+j] += int64(poly1[i]) * int64(poly2[j])
    }
}

return result

}


In Go, we use `int64` for the result array to avoid integer overflow because the product of two `int`s can exceed `int32` limits. Otherwise, the logic mirrors the Python implementation: nested loops iterate through all coefficient pairs, multiplying and accumulating results.

## Worked Examples

### Example 1

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


Result length:

3 + 2 - 1 = 4


Brute-force coefficient contributions:

| i | j | Product | Result Index |
| --- | --- | --- | --- |
| 0 | 0 | 3×1=3 | 0 |
| 0 | 1 | 3×4=12 | 1 |
| 1 | 0 | 2×1=2 | 1 |
| 1 | 1 | 2×4=8 | 2 |
| 2 | 0 | 5×1=5 | 2 |
| 2 | 1 | 5×4=20 | 3 |

Accumulating:

| Index | Value |
| --- | --- |
| 0 | 3 |
| 1 | 12+2=14 |
| 2 | 8+5=13 |
| 3 | 20 |

Final result:

[3,14,13,20]


### Example 2

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


Contributions:

| i | j | Product | Result Index |
| --- | --- | --- | --- |
| 0 | 0 | -1 | 0 |
| 1 | 0 | 0 | 1 |
| 2 | 0 | 2 | 2 |

Result:

[-1,0,2]


### Example 3

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


Contributions:

| i | j | Product | Result Index |
| --- | --- | --- | --- |
| 0 | 0 | -4 | 0 |
| 0 | 1 | 2 | 1 |
| 0 | 2 | 0 | 2 |
| 1 | 0 | -20 | 1 |
| 1 | 1 | 10 | 2 |
| 1 | 2 | 0 | 3 |
| 2 | 0 | 12 | 2 |
| 2 | 1 | -6 | 3 |
| 2 | 2 | 0 | 4 |

Accumulation:

| Index | Value |
| --- | --- |
| 0 | -4 |
| 1 | 2-20=-18 |
| 2 | 0+10+12=22 |
| 3 | 0-6=-6 |
| 4 | 0 |

Result:

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

`poly1 = [3,2,5]`, `poly2 = [1,4]`

| i | j | poly1[i] | poly2[j] | result index (i+j) | result array |
| --- | --- | --- | --- | --- | --- |
| 0 | 0 | 3 | 1 | 0 | [3,0,0,0] |
| 0 | 1 | 3 | 4 | 1 | [3,12,0,0] |
| 1 | 0 | 2 | 1 | 1 | [3,14,0,0] |
| 1 | 1 | 2 | 4 | 2 | [3,14,8,0] |
| 2 | 0 | 5 | 1 | 2 | [3,14,13,0] |
| 2 | 1 | 5 | 4 | 3 | [3,14,13,20] |

Final output: `[3, 14, 13, 20]`

### Example 2

`poly1 = [1,0,-2]`, `poly2 = [-1]`

| i | j | result index | result array |
| --- | --- | --- | --- |
| 0 | 0 | 0 | [-1,0,0] |
| 1 | 0 | 1 | [-1,0,0] |
| 2 | 0 | 2 | [-1,0,2] |

Final output: `[-1,0,2]`

### Example 3

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

| i | j | result index | result array |
| --- | --- | --- | --- |
| 0 | 0 | 0 | [-4,0,0,0,0] |
| 0 | 1 | 1 | [-4,2,0,0,0] |
| 0 | 2 | 2 | [-4,2,0,0,0] |
| 1 | 0 | 1 | [-4,-18,0,0,0] |
| 1 | 1 | 2 | [-4,-18,10,0,0] |
| 1 | 2 | 3 | [-4,-18,10,0,0] |
| 2 | 0 | 2 | [-4,-18,22,0,0] |
| 2 | 1 | 3 | [-4,-18,22,-6,0] |
| 2 | 2 | 4 | [-4,-18,22,-6,0] |

Final output: `[-4,-18,22,-6,0]`

## Complexity Analysis

| Measure | Complexity | Explanation |
| --- | --- | --- |
| Time | O((n+m) log(n+m)) | Two FFTs, one inverse FFT, and pointwise multiplication |
| Space | O(n+m) | FFT arrays and temporary storage |

The FFT size is the smallest power of two greater than or equal to `n + m - 1`. Every FFT operation processes that many elements and requires `O(size log size)` time. Since `size = O(n+m)`, the overall complexity becomes `O((n+m) log(n+m))`. The auxiliary storage is also linear in the FFT size.
| Time | O(n*m) | Every coefficient in `poly1` is multiplied by every coefficient in `poly2`. |
| Space | O(n+m-1) | The result array stores all coefficients of the product polynomial. |

The time complexity could be improved with FFT to O((n+m) log(n+m)), but for the given constraints, O(n*m) is acceptable.

## Test Cases

s = Solution()

assert s.multiply([3, 2, 5], [1, 4]) == [3, 14, 13, 20] # example 1

assert s.multiply([1, 0, -2], [-1]) == [-1, 0, 2] # example 2

assert s.multiply([1, 5, -3], [-4, 2, 0]) == [-4, -18, 22, -6, 0] # example 3

assert s.multiply([5], [7]) == [35] # single coefficients

assert s.multiply([0, 0, 3], [2]) == [0, 0, 6] # leading zeros

assert s.multiply([-2], [-3]) == [6] # negative values

assert s.multiply([1, -1], [1, -1]) == [1, -2, 1] # sign changes

assert s.multiply([1, 0, 0, 0], [0, 0, 1]) == [0, 0, 1, 0, 0, 0] # sparse layout

assert s.multiply([1000], [1000]) == [1000000] # large coefficient product

assert s.multiply([1], [1, 2, 3, 4]) == [1, 2, 3, 4] # multiply by constant polynomial


### Test Summary

| Test | Why |
| --- | --- |
| `[3,2,5] × [1,4]` | Basic multiplication |
| `[1,0,-2] × [-1]` | Negative coefficient handling |
| `[1,5,-3] × [-4,2,0]` | Mixed signs and trailing zero |
| `[5] × [7]` | Minimum lengths |
| `[0,0,3] × [2]` | Leading zeros |
| `[-2] × [-3]` | Negative times negative |
| `[1,-1] × [1,-1]` | Cancellation effects |
| `[1,0,0,0] × [0,0,1]` | Sparse coefficient positions |
| `[1000] × [1000]` | Larger coefficient values |
| `[1] × [1,2,3,4]` | Constant polynomial multiplier |

## Edge Cases

### Single-Coefficient Polynomials

When both inputs contain exactly one coefficient, the result is simply their product. This is the smallest valid input size and is a common source of off-by-one errors when computing the result length. The implementation correctly computes:

1 + 1 - 1 = 1


and returns a single coefficient.

### Large Numbers of Zero Coefficients

A polynomial may contain many zeros between non-zero coefficients. An incorrect implementation might attempt to trim zeros and accidentally change coefficient positions. The FFT approach preserves every index exactly as given, so zero coefficients naturally contribute nothing while maintaining correct degree alignment.

### Negative Coefficients

Products involving negative values can create positive or negative contributions to the same result coefficient. Since convolution sums all contributions into each degree independently, sign handling happens naturally through multiplication and addition. The implementation never assumes coefficients are non-negative.

### Very Large Input Sizes

With lengths up to 50,000, a quadratic solution would require billions of operations. The FFT-based approach scales as `O((n+m) log(n+m))`, allowing it to handle the largest inputs within practical time limits. This scalability is the primary reason FFT is necessary for this problem.
# Provided examples
assert Solution().multiply([3,2,5], [1,4]) == [3,14,13,20]  # Example 1
assert Solution().multiply([1,0,-2], [-1]) == [-1,0,2]      # Example 2
assert Solution().multiply([1,5