Product of array except self

Given an array of integer called nums, return the array such that the element at position i is equal to the product of all elements of nums except nums[i].

To solve this problem without using the division operation and in O(n) time complexity, we can utilize the concept of prefix and suffix products.

The idea is to calculate the product of all elements to the left of each element in the input array and store it in a separate array. Then, calculate the product of all elements to the right of each element and multiply it with the corresponding element in the left product array. This will give us the desired product except for the current element.

Algorithm

1. Initialize an empty array called answer with the same length as the input nums array.
2. Initialize a variable product to 1.
3. Iterate through the nums array from left to right.
4. Set answer[i] to the current value of product.
5. Update the product by multiplying it with nums[i].
6. Reset product to 1.
7. Iterate through the nums array from right to left.
8. Update answer[i] by multiplying it with the current value of product.
9. Update the product by multiplying it with nums[i].
10. Return the answer array.

Complexity

• Time Complexity: O(N), where N is the size of the Array
• Space Complexity: O(N), where N is the size of the Array

Code

## Java Code

import java.util.Arrays;

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

        // Calculate the product of all elements to the left
        int leftProduct = 1;
        for (int i = 0; i < length; i++) {
            result[i] = leftProduct;
            leftProduct *= nums[i];
        }

        // Calculate the product of all elements to the right and combine with left product
        int rightProduct = 1;
        for (int i = length - 1; i >= 0; i--) {
            result[i] *= rightProduct;
            rightProduct *= nums[i];
        }

        return result;
    }

    public static void main(String[] args) {
        // Example usage
        int[] nums = {1, 2, 3, 4};
        int[] result = productExceptSelf(nums);

        // Print the result
        System.out.print("Product except self: ");
        System.out.println(Arrays.toString(result));
    }
}

Output

Product except self: [24, 12, 8, 6]