LeetCode #238. Product of Array Except Self

Source: Dev.to

Solution with division

Time Complexity: O(n) – two linear passes over the array.
Space Complexity: O(1) auxiliary space (only a few extra variables).

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

        int zeroCount = 0;
        int product = 1;

        // First pass: compute product of non‑zero elements and count zeros
        for (int num : nums) {
            if (num == 0)
                zeroCount++;
            else
                product *= num;
        }

        // Second pass: fill the result array based on zero count
        for (int i = 0; i < n; i++) {
            if (zeroCount > 1) {
                result[i] = 0;
            } else if (zeroCount == 1) {
                result[i] = (nums[i] == 0) ? product : 0;
            } else {
                result[i] = product / nums[i];
            }
        }

        return result;
    }
}

Two‑pass solution (without division)

This approach computes the product of all elements except the current one by using prefix and suffix products.

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

        // Prefix product: result[i] holds product of all elements to the left of i
        result[0] = 1;
        for (int i = 1; i < nums.length; i++) {
            result[i] = result[i - 1] * nums[i - 1];
        }

        // Suffix product: multiply by product of elements to the right of i
        int suffix = 1;
        for (int i = nums.length - 1; i >= 0; i--) {
            result[i] *= suffix;
            suffix *= nums[i];
        }

        return result;
    }
}