Product of Array Except Self

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].

The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

You must write an algorithm that runs in O(n) time and without using the division operation.

Example 1:

Input: nums = [1,2,3,4] Output: [24,12,8,6]

Example 2:

Input: nums = [-1,1,0,-3,3] Output: [0,0,9,0,0]

Constraints:

• 2 <= nums.length <= 105
• -30 <= nums[i] <= 30
• The input is generated such that answer[i] is guaranteed to fit in a 32-bit integer.

Follow up: Can you solve the problem in O(1) extra space complexity? (The output array does not count as extra space for space complexity analysis.)

Approach: Prefix and Suffix Products (Optimal Solution)

Algorithm

1. Create an answer array to store the result
2. First pass (left to right): store the product of all elements to the left of each index in answer[i]
3. Second pass (right to left): multiply answer[i] by the product of all elements to the right of each index, tracking the running right product in a variable
4. Return the answer array

Key Insight

Instead of using division, compute the product of all elements except nums[i] as leftProduct[i] * rightProduct[i]. By reusing the answer array for the left products and a running variable for the right products, we achieve O(1) extra space.

Time & Space Complexity

• Time Complexity: O(n) - two passes through the array
• Space Complexity: O(1) - the output array does not count as extra space

Java Implementation

public class ProductOfArrayExceptSelf {

    /**
     * Compute an array where answer[i] is the product of all elements except nums[i].
     * @param nums Input array
     * @return Array of products of all elements except self
     */
    public static int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] answer = new int[n];

        // First pass: left products
        // answer[i] = product of all elements to the left of i
        answer[0] = 1;
        for (int i = 1; i < n; i++) {
            answer[i] = answer[i - 1] * nums[i - 1];
        }

        // Second pass: multiply by right products
        // rightProduct = product of all elements to the right of i
        int rightProduct = 1;
        for (int i = n - 1; i >= 0; i--) {
            answer[i] *= rightProduct;
            rightProduct *= nums[i];
        }

        return answer;
    }

    // Helper method to print array
    public static void printArray(int[] arr) {
        System.out.print("[");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]);
            if (i < arr.length - 1) {
                System.out.print(", ");
            }
        }
        System.out.println("]");
    }

    // Test method
    public static void main(String[] args) {
        // Test case 1
        int[] nums1 = {1, 2, 3, 4};
        System.out.print("Input: ");
        printArray(nums1);
        System.out.print("Output: ");
        printArray(productExceptSelf(nums1)); // Expected: [24, 12, 8, 6]

        // Test case 2
        int[] nums2 = {-1, 1, 0, -3, 3};
        System.out.print("Input: ");
        printArray(nums2);
        System.out.print("Output: ");
        printArray(productExceptSelf(nums2)); // Expected: [0, 0, 9, 0, 0]
    }
}

Example Walkthrough

For nums = [1,2,3,4]:

First pass (left products):

1. i=0: answer[0]=1
2. i=1: answer[1]=1×1=1
3. i=2: answer[2]=1×2=2
4. i=3: answer[3]=2×3=6

answer = [1, 1, 2, 6]

Second pass (right products):

1. i=3: rightProduct=1, answer[3]=6×1=6, rightProduct=1×4=4
2. i=2: answer[2]=2×4=8, rightProduct=4×3=12
3. i=1: answer[1]=1×12=12, rightProduct=12×2=24
4. i=0: answer[0]=1×24=24, rightProduct=24×1=24

answer = [24, 12, 8, 6]

Alternative Approach with Division (Not Allowed)

public static int[] productExceptSelfDivision(int[] nums) {
    int n = nums.length;
    int[] answer = new int[n];
    int totalProduct = 1;
    int zeroCount = 0;

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

    for (int i = 0; i < n; i++) {
        if (zeroCount > 1) {
            answer[i] = 0;
        } else if (zeroCount == 1 && nums[i] != 0) {
            answer[i] = 0;
        } else if (zeroCount == 1 && nums[i] == 0) {
            answer[i] = totalProduct;
        } else {
            answer[i] = totalProduct / nums[i];
        }
    }

    return answer;
}

This approach uses division and handles zeros, but the problem explicitly forbids using the division operation.

Key Insights

1. No Division: Uses prefix and suffix products instead of division to avoid integer overflow and follow the problem constraint
2. Two Passes: One pass for left products, one pass for right products
3. O(1) Extra Space: Reuses the output array for left products and a single variable for right products
4. Zero Handling: Works correctly with zeros without special case handling

The prefix/suffix product approach is the optimal solution for this problem, providing linear time complexity with constant extra space.