1. Understanding the Problem

You are given an integer array nums. Your task is to return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].

For example, if nums = [1, 2, 3, 4], the output array will be [24, 12, 8, 6].

The Core Constraints (The Traps):

This problem comes with two strict constraints that force you away from simple shortcuts:

• You must write an algorithm that runs in O(N) time.
• You cannot use the division operation.
• Follow-up challenge: Can you solve the problem in O(1) extra space complexity? (The output array does not count as extra space for space complexity analysis).

2. The Forbidden Naive Approach: Total Product with Division

If division were allowed, the problem would be trivial: multiply all numbers in the array to get a total product, then loop through the array and calculate answer[i] = total_product / nums[i].

Why This Fails

• Violation of Rules: The problem explicitly forbids division.
• Division by Zero Edge Cases: If the array contains a 0, calculating total_product / 0 raises an undefined division error. If it contains multiple zeros, every output element becomes zero.

3. The Optimal Approach: Prefix and Suffix Products (O(1) Extra Space)

Notice that for any element at index i, the product of all elements except nums[i] can be decomposed into two separate parts:

answer[i] = (product of all numbers to the left of i) × (product of all numbers to the right of i)

Instead of re-calculating products for every index—which would take O(N²) time—we can perform two linear scans:

1. First Pass (Left to Right): Fill the output array with the running product of all elements to the left of each index.
2. Second Pass (Right to Left): Multiply the values in the output array by a running product of all elements to the right of each index.

By using our final output array to store the prefix products directly, we eliminate the need for separate array allocations, achieving optimal O(1) extra space!

4. The Logic Step-by-Step

1. Initialize an array answer of size n where every element is set to 1.
2. Initialize a variable prefix = 1.
3. Left Pass: Iterate through the array from left to right (i = 0 to n - 1):
   • Set answer[i] = prefix (the product of all elements before index i).
   • Update prefix = prefix * nums[i].
4. Initialize a variable suffix = 1.
5. Right Pass: Iterate through the array backwards from right to left (i = n - 1 down to 0):
   • Multiply answer[i] by suffix (answer[i] *= suffix).
   • Update suffix = suffix * nums[i].
6. Return answer.

5. Complexity Analysis

• Time Complexity: O(N) — We scan the array twice (once left-to-right, once right-to-left). Processing each element takes O(1) arithmetic operations.
• Space Complexity: O(1) Extra Space — Beyond two scalar variables (prefix and suffix), we allocate zero additional memory. The output array is explicitly excluded from space complexity evaluation.

6. Code Implementations

Expand the sections below to see the optimal O(1) extra space implementations across different languages.

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        answer = [1] * n
        
        # Step 1: Calculate left (prefix) products
        prefix = 1
        for i in range(n):
            answer[i] = prefix
            prefix *= nums[i]
            
        # Step 2: Calculate right (suffix) products on the fly
        suffix = 1
        for i in range(n - 1, -1, -1):
            answer[i] *= suffix
            suffix *= nums[i]
            
        return answer

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] answer = new int[n];
        
        // Step 1: Calculate left (prefix) products
        int prefix = 1;
        for (int i = 0; i < n; i++) {
            answer[i] = prefix;
            prefix *= nums[i];
        }
        
        // Step 2: Calculate right (suffix) products on the fly
        int suffix = 1;
        for (int i = n - 1; i >= 0; i--) {
            answer[i] *= suffix;
            suffix *= nums[i];
        }
        
        return answer;
    }
}

#include <vector>

class Solution {
public:
    std::vector<int> productExceptSelf(std::vector<int>& nums) {
        int n = nums.size();
        std::vector<int> answer(n, 1);
        
        // Step 1: Calculate left (prefix) products
        int prefix = 1;
        for (int i = 0; i < n; ++i) {
            answer[i] = prefix;
            prefix *= nums[i];
        }
        
        // Step 2: Calculate right (suffix) products on the fly
        int suffix = 1;
        for (int i = n - 1; i >= 0; --i) {
            answer[i] *= suffix;
            suffix *= nums[i];
        }
        
        return answer;
    }
};

7. Conclusion: You Are Ready

Congratulations! You have successfully mastered the Prefix and Suffix technique for Product of Array Except Self! By splitting global dependencies into two unidirectional scans, you bypassed the strict "no division" rule while achieving optimal O(N) time and O(1) extra space. This two-pass prefix/suffix strategy is a foundational mental model that appears frequently in advanced sliding window, subarray, and dynamic programming interview challenges. Keep practicing, and keep optimizing!