3549. Multiply Two Polynomials 🔒

Problem Description

You are given two integer arrays poly1 and poly2 that represent polynomials. Each element at index i in these arrays represents the coefficient of x^i in the polynomial.

For example:

If poly1 = [2, 0, 3, 1], this represents the polynomial A(x) = 2 + 0*x + 3*x^2 + 1*x^3 = 2 + 3x^2 + x^3
If poly2 = [1, 2], this represents the polynomial B(x) = 1 + 2*x

Your task is to multiply these two polynomials and return the coefficients of the resulting polynomial as an array.

The multiplication of polynomials follows the standard algebraic rules where you multiply each term in the first polynomial by each term in the second polynomial and combine like terms.

For the example above:

A(x) * B(x) = (2 + 3x^2 + x^3) * (1 + 2x)
= 2*1 + 2*2x + 3x^2*1 + 3x^2*2x + x^3*1 + x^3*2x
= 2 + 4x + 3x^2 + 6x^3 + x^3 + 2x^4
= 2 + 4x + 3x^2 + 7x^3 + 2x^4

The output array should have length (poly1.length + poly2.length - 1), where each element result[i] represents the coefficient of x^i in the product polynomial.

In the example, the result would be [2, 4, 3, 7, 2].

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

When multiplying two polynomials, the naive approach would be to multiply each term in the first polynomial with each term in the second polynomial. This would give us O(n*m) time complexity where n and m are the lengths of the two polynomials.

However, there's a clever mathematical insight: polynomial multiplication is essentially a convolution operation. When we multiply A(x) * B(x), the coefficient of x^k in the result is the sum of all products a[i] * b[j] where i + j = k.

This convolution operation can be dramatically accelerated using the Fast Fourier Transform (FFT). The key insight comes from the Convolution Theorem, which states that convolution in the time domain equals pointwise multiplication in the frequency domain.

Here's the brilliant idea:

Instead of doing the expensive convolution directly, we transform both polynomials to the frequency domain using FFT
In the frequency domain, convolution becomes simple pointwise multiplication - we just multiply corresponding elements
We then transform back to get our result

Think of it like this: imagine you need to mix two complicated wave patterns. Instead of calculating every interaction point by point, you decompose each wave into its frequency components (like breaking music into individual notes), multiply the corresponding frequencies (which is much simpler), and then reconstruct the final wave.

The FFT can perform this transformation in O(n log n) time, making the entire multiplication process much faster than the naive O(n^2) approach. We pad the arrays to the nearest power of 2 because FFT works most efficiently with powers of 2, allowing the divide-and-conquer algorithm to split evenly at each step.

The use of complex numbers in the implementation is because FFT naturally works with complex exponentials (e^(iθ)), which provide the periodic basis functions needed for the frequency decomposition.

Learn more about Math patterns.

Solution Approach

The implementation uses Fast Fourier Transform (FFT) to efficiently compute polynomial multiplication. Let's walk through the key steps:

1. Padding the Length

First, we calculate the result length as m = len(poly1) + len(poly2) - 1. This is because when multiplying a polynomial of degree n-1 with a polynomial of degree m-1, the result has degree (n-1) + (m-1) = n+m-2, requiring n+m-1 coefficients.

We then round m up to the nearest power of 2 (stored in n) using bit shifting:

n = 1
while n < m:
    n <<= 1

This ensures FFT can use efficient divide-and-conquer splitting.

2. Convert to Complex and Pad

The polynomials are converted to complex numbers and padded with zeros:

fa = list(map(complex, poly1)) + [0j] * (n - len(poly1))
fb = list(map(complex, poly2)) + [0j] * (n - len(poly2))

Complex numbers are used because FFT relies on complex exponentials for frequency decomposition.

3. Forward FFT Transformation

Both polynomial coefficient arrays undergo forward FFT:

self._fft(fa, invert=False)
self._fft(fb, invert=False)

The FFT implementation uses the iterative Cooley-Tukey algorithm:

