Product of Array Except Self

Problem

Given an array nums, return an array answer where answer[i] is the product of all elements of nums except nums[i]. Must run in O(n) without using division.

Constraints

• 2 ≤ nums.length ≤ 10⁵
• −30 ≤ nums[i] ≤ 30
• product of any prefix/suffix fits in int

Approach — Core Patterns

This is a Core Patterns problem. The idea: pick the data structure best matched to the constraints and solve it in one clean pass. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: see the walkthrough below.

Solution code

Python

class Solution:
    def productExceptSelf(self, nums):
        n = len(nums)
        res = [1] * n
        pre = 1
        for i in range(n):
            res[i] = pre
            pre *= nums[i]
        suf = 1
        for i in range(n - 1, -1, -1):
            res[i] *= suf
            suf *= nums[i]
        return res

Java

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

        // First pass: result[i] = product of everything LEFT of i.
        result[0] = 1;
        for (int i = 1; i < n; i++) {
            result[i] = result[i - 1] * nums[i - 1];
        }

        // Second pass: multiply in the running product of everything RIGHT of i.
        int rightProduct = 1;
        for (int i = n - 1; i >= 0; i--) {
            result[i] *= rightProduct;
            rightProduct *= nums[i];
        }
        return result;
    }
}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.