Difficulty: Medium · LeetCode 238

Problem

Return array where answer[i] = product of all elements except nums[i]. Must run O(n) without division.

Examples

Intuition

answer[i] = product_of_all_left × product_of_all_right. Two passes: left to right (prefix), right to left (suffix). Combine into result in O(n) with O(1) extra space.

Optimized Code — Prefix × Suffix

Python

class Solution:
    def productExceptSelf(self, nums: list[int]) -> list[int]:
        n = len(nums)
        res = [1] * n
        prefix = 1
        for i in range(n):
            res[i] = prefix
            prefix *= nums[i]
        suffix = 1
        for i in range(n-1, -1, -1):
            res[i] *= suffix
            suffix *= nums[i]
        return res

C++

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

Java

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

JavaScript

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

Time: O(n) · Space: O(1)*

Takeaway

Pattern: Prefix/Suffix Accumulation — "Everything to the left × everything to the right." Applies to Trapping Rain Water, Max Product Subarray. Avoids division.