Bit-reversal permutation: First, the array elements are reordered using bit-reversal of indices. This prepares the data for the bottom-up approach.
Butterfly operations: The algorithm then performs butterfly operations in increasing sizes (2, 4, 8, ..., n). Each butterfly combines pairs of elements using complex roots of unity w = e^(2πi/len).

4. Pointwise Multiplication in Frequency Domain

After transformation, we multiply corresponding elements:

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

This simple operation in the frequency domain corresponds to convolution in the time domain.

5. Inverse FFT

The product is transformed back to coefficient form:

self._fft(fa, invert=True)

The inverse FFT uses the same algorithm but with conjugate roots of unity (negative angle) and divides by n at the end to normalize.

6. Extract Result

Finally, we extract the first m coefficients and round to integers:

return [int(round(fa[i].real)) for i in range(m)]

The imaginary parts should be negligible (close to zero) due to numerical precision, so we take only the real parts.

The overall time complexity is O(n log n) where n is the padded size, making this approach much more efficient than the naive O(n²) multiplication for large polynomials.

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a small example with poly1 = [1, 2] and poly2 = [3, 4].

These represent:

A(x) = 1 + 2x
B(x) = 3 + 4x

Step 1: Calculate result length and padding

Result length m = 2 + 2 - 1 = 3
Round up to nearest power of 2: n = 4

Step 2: Convert to complex and pad with zeros

fa = [1+0j, 2+0j, 0+0j, 0+0j]
fb = [3+0j, 4+0j, 0+0j, 0+0j]

Step 3: Apply FFT to both arrays

For fa, the FFT transforms it to frequency domain:

After bit-reversal: [1+0j, 0+0j, 2+0j, 0+0j]
After butterfly operations: [3+0j, 1-2j, -1+0j, 1+2j]

For fb, similarly:

After bit-reversal: [3+0j, 0+0j, 4+0j, 0+0j]
After butterfly operations: [7+0j, 3-4j, -1+0j, 3+4j]

Step 4: Pointwise multiplication in frequency domain Multiply corresponding elements:

fa[0] = (3+0j) * (7+0j) = 21+0j
fa[1] = (1-2j) * (3-4j) = (3-8) + (-4-6)j = -5-10j
fa[2] = (-1+0j) * (-1+0j) = 1+0j
fa[3] = (1+2j) * (3+4j) = (3-8) + (4+6)j = -5+10j

Result: fa = [21+0j, -5-10j, 1+0j, -5+10j]

Step 5: Inverse FFT Transform back to coefficient form:

Apply inverse FFT with conjugate roots
After butterfly operations and normalization by dividing by 4:
fa = [3+0j, 10+0j, 8+0j, 0+0j]

Step 6: Extract result Take the first 3 coefficients (since m = 3):

Result: [3, 10, 8]

Verification: (1 + 2x) * (3 + 4x) = 3 + 4x + 6x + 8x² = 3 + 10x + 8x²

The coefficients [3, 10, 8] match our expected result!

Solution Implementation

