Data Structures & Algorithms › Arrays
💡
Exercise 18

Product of Array Except Self 25 XP Medium

LeetCode Ctrl+Enter Run Ctrl+S Save

LeetCode #238: Product of Array Except Self — a tricky problem that teaches prefix and suffix patterns.

Given an array nums, return an array answer where answer[i] is the product of all elements EXCEPT nums[i]. You cannot use division.

Example:
[1, 2, 3, 4] → [24, 12, 8, 6]
answer[0] = 2×3×4 = 24, answer[1] = 1×3×4 = 12, etc.

The Trick — Prefix × Suffix:
For each position, the answer is (product of everything to the LEFT) × (product of everything to the RIGHT).

# Step 1: Build prefix products (left to right) # [1, 2, 3, 4] # ^ prefix[0] = 1 (nothing to the left) # ^ prefix[1] = 1 # ^ prefix[2] = 1 × 2 = 2 # ^ prefix[3] = 1 × 2 × 3 = 6 # prefix = [1, 1, 2, 6] # Step 2: Multiply by suffix products (right to left) # suffix starts at 1 # i=3: answer[3] = 6 × 1 = 6, suffix = 1 × 4 = 4 # i=2: answer[2] = 2 × 4 = 8, suffix = 4 × 3 = 12 # i=1: answer[1] = 1 × 12 = 12, suffix = 12 × 2 = 24 # i=0: answer[0] = 1 × 24 = 24 # answer = [24, 12, 8, 6] ✓

💭 Time to code! Use the step-by-step approach described above. Don't peek at the solution — try first! 🚀

Complexity: Time O(n), Space O(1) extra (the output array doesn't count)

📋 Instructions
Implement `productExceptSelf(nums)` using the **prefix-suffix approach**. - Do NOT use division - First pass: build prefix products into the answer array - Second pass: multiply by suffix products from right to left - Return the answer array
Two passes. Pass 1 (left→right): prefix = 1, then for each i: answer[i] = prefix, then prefix *= nums[i]. Pass 2 (right→left): suffix = 1, then for i from n-1 to 0: answer[i] *= suffix, then suffix *= nums[i].
⚠️ Try solving it yourself first — you'll learn more!
def productExceptSelf(nums):
    n = len(nums)
    answer = [1] * n
    
    # Left pass: prefix products
    prefix = 1
    for i in range(n):
        answer[i] = prefix
        prefix *= nums[i]
    
    # Right pass: multiply by suffix products
    suffix = 1
    for i in range(n - 1, -1, -1):
        answer[i] *= suffix
        suffix *= nums[i]
    
    return answer
🧪 Test Cases
Input
productExceptSelf([1, 2, 3, 4])
Expected
[24, 12, 8, 6]
Test case 1
Input
productExceptSelf([-1, 1, 0, -3, 3])
Expected
[0, 0, 9, 0, 0]
Test case 2
← Previous Next Exercise →
main.py
Hi! I'm Rex 👋
Output
Ready. Press ▶ Run or Ctrl+Enter.
›