LeetCode · #238

Product of Array Except Self Solution

Given an integer array nums, return an array answer where answer[i] is the product of all elements except nums[i]. You must solve it without using division and in O(n) time.

01
Section One · Problem

Problem Statement

🏷️

Difficulty

Medium

🔗

LeetCode

Problem #238

🏗️

Pattern

Prefix Sum — prefix & suffix products

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i]. The algorithm must run in O(n) time and must not use the division operation.

Example
Input: nums = [1, 2, 3, 4] Output: [24, 12, 8, 6] // answer[0] = 2×3×4 = 24, answer[1] = 1×3×4 = 12, ...
Example 2
Input: nums = [-1, 1, 0, -3, 3] Output: [0, 0, 9, 0, 0] // Zero at index 2 zeros out all other positions; answer[2] = (-1)×1×(-3)×3 = 9
Constraints
• 2 ≤ nums.length ≤ 10⁵ • -30 ≤ nums[i] ≤ 30 • The product of any prefix or suffix fits in a 32-bit integer • You must NOT use division ↑ Key constraint — forces prefix/suffix approach
02
Section Two · Approach 1

Brute Force — O(n²)

For each index i, multiply all other elements together. Two nested loops — the outer selects the position, the inner computes the product of everything except that position.

Why it works

Directly implements the definition: answer[i] = ∏ nums[j] for all j ≠ i. Correct by construction — every non-self element is multiplied.

Why we can do better
Problem: Each element's product is computed independently, repeating most of the multiplication. The product of elements to the left of index i overlaps heavily with index i-1. Prefix and suffix products precompute these running products, reducing repeated work from O(n) per element to O(1).
Java — Brute Force
class Solution { public int[] productExceptSelf(int[] nums) { int n = nums.length; int[] answer = new int[n]; for (int i = 0; i < n; i++) { int product = 1; for (int j = 0; j < n; j++) { if (j != i) product *= nums[j]; } answer[i] = product; } return answer; } }
Python — Brute Force
class Solution: def productExceptSelf(self, nums: list[int]) -> list[int]: n = len(nums) answer = [1] * n for i in range(n): product = 1 for j in range(n): if j != i: product *= nums[j] answer[i] = product return answer
MetricValue
TimeO(n²) — n multiplications per element
SpaceO(1) — excluding the output array
03
Section Three · Approach 2

Prefix & Suffix Products — O(n)

The product of all elements except nums[i] equals product of everything to the left × product of everything to the right. Compute running prefix products left-to-right, then multiply in suffix products right-to-left — all in the output array itself.

💡 Mental model: Imagine you're standing in a line of people, each holding a number. You want to know the product of everyone else's number — without asking each person individually. Instead, a runner goes left-to-right whispering "the product of everyone to your left is X." Then a second runner goes right-to-left whispering "multiply by Y — the product of everyone to your right." Each person now has the complete product of all others. Two passes, no division.
Algorithm — Two-pass prefix/suffix
  • Step 1: Initialize answer[i] = 1 for all i.
  • Step 2: Left pass — maintain a running prefix = 1. For each i from 0 to n−1: set answer[i] = prefix, then prefix *= nums[i].
  • Step 3: Right pass — maintain a running suffix = 1. For each i from n−1 to 0: set answer[i] *= suffix, then suffix *= nums[i].
  • Step 4: Return answer — each slot now holds left-product × right-product.
🎯 When to recognize this pattern:
  • Any time a problem asks for a value that depends on all other elements (excluding the current one) — think prefix/suffix decomposition.
  • The signal is "for each index, compute something from left side AND right side." This pattern appears in LC 238, LC 42 (Trapping Rain Water — prefix max + suffix max), LC 135 (Candy — left and right passes), and range-product queries.
Why no extra arrays needed:
  • The output array itself stores the prefix products from the left pass.
  • The right pass multiplies suffix products directly into the output.
  • We only need one extra variable (suffix) as we sweep right-to-left — achieving O(1) extra space beyond the required output.
04
Section Four · Trace