1class Solution:
2    def multiply(self, poly1: List[int], poly2: List[int]) -> List[int]:
3        """
4        Multiply two polynomials using Fast Fourier Transform (FFT).
5      
6        Args:
7            poly1: Coefficients of first polynomial (lowest degree first)
8            poly2: Coefficients of second polynomial (lowest degree first)
9      
10        Returns:
11            Coefficients of the product polynomial
12        """
13        # Handle empty polynomials
14        if not poly1 or not poly2:
15            return []
16      
17        # Calculate result size (degree of product + 1)
18        result_size = len(poly1) + len(poly2) - 1
19      
20        # Find next power of 2 for FFT size
21        fft_size = 1
22        while fft_size < result_size:
23            fft_size <<= 1
24      
25        # Convert polynomials to complex numbers and pad with zeros
26        complex_poly1 = [complex(coeff) for coeff in poly1] + [0j] * (fft_size - len(poly1))
27        complex_poly2 = [complex(coeff) for coeff in poly2] + [0j] * (fft_size - len(poly2))
28      
29        # Apply FFT to both polynomials
30        self._fft(complex_poly1, invert=False)
31        self._fft(complex_poly2, invert=False)
32      
33        # Pointwise multiplication in frequency domain
34        for i in range(fft_size):
35            complex_poly1[i] *= complex_poly2[i]
36      
37        # Apply inverse FFT to get the result
38        self._fft(complex_poly1, invert=True)
39      
40        # Extract real parts and round to nearest integer
41        return [int(round(complex_poly1[i].real)) for i in range(result_size)]
42  
43    def _fft(self, coefficients: List[complex], invert: bool) -> None:
44        """
45        Perform in-place FFT or inverse FFT using Cooley-Tukey algorithm.
46      
47        Args:
48            coefficients: Complex coefficients to transform (modified in-place)
49            invert: If True, performs inverse FFT; if False, performs forward FFT
50        """
51        n = len(coefficients)
52      
53        # Bit-reversal permutation for in-place computation
54        j = 0
55        for i in range(1, n):
56            bit = n >> 1
57            # Update bit-reversed index
58            while j & bit:
59                j ^= bit
60                bit >>= 1
61            j ^= bit
62            # Swap elements if needed
63            if i < j:
64                coefficients[i], coefficients[j] = coefficients[j], coefficients[i]
65      
66        # Cooley-Tukey FFT main loop
67        current_length = 2
68        while current_length <= n:
69            # Calculate angle for current stage
70            angle = 2 * math.pi / current_length * (-1 if invert else 1)
71            # Root of unity for current stage
72            w_n = complex(math.cos(angle), math.sin(angle))
73          
74            # Process all groups of current length
75            for start in range(0, n, current_length):
76                w = complex(1, 0)  # Initialize twiddle factor
77                half_length = start + current_length // 2
78              
79                # Butterfly operations within each group
80                for k in range(start, half_length):
81                    # Butterfly computation
82                    even_part = coefficients[k]
83                    odd_part = coefficients[k + current_length // 2] * w
84                    coefficients[k] = even_part + odd_part
85                    coefficients[k + current_length // 2] = even_part - odd_part
86                    # Update twiddle factor
87                    w *= w_n
88          
89            # Double the length for next stage
90            current_length <<= 1
91      
92        # Normalize for inverse FFT
93        if invert:
94            for i in range(n):
95                coefficients[i] /= n
96

1class Solution {
2    /**
3     * Multiplies two polynomials using Fast Fourier Transform (FFT)
4     * @param poly1 First polynomial coefficients (from lowest to highest degree)
5     * @param poly2 Second polynomial coefficients (from lowest to highest degree)
6     * @return Resulting polynomial coefficients after multiplication
7     */
8    public long[] multiply(int[] poly1, int[] poly2) {
9        // Handle null or empty inputs
10        if (poly1 == null || poly2 == null || poly1.length == 0 || poly2.length == 0) {
11            return new long[0];
12        }
13
14        // Calculate the size of the result polynomial
15        // When multiplying polynomials of degree n and m, result has degree n+m
16        int resultSize = poly1.length + poly2.length - 1;
17      
18        // Find the next power of 2 greater than or equal to resultSize
19        // FFT requires the array size to be a power of 2
20        int fftSize = 1;
21        while (fftSize < resultSize) {
22            fftSize <<= 1;
23        }
24
25        // Create complex arrays for FFT, padding with zeros as needed
26        Complex[] complexPoly1 = new Complex[fftSize];
27        Complex[] complexPoly2 = new Complex[fftSize];
28      
29        // Initialize complex arrays with polynomial coefficients
30        for (int i = 0; i < fftSize; i++) {
31            complexPoly1[i] = new Complex(i < poly1.length ? poly1[i] : 0, 0);
32            complexPoly2[i] = new Complex(i < poly2.length ? poly2[i] : 0, 0);
33        }
34
35        // Apply FFT to transform polynomials to frequency domain
36        fft(complexPoly1, false);
37        fft(complexPoly2, false);
38
39        // Multiply the polynomials element-wise in frequency domain
40        for (int i = 0; i < fftSize; i++) {
41            complexPoly1[i] = complexPoly1[i].mul(complexPoly2[i]);
42        }
43
44        // Apply inverse FFT to transform back to coefficient representation
45        fft(complexPoly1, true);
46
47        // Extract real parts and round to get integer coefficients
48        long[] result = new long[resultSize];
49        for (int i = 0; i < resultSize; i++) {
50            result[i] = Math.round(complexPoly1[i].re);
51        }
52      
53        return result;
54    }
55
56    /**
57     * Performs Fast Fourier Transform or its inverse on the given array
58     * @param array Array of complex numbers to transform in-place
59     * @param invert If true, performs inverse FFT; otherwise, performs forward FFT
60     */
61    private static void fft(Complex[] array, boolean invert) {
62        int n = array.length;
63
64        // Bit-reversal permutation
65        // Rearranges elements according to bit-reversed indices
66        for (int i = 1, j = 0; i < n; i++) {
67            int bit = n >>> 1;
68          
69            // Calculate bit-reversed index
70            while ((j & bit) != 0) {
71                j ^= bit;
72                bit >>>= 1;
73            }
74            j ^= bit;
75          
76            // Swap elements if needed
77            if (i < j) {
78                Complex temp = array[i];
79                array[i] = array[j];
80                array[j] = temp;
81            }
82        }
83
84        // Cooley-Tukey FFT algorithm
85        // Iteratively combines smaller DFTs into larger ones
86        for (int length = 2; length <= n; length <<= 1) {
87            // Calculate the angle for the primitive root of unity
88            double angle = 2 * Math.PI / length * (invert ? -1 : 1);
89            Complex primitiveRoot = new Complex(Math.cos(angle), Math.sin(angle));
90
91            // Process each segment of size 'length'
92            for (int startIndex = 0; startIndex < n; startIndex += length) {
93                Complex omega = new Complex(1, 0);
94                int halfLength = length >>> 1;
95              
96                // Butterfly operations within the segment
97                for (int j = 0; j < halfLength; j++) {
98                    // Get the two elements to combine
99                    Complex u = array[startIndex + j];
100                    Complex v = array[startIndex + j + halfLength].mul(omega);
101                  
102                    // Combine using butterfly operation
103                    array[startIndex + j] = u.add(v);
104                    array[startIndex + j + halfLength] = u.sub(v);
105                  
106                    // Update the twiddle factor
107                    omega = omega.mul(primitiveRoot);
108                }
109            }
110        }
111
112        // Normalize the result for inverse FFT
113        if (invert) {
114            for (int i = 0; i < n; i++) {
115                array[i].re /= n;
116                array[i].im /= n;
117            }
118        }
119    }
120
121    /**
122     * Complex number class for FFT operations
123     */
124    private static final class Complex {
125        double re;  // Real part
126        double im;  // Imaginary part
127      
128        /**
129         * Creates a complex number with given real and imaginary parts
130         */
131        Complex(double re, double im) {
132            this.re = re;
133            this.im = im;
134        }
135      
136        /**
137         * Adds this complex number to another
138         * @param other The complex number to add
139         * @return Sum of the two complex numbers
140         */
141        Complex add(Complex other) {
142            return new Complex(re + other.re, im + other.im);
143        }
144      
145        /**
146         * Subtracts another complex number from this one
147         * @param other The complex number to subtract
148         * @return Difference of the two complex numbers
149         */
150        Complex sub(Complex other) {
151            return new Complex(re - other.re, im - other.im);
152        }
153      
154        /**
155         * Multiplies this complex number by another
156         * Formula: (a + bi) * (c + di) = (ac - bd) + (ad + bc)i
157         * @param other The complex number to multiply with
158         * @return Product of the two complex numbers
159         */
160        Complex mul(Complex other) {
161            return new Complex(
162                re * other.re - im * other.im,
163                re * other.im + im * other.re
164            );
165        }
166    }
167}
168

1class Solution {
2    using cd = complex<double>;
3
4    /**
5     * Performs Fast Fourier Transform (FFT) or its inverse on a complex vector
6     * @param a - input/output vector of complex numbers to transform
7     * @param invert - if true, performs inverse FFT; if false, performs forward FFT
8     */
9    void fft(vector<cd>& a, bool invert) {
10        int n = a.size();
11      
12        // Bit-reversal permutation to rearrange elements for in-place FFT
13        for (int i = 1, j = 0; i < n; ++i) {
14            int bit = n >> 1;
15            // Update j to its bit-reversed position
16            for (; j & bit; bit >>= 1) {
17                j ^= bit;
18            }
19            j ^= bit;
20          
21            // Swap elements at positions i and j if needed
22            if (i < j) {
23                swap(a[i], a[j]);
24            }
25        }
26      
27        // Cooley-Tukey FFT algorithm - iterative implementation
28        for (int len = 2; len <= n; len <<= 1) {
29            // Calculate the angle for the primitive root of unity
30            double angle = 2 * M_PI / len * (invert ? -1 : 1);
31            cd wlen(cos(angle), sin(angle));  // Primitive len-th root of unity
32          
33            // Process each block of size 'len'
34            for (int i = 0; i < n; i += len) {
35                cd w(1, 0);  // Initialize to 1 (identity element)
36                int halfLen = len >> 1;
37              
38                // Butterfly operations within each block
39                for (int j = 0; j < halfLen; ++j) {
40                    cd u = a[i + j];                  // First half element
41                    cd v = a[i + j + halfLen] * w;    // Second half element with twiddle factor
42                  
43                    a[i + j] = u + v;                 // Upper branch of butterfly
44                    a[i + j + halfLen] = u - v;       // Lower branch of butterfly
45                  
46                    w *= wlen;  // Update twiddle factor for next iteration
47                }
48            }
49        }
50      
51        // Normalize the result for inverse FFT
52        if (invert) {
53            for (cd& x : a) {
54                x /= n;
55            }
56        }
57    }
58
59public:
60    /**
61     * Multiplies two polynomials using FFT-based convolution
62     * @param poly1 - coefficients of the first polynomial (lowest degree first)
63     * @param poly2 - coefficients of the second polynomial (lowest degree first)
64     * @return coefficients of the product polynomial
65     */
66    vector<long long> multiply(vector<int>& poly1, vector<int>& poly2) {
67        // Handle edge case of empty polynomials
68        if (poly1.empty() || poly2.empty()) {
69            return {};
70        }
71      
72        // Calculate the size of the result polynomial
73        int resultSize = poly1.size() + poly2.size() - 1;
74      
75        // Find the next power of 2 for FFT size requirement
76        int fftSize = 1;
77        while (fftSize < resultSize) {
78            fftSize <<= 1;
79        }
80
81        // Initialize complex vectors for FFT with proper padding
82        vector<cd> complexPoly1(fftSize), complexPoly2(fftSize);
83      
84        // Copy polynomial coefficients to complex vectors, pad with zeros
85        for (int i = 0; i < fftSize; ++i) {
86            complexPoly1[i] = i < poly1.size() ? cd(poly1[i], 0) : cd(0, 0);
87            complexPoly2[i] = i < poly2.size() ? cd(poly2[i], 0) : cd(0, 0);
88        }
89
90        // Transform both polynomials to frequency domain
91        fft(complexPoly1, false);
92        fft(complexPoly2, false);
93      
94        // Perform pointwise multiplication in frequency domain
95        for (int i = 0; i < fftSize; ++i) {
96            complexPoly1[i] *= complexPoly2[i];
97        }
98      
99        // Transform back to time domain (coefficient representation)
100        fft(complexPoly1, true);
101
102        // Extract real parts and round to nearest integer for the result
103        vector<long long> result(resultSize);
104        for (int i = 0; i < resultSize; ++i) {
105            result[i] = llround(complexPoly1[i].real());
106        }
107      
108        return result;
109    }
110};
111

1/**
2 * Multiplies two polynomials represented as coefficient arrays
3 * Uses FFT (Fast Fourier Transform) for efficient multiplication of large polynomials
4 * @param poly1 - First polynomial coefficients array
5 * @param poly2 - Second polynomial coefficients array
6 * @returns Product polynomial coefficients array
7 */
8export function multiply(poly1: number[], poly2: number[]): number[] {
9    const poly1Length = poly1.length;
10    const poly2Length = poly2.length;
11  
12    // Handle empty polynomial cases
13    if (!poly1Length || !poly2Length) {
14        return [];
15    }
16
17    // Use naive multiplication for small polynomials (threshold: 64 coefficients)
18    if (Math.min(poly1Length, poly2Length) <= 64) {
19        const resultLength = poly1Length + poly2Length - 1;
20        const result = new Array<number>(resultLength).fill(0);
21      
22        // Perform coefficient-wise multiplication
23        for (let i = 0; i < poly1Length; ++i) {
24            for (let j = 0; j < poly2Length; ++j) {
25                result[i + j] += poly1[i] * poly2[j];
26            }
27        }
28      
29        // Round results to handle floating-point errors
30        return result.map(value => Math.round(value));
31    }
32
33    // Calculate required FFT size (must be power of 2)
34    const resultLength = poly1Length + poly2Length - 1;
35    let fftSize = 1;
36    while (fftSize < resultLength) {
37        fftSize <<= 1;
38    }
39
40    // Initialize complex number arrays for first polynomial
41    const realPartA = new Float64Array(fftSize);
42    const imagPartA = new Float64Array(fftSize);
43    for (let i = 0; i < poly1Length; ++i) {
44        realPartA[i] = poly1[i];
45    }
46
47    // Initialize complex number arrays for second polynomial
48    const realPartB = new Float64Array(fftSize);
49    const imagPartB = new Float64Array(fftSize);
50    for (let i = 0; i < poly2Length; ++i) {
51        realPartB[i] = poly2[i];
52    }
53
54    // Apply FFT to both polynomials
55    fft(realPartA, imagPartA, false);
56    fft(realPartB, imagPartB, false);
57
58    // Perform point-wise multiplication in frequency domain
59    for (let i = 0; i < fftSize; ++i) {
60        const realA = realPartA[i];
61        const imagA = imagPartA[i];
62        const realB = realPartB[i];
63        const imagB = imagPartB[i];
64      
65        // Complex multiplication: (a + bi) * (c + di) = (ac - bd) + (ad + bc)i
66        realPartA[i] = realA * realB - imagA * imagB;
67        imagPartA[i] = realA * imagB + imagA * realB;
68    }
69
70    // Apply inverse FFT to get the result
71    fft(realPartA, imagPartA, true);
72
73    // Extract and round the result coefficients
74    const output = new Array<number>(resultLength);
75    for (let i = 0; i < resultLength; ++i) {
76        output[i] = Math.round(realPartA[i]);
77    }
78  
79    return output;
80}
81
82/**
83 * Performs Fast Fourier Transform (FFT) or its inverse on complex number arrays
84 * Uses the Cooley-Tukey algorithm with bit-reversal permutation
85 * @param realPart - Real parts of complex numbers (modified in-place)
86 * @param imagPart - Imaginary parts of complex numbers (modified in-place)
87 * @param invert - If true, performs inverse FFT; otherwise performs forward FFT
88 */
89function fft(realPart: Float64Array, imagPart: Float64Array, invert: boolean): void {
90    const size = realPart.length;
91
92    // Bit-reversal permutation for in-place FFT
93    for (let i = 1, j = 0; i < size; ++i) {
94        let bit = size >> 1;
95      
96        // Update bit-reversed index
97        for (; j & bit; bit >>= 1) {
98            j ^= bit;
99        }
100        j ^= bit;
101      
102        // Swap elements if needed
103        if (i < j) {
104            [realPart[i], realPart[j]] = [realPart[j], realPart[i]];
105            [imagPart[i], imagPart[j]] = [imagPart[j], imagPart[i]];
106        }
107    }
108
109    // Cooley-Tukey FFT algorithm
110    for (let subproblemSize = 2; subproblemSize <= size; subproblemSize <<= 1) {
111        // Calculate twiddle factor angle
112        const angle = ((2 * Math.PI) / subproblemSize) * (invert ? -1 : 1);
113        const twiddleCos = Math.cos(angle);
114        const twiddleSin = Math.sin(angle);
115
116        // Process each subproblem
117        for (let start = 0; start < size; start += subproblemSize) {
118            let wReal = 1;
119            let wImag = 0;
120            const halfSize = subproblemSize >> 1;
121          
122            // Butterfly operations within subproblem
123            for (let k = 0; k < halfSize; ++k) {
124                // Get butterfly pair indices
125                const topIndex = start + k;
126                const bottomIndex = start + k + halfSize;
127              
128                // Store top butterfly value
129                const topReal = realPart[topIndex];
130                const topImag = imagPart[topIndex];
131              
132                // Get bottom butterfly value
133                const bottomReal = realPart[bottomIndex];
134                const bottomImag = imagPart[bottomIndex];
135              
136                // Apply twiddle factor to bottom value
137                const twiddledReal = bottomReal * wReal - bottomImag * wImag;
138                const twiddledImag = bottomReal * wImag + bottomImag * wReal;
139              
140                // Perform butterfly operation
141                realPart[topIndex] = topReal + twiddledReal;
142                imagPart[topIndex] = topImag + twiddledImag;
143                realPart[bottomIndex] = topReal - twiddledReal;
144                imagPart[bottomIndex] = topImag - twiddledImag;
145              
146                // Update twiddle factor for next iteration
147                const nextWReal = wReal * twiddleCos - wImag * twiddleSin;
148                wImag = wReal * twiddleSin + wImag * twiddleCos;
149                wReal = nextWReal;
150            }
151        }
152    }
153
154    // Normalize values for inverse FFT
155    if (invert) {
156        for (let i = 0; i < size; ++i) {
157            realPart[i] /= size;
158            imagPart[i] /= size;
159        }
160    }
161}
162

Time and Space Complexity

The time complexity of this polynomial multiplication algorithm using FFT (Fast Fourier Transform) is O(n log n), where n is the next power of 2 greater than or equal to len(poly1) + len(poly2) - 1.

Time Complexity Analysis:

The algorithm first pads both polynomials to length n (next power of 2), which takes O(n) time
The FFT function _fft() is called three times (twice for forward transform, once for inverse transform)
Each FFT call has complexity O(n log n):
- The bit-reversal permutation loop takes O(n) time
- The main FFT computation has log n levels (since len_ doubles each iteration from 2 to n)
- At each level, all n elements are processed exactly once, giving O(n) work per level
- Total: O(n log n) per FFT call
The element-wise multiplication of transformed arrays takes O(n) time
Overall: O(n) + 3 * O(n log n) + O(n) = O(n log n)

Space Complexity Analysis: The space complexity is O(n), where n is the next power of 2 greater than or equal to the sum of the input polynomial degrees.

Two arrays fa and fb are created, each of size n: O(n) space
The FFT function operates in-place on these arrays, requiring only O(1) additional space for temporary variables
The final result list of size m = len(poly1) + len(poly2) - 1 uses O(m) = O(n) space
Total auxiliary space: O(n)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Numerical Precision Errors with Floating-Point Arithmetic

The Problem: FFT operates in the complex number domain using floating-point arithmetic. When converting back to integer coefficients, rounding errors can accumulate, especially for:

Large coefficients (e.g., values near 10^9)
Long polynomials with many terms
Multiple intermediate calculations involving trigonometric functions

Example Scenario:

# Large coefficients can lose precision
poly1 = [999999999, 999999999]
poly2 = [999999999, 999999999]
# Expected: [999999998000000001, 1999999998000000000, 999999998000000001]
# Actual might be off by ±1 or more due to floating-point errors

Solutions:

a) Use Number Theoretic Transform (NTT) for Integer Polynomials:

class Solution:
    def multiply(self, poly1: List[int], poly2: List[int]) -> List[int]:
        # For integer-only operations, use NTT with modular arithmetic
        MOD = 998244353  # Prime with 2^23 * 119 + 1 form
        g = 3  # Primitive root
      
        def ntt(a, invert=False):
            n = len(a)
            if n == 1:
                return
          
            # Similar structure to FFT but with modular arithmetic
            # ... (implementation details)

b) Implement Multi-Precision or Use Decimal for Better Accuracy:

