// Product of Array Except Self - https://leetcode.com/problems/product-of-array-except-self/description/

class Solution {
    // Brute Force 
    // Time Complexity: O(n^2)
    // Space Complexity: O(1)
    // Below solution leads to Time Limit Exceeded on LeetCode
    // public int[] productExceptSelf(int[] nums) {
    //     int[] answer = new int[nums.length];
    //     for(int i = 0; i < nums.length; i++) {
    //         int product = 1;
    //         for (int j = 0; j < nums.length; j++) {
    //             if (i != j) {
    //                 product *= nums[j];
    //             }
    //         }

    //         answer[i] = product;
    //     }

    //     return answer;
    // }

    // Ignoring the Division constraint
    // Time Complexity: O(n)
    // Space Complexity: O(1)
    // Below solution doesn't work when input array has 0
    // public int[] productExceptSelf(int[] nums) {
    //     int[] answer = new int[nums.length];
    //     int arrayProduct = 1;
    //     for(int i = 0; i < nums.length; i++) {
    //         arrayProduct *= nums[i];
    //     }

    //     for(int i = 0; i < nums.length; i++) {
    //         if (nums[i] != 0) {
    //             answer[i] = arrayProduct / nums[i];
    //         }
            
    //     }

    //     return answer;
    // }

    // Using Prefix & Suffix products
    // Time Complexity: O(n)
    // Space Complexity: O(n)
    public int[] productExceptSelf(int[] nums) {
        int[] answer = new int[nums.length];

        int[] prefix = new int[nums.length];
        int[] suffix = new int[nums.length];


        // prefixes
        prefix[0] = 1;
        for(int i = 1; i < nums.length; i++) {
            prefix[i] = prefix[i - 1] * nums[i - 1];
        }

        // suffixes
        suffix[nums.length - 1] = 1;
        for(int i = nums.length - 2; i >= 0; i--) {
            suffix[i] = suffix[i + 1] * nums[i + 1];
        }

        for(int i = 0; i < nums.length; i++) {
            answer[i] = prefix[i] * suffix[i];
        }

        return answer;
    }
}