Product of Array Except Self medium

Problem Statement

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] Explanation: The product of all the elements except itself. - For nums[0] = 1, the product is 2 * 3 * 4 = 24. - For nums[1] = 2, the product is 1 * 3 * 4 = 12. - For nums[2] = 3, the product is 1 * 2 * 4 = 8. - For nums[3] = 4, the product is 1 * 2 * 3 = 6.

Example 2:

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

Steps

The core idea is to calculate the product of elements to the left and right of each index separately, then combine them. We avoid division by doing this in two passes.

1. First Pass (Left to Right): Create an array left where left[i] stores the product of all numbers to the left of nums[i]. left[0] will be 1 (since there are no elements to its left).

2. Second Pass (Right to Left): Create a variable rightProduct initialized to 1. Iterate through nums from right to left. In each iteration, multiply rightProduct by nums[i] and store the result in rightProduct. Update answer[i] by multiplying left[i] with rightProduct.

Explanation

The algorithm efficiently calculates the product of elements excluding the current element without using division. The use of two passes ensures that we consider both the left and right products. The rightProduct variable dynamically keeps track of the product of elements to the right.

Code

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] answer = new int[n];
        int[] left = new int[n];
        
        //First Pass: Left Product
        left[0] = 1;
        for(int i=1; i<n; i++){
            left[i] = left[i-1] * nums[i-1];
        }
        
        //Second Pass: Right Product
        int rightProduct = 1;
        for(int i=n-1; i>=0; i--){
            answer[i] = left[i] * rightProduct;
            rightProduct *= nums[i];
        }
        
        return answer;
    }
}

Complexity

• Time Complexity: O(n) - We iterate through the array twice.
• Space Complexity: O(n) - We use an extra array left of size n. We could potentially optimize this to O(1) space by directly modifying the input array and using a temporary variable, but the problem description expects an array to be returned.