from decimal import Decimal, getcontext

class Solution:
    def multiply(self, poly1: List[int], poly2: List[int]) -> List[int]:
        # Set higher precision
        getcontext().prec = 50
      
        # Convert to Decimal for calculations
        # ... (rest of implementation with Decimal type)

2. Incorrect Handling of Edge Cases

The Problem: The code might fail or produce incorrect results for:

Single-element polynomials (constants)
Polynomials with all zero coefficients
Very small polynomials where FFT overhead isn't worth it

Solutions:

class Solution:
    def multiply(self, poly1: List[int], poly2: List[int]) -> List[int]:
        # Handle edge cases explicitly
        if not poly1 or not poly2:
            return []
      
        # For very small polynomials, use naive multiplication
        if len(poly1) * len(poly2) <= 64:  # Threshold can be tuned
            return self._naive_multiply(poly1, poly2)
      
        # Continue with FFT for larger inputs
        # ...
  
    def _naive_multiply(self, poly1: List[int], poly2: List[int]) -> List[int]:
        result = [0] * (len(poly1) + len(poly2) - 1)
        for i in range(len(poly1)):
            for j in range(len(poly2)):
                result[i + j] += poly1[i] * poly2[j]
        return result

3. Memory Inefficiency with Padding

The Problem: Always padding to the next power of 2 can waste significant memory. For example, if the result needs 513 coefficients, the code pads to 1024, nearly doubling memory usage.

