Skip to content
LEETFLIX

Product of Array Except Self

MediumArrayPrefix sum
Solve on LeetCode

Medium · prefix × suffix products. Real solution for this problem — same player as the hand-authored deep-dives.

01

Problem

Read the prompt, flip through the examples, then steal the idea.

LeetCode 238. Product of Array Except Self. The copyrighted prompt is on LeetCode. This page is a working prefix × suffix products for this problem: editable input, Python, Go, and a step-by-step animation.

Constraints

  • —Player inputs are capped so the animation stays readable.
  • —Match LeetCode's own constraints when you submit there.

Examples

Input

nums =
[1, 2, 3, 4]

Output

[24, 12, 8, 6]

02

Solution

Python and Go. The walkthrough below runs this same code.

Approach 1Optimal▶ Animated

Prefix pass, then suffix pass

out[i] is (product of everything left of i) × (product of everything right of i). Two linear sweeps, no division.

A left-to-right pass writes prefix products. A right-to-left pass multiplies in the suffix products.

Algorithm

  1. Seed out with prefix products (out[0] = 1).
  2. Walk right-to-left with a running suffix product and multiply into out.
Time
O(n)
Space
O(1)

Output array does not count.

Solution.py
class Solution:    def productExceptSelf(self, nums: list[int]) -> list[int]:        n = len(nums)        out = [1] * n        pref = 1        for i in range(n):            out[i] = pref            pref *= nums[i]        suff = 1        for i in range(n - 1, -1, -1):            out[i] *= suff            suff *= nums[i]        return out
Watch this run

03

Interactive walkthrough

Playing “Prefix pass, then suffix pass”. Edit the input, hit Run, then scrub.

Approach: Prefix pass, then suffix pass

Loading animation…