LeetCode #238. Product of Array Except Self

1.Solution with division

Time Complexity O(n)

• First loop iterates through all n elements once to calculate the product and count zeros
• Second loop iterates through all n elements once to populate the result array
• Total: O(n) + O(n) = O(n)

Space Complexity

O(1) auxiliary space: Only uses a constant amount of extra variables (zeroCount, product, i).
The space complexity is typically considered O(1) since the output array doesn't count as extra space (it's required by the problem), and no additional space proportional to input size is used.

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

        int zeroCount = 0;
        int product = 1;

        for (int num : nums) {
            if (num == 0)
                zeroCount++;
            else 
                product *= num;
        }

        for (int i = 0; i < n; i++) {
            if (zeroCount > 1)
                result[i] = 0;
            if (zeroCount == 1)
                result[i] = (nums[i] == 0) ? product : 0;
            else 
                result[i] = product / nums[i];
        }

        return result;
    }
}  

2.Solution without division

Time Complexity: O(n)

You do two linear passes over the array:

• Prefix pass (left → right)
• Suffix pass (right → left)

Each element is processed a constant number of times.
O(n) + O(n) = O(n)

Space Complexity: O(1)

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

        // prefix product
        result[0] = 1;
        for (int i = 1; i <nums.length; i++) {
            result[i] = result[i - 1] * nums[i - 1]; 
        }

        // suffix product
        int suffix = 1;
        for (int i = nums.length - 1; i >= 0; i--) {
            result[i] *= suffix;
            suffix *= nums[i];
        }
        return result;    
    }
}