Solution - Use Bluestein's Algorithm for Non-Power-of-2 Sizes:

class Solution:
    def multiply(self, poly1: List[int], poly2: List[int]) -> List[int]:
        result_size = len(poly1) + len(poly2) - 1
      
        # Check if padding overhead is too large
        fft_size = 1
        while fft_size < result_size:
            fft_size <<= 1
      
        if fft_size > 1.5 * result_size:  # More than 50% overhead
            # Use Bluestein's algorithm or mixed-radix FFT
            return self._bluestein_multiply(poly1, poly2)
      
        # Continue with standard FFT
        # ...

4. Overflow in Bit-Reversal Index Calculation

The Problem: The bit-reversal permutation code uses bit manipulation that might behave unexpectedly for very large array sizes or in different programming environments.

Solution - Use More Robust Bit-Reversal:

def _bit_reverse_copy(self, coefficients: List[complex]) -> List[complex]:
    n = len(coefficients)
    result = [0j] * n
    bits = n.bit_length() - 1
  
    for i in range(n):
        # Calculate bit-reversed index more explicitly
        rev = 0
        temp = i
        for _ in range(bits):
            rev = (rev << 1) | (temp & 1)
            temp >>= 1
        result[rev] = coefficients[i]
  
    return result

These pitfalls are particularly important to consider when implementing FFT-based polynomial multiplication in production code where accuracy and efficiency are critical.

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27

1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30

1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

["jk", "mno"]

["jm", "kn", "lo"]

["jklmnp"]

["jm","jn","jo","km","kn","ko","lm","ln","lo"]

I don't know