Product of Array Except Self — Prefix × Suffix O(n) O(1) [Google, Meta, Amazon]

Problem Statement

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 in O(n) without using division.

Input: [1,2,3,4] → [24,12,8,6]

Intuition
C++ Solution
Java Solution
Python Solution
JavaScript Solution
Complexity: O(n) time, O(1) extra space (output array doesn't count)

Intuition

answer[i] = (product of all elements left of i) × (product of all elements right of i)

Pass 1 (left→right): fill answer[i] with prefix product up to i-1. Pass 2 (right→left): multiply in suffix product using a running variable.

answer[0] = 1
for i = 1 to n-1: answer[i] = answer[i-1] * nums[i-1]

suffix = 1
for i = n-1 downto 0:
    answer[i] *= suffix
    suffix *= nums[i]

C++ Solution

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> ans(n, 1);
        // Left prefix
        for (int i = 1; i < n; i++) ans[i] = ans[i-1] * nums[i-1];
        // Right suffix
        int suffix = 1;
        for (int i = n-1; i >= 0; i--) {
            ans[i] *= suffix;
            suffix *= nums[i];
        }
        return ans;
    }
};

Java Solution

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] ans = new int[n];
        ans[0] = 1;
        for (int i = 1; i < n; i++) ans[i] = ans[i-1] * nums[i-1];
        int suffix = 1;
        for (int i = n-1; i >= 0; i--) { ans[i] *= suffix; suffix *= nums[i]; }
        return ans;
    }
}

Python Solution

def productExceptSelf(nums):
    n = len(nums)
    ans = [1] * n
    for i in range(1, n): ans[i] = ans[i-1] * nums[i-1]
    suffix = 1
    for i in range(n-1, -1, -1):
        ans[i] *= suffix
        suffix *= nums[i]
    return ans

JavaScript Solution

function productExceptSelf(nums) {
    const n = nums.length, ans = new Array(n).fill(1);
    for (let i = 1; i < n; i++) ans[i] = ans[i-1] * nums[i-1];
    let suffix = 1;
    for (let i = n-1; i >= 0; i--) { ans[i] *= suffix; suffix *= nums[i]; }
    return ans;
}

Complexity: O(n) time, O(1) extra space (output array doesn't count)

Follow-up with zeros: Handle arrays with zeros carefully — track count of zeros separately.