class Solution {
    // O(n)
    public int[] productExceptSelf(int[] nums) {
        int[] result = new int[nums.length];
        
        // Calculate lefts and store in result.
        int prefix = 1;
        for (int i = 0; i < nums.length; i++) {
            result[i] = prefix;
            prefix *= nums[i];
        }
        
        // Calculate rights and the product from the end of the array.
        int postfix = 1;
        for (int i = nums.length - 1; i >= 0; i--) {
            result[i] *= postfix;
            postfix *= nums[i];
        }
        
        return result;
    }
}