Product Except Self LeetCode 238 Guide

LeetCode 238 gives you an integer array nums of length n. You must return an array answer where answer[i] equals the product of every element in nums except nums[i] itself. For example, given [1, 2, 3, 4] the output is [24, 12, 8, 6]: each position holds the product of all other elements.

The problem explicitly forbids using division and requires O(n) time. The follow-up challenge asks you to solve it using O(1) extra space (not counting the output array, which does not count as extra space per the problem statement).

Key constraints and facts to keep in mind before designing your solution:

The tempting shortcut is to compute the total product of all elements and then divide by nums[i] for each position. When no zeros are present this works, but zeros break the approach in two distinct ways: if exactly one element is zero, only the position of that zero has a nonzero answer; if two or more elements are zero, every answer is zero.

Handling these cases correctly requires multiple conditional branches, tracking zero counts, and special-casing the index of the zero element. Even ignoring the problem's explicit ban on division, this leads to messy and error-prone code that is hard to verify in an interview setting.

More fundamentally, the prefix/suffix product approach is cleaner, more general, and maps directly onto the problem structure. It avoids division entirely and handles all zero configurations naturally without any extra logic.

The key observation is that answer[i] = (product of all elements to the left of i) * (product of all elements to the right of i). These two parts can be computed independently in two linear passes, then multiplied together element-wise.

First pass (left to right): build a prefix array where prefix[i] holds the product of nums[0] through nums[i-1]. By convention prefix[0] = 1 because there are no elements to the left of index 0. Second pass (right to left): build a suffix array where suffix[i] holds the product of nums[i+1] through nums[n-1]. Again suffix[n-1] = 1 by convention.

The final answer at each position is simply prefix[i] * suffix[i]. Both arrays are O(n) in size, and each pass is O(n) in time, giving an overall O(n) time and O(n) space solution. The O(1) space optimization eliminates the need for a separate suffix array.

The O(1) space trick reuses the output array for the prefix products in the first pass, then sweeps right to left with a single integer variable tracking the running suffix product. This eliminates the separate suffix array entirely.

First pass: use the output array itself to store prefix products exactly as described above — answer[0] = 1, answer[i] = answer[i-1] * nums[i-1]. Second pass: initialize a variable suffix = 1. Traverse from right to left: multiply answer[i] by suffix, then update suffix = suffix * nums[i]. After both passes, answer[i] holds the correct result.

Because the output array is declared "free" by the problem, and the only additional storage is the single suffix integer variable, the extra space is O(1). This is the solution that impresses interviewers and earns full marks on the follow-up.

Starting with nums = [1, 2, 3, 4]. First pass (left to right): answer starts as [1, 1, 1, 1]. At i=1: answer[1] = answer[0] * nums[0] = 1 * 1 = 1. At i=2: answer[2] = answer[1] * nums[1] = 1 * 2 = 2. At i=3: answer[3] = answer[2] * nums[2] = 2 * 3 = 6. After left pass: answer = [1, 1, 2, 6].

Second pass (right to left): initialize suffix = 1. At i=3: answer[3] *= suffix → 6 * 1 = 6; suffix *= nums[3] → 1 * 4 = 4. At i=2: answer[2] *= suffix → 2 * 4 = 8; suffix *= nums[2] → 4 * 3 = 12. At i=1: answer[1] *= suffix → 1 * 12 = 12; suffix *= nums[1] → 12 * 2 = 24. At i=0: answer[0] *= suffix → 1 * 24 = 24; suffix *= nums[0] → 24 * 1 = 24.

Final answer: [24, 12, 8, 6]. Verification: 24 = 2*3*4, 12 = 1*3*4, 8 = 1*2*4, 6 = 1*2*3. All correct. The trace makes clear that the left pass accumulates running left products and the right pass multiplies in running right products — together they cover all elements except the current index.

Python: def productExceptSelf(nums): n = len(nums); answer = [1] * n — left pass: for i in range(1, n): answer[i] = answer[i-1] * nums[i-1] — right pass: suffix = 1; for i in range(n-2, -1, -1): answer[i] *= suffix; suffix *= nums[i] — return answer. Two simple loops, O(n) time, O(1) extra space.

Java: public int[] productExceptSelf(int[] nums) { int n = nums.length; int[] answer = new int[n]; Arrays.fill(answer, 1); for (int i = 1; i < n; i++) answer[i] = answer[i-1] * nums[i-1]; int suffix = 1; for (int i = n-2; i >= 0; i--) { answer[i] *= suffix; suffix *= nums[i]; } return answer; }. Identical logic, same two passes, fully O(1) extra space.

Both solutions handle all edge cases cleanly: arrays containing zeros (no special casing needed), negative numbers (products work naturally), and n = 2 (each pass executes exactly once). The code is concise, readable, and straightforward to explain during an interview.

Product of Array Except Self is the canonical prefix/suffix product problem. The same two-pass left-right structure appears in Trapping Rain Water (LeetCode 42), where you precompute left-max and right-max arrays and take their minimum at each index. The structural similarity is not a coincidence — both problems decompose an answer at each index into a left contribution and a right contribution.

Prefix Sum (the additive analogue) underlies Subarray Sum Equals K (LeetCode 560), Range Sum Query, and many sliding window problems. Recognizing that product and sum both admit prefix precomputation is a powerful pattern generalization for algorithm interviews.

After mastering this problem, explore Subarray Sum Equals K for the additive prefix pattern, Container With Most Water for two-pointer greedy, and the broader Dynamic Programming category for problems that generalize running accumulations into full DP tables.