238. Product of Array Except Self

Problem

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]. You must do this without using division and in O(n) time.

Explanation

First pass: double loops

I first multiplied every combination with two nested loops, skipping the current index. This works but costs O(n^2) time.

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];
 
        for (int i = 0; i < n; i++) {
            int product = 1;
            for (int j = 0; j < n; j++) {
                if (j != i) product *= nums[j];
            }
            result[i] = product;
        }
 
        return result;
    }
}

Final pass: prefix * suffix

To reach O(n), I precompute prefix products from the left and suffix products from the right in one output array. First loop stores the product of everything to the left of each index. Second loop walks backward, multiplying by a running suffix product so each position ends up with left * right. This keeps extra space to O(1) beyond the output.

Time: O(n)
Space: O(1) extra (output excluded)

Solution