Visual Walkthrough

Trace through nums = [1, 2, 3, 4]:

Prefix & Suffix Products — two passes building the answer
INPUT ARRAY 1 [0] 2 [1] 3 [2] 4 [3] Left Pass → (prefix products) prefix starts at 1, stored BEFORE multiplying current element i=0: answer[0] = prefix = 1, then prefix = 1×1 = 1 i=1: answer[1] = prefix = 1, then prefix = 1×2 = 2 i=2: answer[2] = prefix = 2, then prefix = 2×3 = 6 i=3: answer[3] = prefix = 6, then prefix = 6×4 = 24 answer[] after left pass: 1 1 2 6 ← Right Pass (suffix products multiplied in) suffix starts at 1, multiplied INTO answer BEFORE updating suffix i=3: answer[3] = 6 × suffix(1) = 6, then suffix = 1×4 = 4 i=2: answer[2] = 2 × suffix(4) = 8, then suffix = 4×3 = 12 i=1: answer[1] = 1 × suffix(12) = 12, then suffix = 12×2 = 24 i=0: answer[0] = 1 × suffix(24) = 24, then suffix = 24×1 = 24 FINAL answer[]: 24 12 8 6 Answer: [24, 12, 8, 6] ✓
Notice:
  • Two linear passes — no nested loops.
  • The left pass builds "product of everything before me." The right pass multiplies in "product of everything after me." Each element's final value is left × right — the product of all others.
05
Section Five · Implementation

Code — Java & Python

Java — Prefix/Suffix in-place
class Solution { public int[] productExceptSelf(int[] nums) { int n = nums.length; int[] answer = new int[n]; // Left pass — answer[i] holds product of all elements left of i int prefix = 1; for (int i = 0; i < n; i++) { answer[i] = prefix; prefix *= nums[i]; // include current for next position } // Right pass — multiply suffix product into each position int suffix = 1; for (int i = n - 1; i >= 0; i--) { answer[i] *= suffix; suffix *= nums[i]; // include current for next position } return answer; } }
Python — Prefix/Suffix in-place
class Solution: def productExceptSelf(self, nums: list[int]) -> list[int]: 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 suffix products in suffix = 1 for i in range(n - 1, -1, -1): answer[i] *= suffix suffix *= nums[i] return answer
06
Section Six · Analysis

Complexity Analysis

Approach Time Space Trade-off
Brute Force O(n²) O(1) Correct but too slow for n = 10⁵
Total Product ÷ current O(n) O(1) Violates the "no division" constraint; fails on zeros
Prefix/Suffix ← optimal O(n) O(1)* Two passes, no division. *O(1) extra beyond output array.
Why not division?:
  • Division seems tempting — compute total product, then answer[i] = total / nums[i].
  • But: (1) the problem explicitly forbids it, (2) zeros break it — dividing by zero is undefined, and you'd need special-case handling for one or more zeros.
  • The prefix/suffix approach handles zeros naturally because it never divides.
07
Section Seven · Edge Cases

Edge Cases & Pitfalls

Case Input Why It Matters
Contains one zero [1, 2, 0, 4] Only the zero's position gets a non-zero product (1×2×4=8). All others become 0.
Contains two zeros [0, 2, 0, 4] Every position includes at least one zero → entire answer is [0, 0, 0, 0].
Negative numbers [-1, 2, -3, 4] Sign handling is automatic — multiplication preserves sign correctly.
Two elements [3, 5] Minimum input. answer = [5, 3] — each is the other's value.
All ones [1, 1, 1, 1] Every product is 1. Prefix/suffix stays 1 throughout — the identity case.
Large array n = 10⁵, values in [-30, 30] Guaranteed to fit in 32-bit int per constraints. No overflow concern.
⚠ Common Mistake: Confusing the order of operations in the left pass — storing prefix into answer[i] before multiplying prefix *= nums[i]. If you multiply first, you include nums[i] in its own product. The correct sequence is: store, then update. Same rule applies in the right pass.

← Back to Arrays & Hashing problems