Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Multiplying two degree-n polynomials (or two big integers) by the schoolbook method is O(n²) because every coefficient pair multiplies. FFT drops it to O(n log n). The idea: a degree-n polynomial is determined by its values at n+1 points, and in point-value form multiplication is just pointwise multiply — O(n). The Fast Fourier Transform evaluates a polynomial at the 2ᵏ complex roots of unity in O(n log n) by divide-and-conquer (split into even/odd-indexed coefficients), and the inverse FFT interpolates back. So: FFT both inputs, multiply values pointwise, inverse-FFT, round to integers.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you understand that polynomial multiplication is convolution, that values-at-points multiply pointwise, and that the FFT evaluates/interpolates at roots of unity in O(n log n) — plus the practical details (power-of-two padding, the 1/N in the inverse, rounding).
Where candidates slip
Forgetting the 1/N scaling in the inverse FFT, not padding to a power of two, truncating instead of rounding the inverse result, or using floating-point FFT where exactness is required (should be NTT).
How to stand out
State the convolution theorem precisely, explain the even/odd split that gives the O(n log n) recurrence, and mention NTT (FFT over a prime field) as the exact-arithmetic alternative for integer convolutions.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachExplore the full treeCollapse the tree
How to read it:FFT moves both inputs to value space where multiplication is pointwise; inverse FFT brings the product back to coefficients.
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2
Schoolbook Convolution (Baseline)
1Hint 1Explore hintHide hint
The product coefficient cₖ is the sum of all aᵢ·bⱼ with i + j = k. How would you compute every cₖ directly from that definition?
2Hint 2Explore hintHide hint
Two nested loops: for each i and each j, add aᵢ·bⱼ into c[i + j]. That's the literal convolution.
3Hint 3Explore hintHide hint
It's O(n²) — every pair (i, j) contributes once. For n ≈ 2·10⁵ that's ~4·10¹⁰ multiply-adds, too slow. What lets us avoid touching every pair?
A · Core idea
Compute the convolution straight from its definition: cₖ = Σ_{i+j=k} aᵢ·bⱼ. Run two nested loops and accumulate each aᵢ·bⱼ into c[i+j].
Why it is correct. It is the definition of polynomial multiplication — every term aᵢxⁱ · bⱼxʲ = aᵢbⱼ x^{i+j} lands in coefficient i+j, and we add up all such contributions. Nothing can go wrong beyond integer overflow if coefficients are large (use 64-bit accumulators).
Why it does not scale. There are lenA · lenB pairs (i, j), and each is visited exactly once, so the cost is Θ(n²). For n up to 2·10⁵, that's on the order of 4·10¹⁰ operations — far beyond a time limit. The work is fundamentally 'every coefficient of A interacts with every coefficient of B'.
The structural waste. The quadratic cost comes from working in the coefficient representation, where multiplication is convolution. If we could switch to a representation where multiplication is pointwise (one multiply per index, O(n) total), the only remaining cost would be the conversion in and out. That conversion is exactly what the FFT makes cheap.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
A = [1, 2], B = [1, 3]i=0,j=0
c[0] += 1·1
c=[1,0,0][1, 5, 6]C · Code with teaching comments
Reference implementation previewpublic long[] multiply(int[] a, int[] b) { long[] c = new long[a.length + b.length - 1]; for (int i = 0; i < a.length; i++) { for (int j = 0; j < b.length; j++) { c[i + j] += (long) a[i] * b[j]; // 64-bit accumulateExplore the full codeHide the full code
D · Why it works and complexityO(n²) timeO(n) spaceOpen the invariant and proofExplore the proofHide the proof
Schoolbook is the honest definition and the right tool when n is small — its constant factor beats FFT until n is in the thousands. Its only flaw is the O(n²) from staying in coefficient space. FFT's entire contribution is a fast change of representation to where multiplication is O(n).
ComplexityO(n²) time, O(n) space — The double loop over all (i, j) pairs does lenA·lenB ≈ n² multiply-adds, hence O(n²) time. The output array of length lenA + lenB − 1 is O(n) space.
E · Edge cases and pitfalls3Using it for n ≈ 2·10⁵ — O(n²) is far too slow.Explore edge casesHide edge cases
Pitfalls
- Using it for n ≈ 2·10⁵ — O(n²) is far too slow.
- Accumulating products in a 32-bit int — overflow; use long.
- Allocating the wrong output length (must be lenA + lenB − 1).
Approach 2 of 2 · Optimal
Iterative FFT + Pointwise Multiply (Optimal)
1Hint 1Explore hintHide hint
A degree-d polynomial is uniquely determined by its values at d+1 points. In value form, the product at a point is just the product of the two values. What stops us from using arbitrary evaluation points?
2Hint 2Explore hintHide hint
Evaluating at arbitrary points is O(n²). But the complex Nth roots of unity have symmetry: ω^{k+N/2} = −ω^k. Splitting the polynomial into even-indexed and odd-indexed coefficients lets you compute the values at all N roots from the two half-size transforms in O(n) extra work.
3Hint 3Explore hintHide hint
That recurrence T(N) = 2T(N/2) + O(N) is O(n log n) — the FFT. The inverse FFT is the same routine with conjugated roots, then divide by N. Round the real parts at the end.
A · Core idea
Change representation so that multiplication becomes pointwise, using the roots of unity as the magic evaluation points.
The convolution theorem (the core fact). A polynomial product is a convolution of coefficients. The theorem says: convolution in coefficient space equals pointwise multiplication in value space. So if you evaluate A and B at the same set of points, the product polynomial C = A·B takes the value A(xᵢ)·B(xᵢ) at each point xᵢ. Evaluating is O(n) once you can transform; the multiply is O(n); the only question is how to evaluate and interpolate fast.
Why the roots of unity. A degree-N distinct points. Choosing those points to be the Nth complex roots of unity ωᵏ = e^{2πik/N} unlocks a symmetry: ω^{k+N/2} = −ωᵏ. Write A(x) = A_even(x²) + x·A_odd(x²), splitting coefficients by index parity. Evaluated at ωᵏ and ω^{k+N/2}, the two share the same A_even(ω^{2k}) and A_odd(ω^{2k}) and differ only in the sign of the x factor. So computing all N values reduces to two half-size transforms plus O(N) combination work — the butterfly. That recurrence T(N) = 2T(N/2) + O(N) solves to O(N log N). This is the Fast Fourier Transform.
The inverse FFT. Interpolating values back to coefficients is the same transform evaluated at the conjugate roots ω^{−k} (equivalently e^{−2πik/N}), followed by dividing every entry by N. The 1/N factor is not optional — it's the normalisation that makes forward-then-inverse the identity. Skip it and every coefficient comes out scaled by N.
The full pipeline. Pad A and B with zeros up to N, the next power of two ≥ lenA + lenB − 1 (the product has that many coefficients, and the radix-2 FFT needs a power-of-two length). Run FFT(A) and FFT(B); multiply the value arrays pointwise; run the inverse FFT; the real parts (rounded to the nearest integer) are the product coefficients. For big-integer multiplication, treat digits as coefficients and propagate base-10 carries at the end.
Why round, not truncate. FFT uses floating-point double arithmetic, so the recovered coefficients are integers plus a tiny error. Math.round snaps to the correct integer; truncation would turn 5.9999999 into 5. This is safe only while coefficients are small enough that accumulated error stays below 0.5.
Exactness via NTT. When floating error is unacceptable (large coefficients, adversarial inputs), replace the complex roots of unity with a primitive root of unity in a prime field — the Number-Theoretic Transform. It runs the identical butterfly structure in modular integer arithmetic, so results are exact, at the cost of working modulo a special prime (e.g. 998244353) and CRT-combining if one modulus isn't enough.
Overflow / precision notes. Complex FFT uses double; the danger is precision, not integer overflow. Keep coefficients modest or split them. In an NTT, reduce mod the prime after each multiply and use long. Python's complex and big ints make the reference implementation straightforward.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
A = [1, 2], B = [1, 3]Array state
coeffs
padded inputs
[1, 5, 6]C · Code with teaching comments
D · Why it works and complexityO(n log n) timeO(n) spaceOpen the invariant and proofExplore the proofHide the proof
FFT is a representation change, not a multiplication trick: it ships the polynomial to 'value space' where multiplication is one multiply per point, then ships the answer home. The whole speedup lives in evaluating at the roots of unity, where the even/odd split halves the problem at O(N) cost per level. Remember the three practical hazards — power-of-two padding, the 1/N in the inverse, and rounding — and reach for NTT whenever you need exact integer convolution.
ComplexityO(n log n) time, O(n) space — Each FFT/inverse-FFT runs the butterfly network over log₂N levels, each level touching all N elements once → O(N log N). The pointwise multiply is O(N). With N the next power of two ≥ lenA+lenB−1, total time is O(n log n) and space O(n).
E · Edge cases and pitfalls9one input empty — Product is empty; guard lenA·lenB = 0 before transforming.Explore edge casesHide edge cases
Edge cases handled
one input emptyProduct is empty; guard lenA·lenB = 0 before transforming.A = B (squaring)Transform once, square the values pointwise — saves one FFT.single-element inputsneed = 1, n = 1; the FFT is a no-op and the product is the single coefficient product.big-integer multiplyConvolve digit arrays, then propagate base-10 carries to normalise digits.
Pitfalls
- Forgetting the 1/N division in the inverse FFT — every coefficient is N times too big.
- Not padding to a power of two — the radix-2 split breaks.
- Truncating instead of rounding the inverse result — off-by-one coefficients.
- Using complex FFT when exact integers are required — use NTT instead.
- Letting floating error exceed 0.5 with large coefficients — split coefficients or switch to NTT.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewimport java.util.*; public long[] multiply(int[] a, int[] b) { int need = a.length + b.length - 1; int n = Integer.highestOneBit(need - 1) << 1; // next power of two >= needExplore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Missing the inverse-FFT 1/N normalisation
Forward then inverse FFT is the identity ONLY if the inverse divides every entry by N. Skip it and the recovered coefficients are all scaled by N — silently wrong by a constant factor.
Explore the code comparisonHide the code comparison
Missing the inverse-FFT 1/N normalisation
Forward then inverse FFT is the identity ONLY if the inverse divides every entry by N. Skip it and the recovered coefficients are all scaled by N — silently wrong by a constant factor.
Don't write this
self.fft(fc, True)
# forgot to divide by n inside fft when invert=True
return [round(fc[i].real) for i in range(need)] # N times too largeWrite this instead
# inside fft(): if invert: for i in range(n): a[i] /= n
self.fft(fc, True)
return [round(fc[i].real) for i in range(need)]2Truncating instead of rounding
FFT arithmetic is floating point, so an integer coefficient comes back as e.g. 5.9999999 or 6.0000001. int() truncates 5.9999999 to 5; Math.round / round snaps to the correct integer.
Explore the code comparisonHide the code comparison
Truncating instead of rounding
FFT arithmetic is floating point, so an integer coefficient comes back as e.g. 5.9999999 or 6.0000001. int() truncates 5.9999999 to 5; Math.round / round snaps to the correct integer.
Don't write this
c[i] = (long) re1[i]; // truncates 5.9999999 -> 5Write this instead
c[i] = Math.round(re1[i]); // rounds to nearest integer3Using complex FFT when exactness is required
For large coefficients the accumulated double error can exceed 0.5, so rounding lands on the wrong integer. Exact integer convolution needs NTT (a transform over a prime field) where all arithmetic is modular and exact.
Explore the code comparisonHide the code comparison
Using complex FFT when exactness is required
For large coefficients the accumulated double error can exceed 0.5, so rounding lands on the wrong integer. Exact integer convolution needs NTT (a transform over a prime field) where all arithmetic is modular and exact.
Don't write this
# complex FFT with huge coefficients -> rounding errors -> wrong digitsWrite this instead
# Number-Theoretic Transform mod 998244353 (g = 3 is a primitive root):
# same butterfly structure, but in modular integer arithmetic -> exactRevise
Carry the pattern into the interview
Pattern to remember
Coefficients → values (FFT) → pointwise multiply → values → coefficients (inverse FFT)
Code pattern to memorize
1. pad both arrays to size N = next power of two >= len(A)+len(B)-1
2. A_vals = FFT(A), B_vals = FFT(B) # evaluate at N roots of unity
3. C_vals[i] = A_vals[i] * B_vals[i] # pointwise, O(N)
4. C = inverseFFT(C_vals) # interpolate back
5. round real parts to nearest integer (carry for big-int multiply)Rules to remember
- 1Pad the combined length to the next power of two ≥
lenA + lenB − 1; the radix-2 FFT needs a power-of-two size, and the product has that many coefficients. - 2The convolution theorem is the whole trick: pointwise product in value space equals convolution (polynomial product) in coefficient space.
- 3Inverse FFT is the forward FFT with conjugated roots (or
e^{+2πi/N}) followed by dividing every entry by N — forgetting the/Nscales the answer wrong. - 4Round the inverse-FFT real parts to the nearest integer; floating-point error is small but nonzero, so
Math.round, not truncation. For big integers, propagate base-10 carries afterward. - 5Use double precision and watch error growth for large coefficients; for exact integer results prefer NTT (number-theoretic transform) over a prime modulus to avoid floating point entirely.
Use this pattern when
- Multiply two **large polynomials** or **big integers** with thousands+ of terms/digits
- Compute a **convolution** of two long sequences (signal processing, counting with generating functions)
- String matching with wildcards, or counting pairs with a target sum via polynomial squaring
- Any O(n²) 'all pairs (i, j) contribute to bucket i+j' that you want at O(n log n)
Choose another pattern when
- n is small (≤ a few thousand) → schoolbook O(n²) is simpler and the constant factor wins
- You need an **exact** integer convolution and floating error is unacceptable → use NTT, not complex FFT
- The operation isn't a convolution (indices don't add) → FFT doesn't apply
- You only multiply two small numbers → just use the language's big-integer multiply
Interview takeaway
FFT multiplies in O(n log n) by changing representation: a polynomial is equally described by its coefficients or by its values at enough points, and in the value representation multiplication is trivially pointwise. The Fast Fourier Transform is just a clever O(n log n) way to evaluate at the roots of unity (split even/odd coefficients, recurse) and to invert that evaluation. The convolution theorem — pointwise in value space = convolution in coefficient space — is the one fact to remember; NTT is the exact-integer cousin.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternFFT / convolution via change of representation. Reach for it whenever an O(n²) computation is 'every pair (i, j) contributes to bucket i+j' — a convolution — and n is large. Move to value space (FFT), multiply pointwise, move back (inverse FFT). NTT is the exact-integer variant; both power big-integer multiplication, string matching with wildcards, and generating-function counting.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Number-Theoretic Transform (NTT)Coming soonFFT over a prime field — exact integer convolution, no floating point.
- Modular ExponentiationNTT needs powers of a primitive root mod p — computed with fast exponentiation.
- Chinese Remainder TheoremCombine NTT results modulo several primes to recover large exact coefficients.
- Big Integer MultiplicationComing soonTreat digits as polynomial coefficients, FFT-multiply, then propagate carries.