LeetCode 238: Product of Array Except Self

Explanation

To solve this problem, we can calculate the product of all elements to the left of each element and the product of all elements to the right of each element separately. Then, we can multiply these two products together to get the final product excluding the current element. This approach avoids using division and runs in O(n) time complexity.

1. Initialize two arrays leftProducts and rightProducts of the same size as the input array nums.
2. Calculate the product of all elements to the left of each element in nums and store it in leftProducts.
3. Calculate the product of all elements to the right of each element in nums and store it in rightProducts.
4. Multiply the corresponding elements in leftProducts and rightProducts to get the final result.

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];
        
        int[] leftProducts = new int[n];
        int[] rightProducts = new int[n];
        
        leftProducts[0] = 1;
        for (int i = 1; i < n; i++) {
            leftProducts[i] = leftProducts[i - 1] * nums[i - 1];
        }
        
        rightProducts[n - 1] = 1;
        for (int i = n - 2; i >= 0; i--) {
            rightProducts[i] = rightProducts[i + 1] * nums[i + 1];
        }
        
        for (int i = 0; i < n; i++) {
            result[i] = leftProducts[i] * rightProducts[i];
        }
        
        return result;
    }
}