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

        // Step-1 calculate prefix product of each element
        int[] prefix = new int[n];
        prefix[0] = 1;

        int product = nums[0];
        for(int i=1;i<n;i++)
        {
            prefix[i] = product;
            product = product*nums[i];
        }

        // Step-2 calculate suffix product of each element
        int[] suffix = new int[n];
        suffix[n-1] = 1;
        product = nums[n-1];
        for(int i=n-2;i>=0;i--)
        {
            suffix[i] = product;
            product = product*nums[i];
        }

        for(int i=0;i<n;i++)
        {
            arr[i] = prefix[i]*suffix[i];
        }
        return arr;
    }
}