Product of Array except Self

Problem Link

238. Product of Array Except Self – LeetCode

Problem Statement

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].

Constraints:

• You must solve it in O(n) time.

• You cannot use the division operation.

• The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

Examples

Example 1:

Input: nums = [1, 2, 3, 4]
Output: [24, 12, 8, 6]
Explanation: 
- answer[0] = 2 * 3 * 4 = 24
- answer[1] = 1 * 3 * 4 = 12
- answer[2] = 1 * 2 * 4 = 8
- answer[3] = 1 * 2 * 3 = 6

Example 2:

Input: nums = [-1, 1, 0, -3, 3]
Output: [0, 0, 9, 0, 0]
Explanation: Any position that includes the zero will become zero except the position where zero is excluded in the product.

Constraints

• 2 <= nums.length <= 10⁵

• -30 <= nums[i] <= 30

• The product of all elements except self is guaranteed to fit in a 32-bit signed integer.

Intuition

We need to find the product of all elements except the current one, for every index.

Using division would make this trivial, but since it's not allowed, we approach it with prefix and postfix multiplication.

• For each index i, the result is:

  product of elements before i * product of elements after i
  

We maintain two passes:

1. Left to right to build prefix product

2. Right to left to multiply with postfix product

Approach

1. Initialize an output array ans[] of size n.

2. Traverse from left to right:

   • Use a variable pre to store the product of all elements before current index.

   • Store pre in ans[i], then update pre *= nums[i]

3. Traverse from right to left:

   • Use a variable post to store the product of all elements after current index.

   • Multiply ans[i] *= post, then update post *= nums[i]

4. Return ans

Java Code

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] ans = new int[n];

        // Step 1: Prefix products
        int pre = 1;
        for (int i = 0; i < n; i++) {
            ans[i] = pre;
            pre *= nums[i];
        }

        // Step 2: Postfix products
        int post = 1;
        for (int i = n - 1; i >= 0; i--) {
            ans[i] *= post;
            post *= nums[i];
        }

        return ans;
    }
}

Time and Space Complexity

Note: The space is considered O(1) as per the problem’s definition, since the output array is not counted toward space complexity.

Dry Run

Input:

nums = [1, 2, 3, 4]

Step-by-Step:

Prefix Pass:

pre = 1           → ans = [1, _, _, _]
pre = 1*1 = 1     → ans = [1, 1, _, _]
pre = 1*2 = 2     → ans = [1, 1, 2, _]
pre = 2*3 = 6     → ans = [1, 1, 2, 6]

Postfix Pass:

post = 1           → ans = [1, 1, 2, 6*1=6]
post = 1*4 = 4     → ans = [1, 1, 2*4=8, 6]
post = 4*3 = 12    → ans = [1, 1*12=12, 8, 6]
post = 12*2 = 24   → ans = [1*24=24, 12, 8, 6]

Final Output:

[24, 12, 8, 6]

Key Observations

• Prefix product and postfix product allow us to compute the product except self in one forward and one backward pass.

• No division was used.

• Space-optimized: No need for extra arrays.

Conclusion

This is a classic problem on array transformation using prefix/postfix techniques. It teaches:

• How to simulate exclusion without division

• How to optimize for time and space

• Dual-pass array building logic

This technique appears in many derivative problems, such as:

• Left/Right product sums

• Cumulative product range queries

• Balanced array problems