Product of Array Except Self

LeetCode 238 • Medium • Arrays

Return array where ans[i] = product of all elements except nums[i]. No division. Pass 1: prefix products. Pass 2: suffix × result. O(1) extra space.

TimeO(n)two passes

SpaceO(1)output doesn't count

prefix: — suffix: —

Prefix pass

Suffix pass

Result

prefix

—

suffix

—

Speed:

Ready

Press Play. Pass 1: result[i] = prefix (product of nums[0..i-1]). Pass 2: result[i] *= suffix (product of nums[i+1..n-1]).

✎ Whiteboard

Size:3

⌨ Type It

Practice until you don't need to look. Use the guide comments below as scaffolding. The green highlights are the nuances to burn into memory.

# ─── PRODUCT EXCEPT SELF (LeetCode 238) ───

# Pattern: Prefix pass + suffix pass

# Time: O(n) Space: O(1) output

# 1. Define: productExceptSelf(nums)

# 2. Init result and length:

# n = len(nums)

# result = [1] * n

# 3. Prefix pass (left to right):

# prefix = 1

# for i in range(n):

# result[i] = prefix; prefix *= nums[i]

# 4. Suffix pass (right to left):

# suffix = 1

# for i in range(n-1, -1, -1):

# result[i] *= suffix; suffix *= nums[i]

# 5. Return: return result

# Vars: result, prefix, suffix, i

▼ your implementation ▼

Verify your solution: