238. Product of Array Except Self

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of numsexcept nums[i].

!!! info Write an algorithm that runs in O(n) time and without using the division operation.

# Intuition

• We need to find the product of all elements before and after the current element.
• We can iterate from end to store the product of all elements till now excluding the self.
  • Then iterate from the start to get the product of all elements till now excluding the self.

# Approach

• Iterate from the end to store the product till now excluding the self in the answer array.
  • Iterate from the start to get the product of all elements till now excluding the self.
  • the current element is product of answer[i] = productTillNowFront * answer[i];

# Complexity

• We iterate over the array twice.
• Extra space is used to store the answer, but as per the question its to be ignored

# Code

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int[] answer = new int[nums.length];
 
        // calculate the product till now from the end
        answer[nums.length - 1] = 1;
        int productTillNow = nums[nums.length - 1];
        
        for (int i = nums.length - 2; i >= 0; --i) {
            answer[i] = productTillNow;
            productTillNow *= nums[i];
        }
 
        // calculate the product till now from the start
        int productTillNowFront = 1;
        for (int i = 0; i < nums.length; ++i) {
            int temp = nums[i];
            answer[i] = productTillNowFront * answer[i];
 
            productTillNowFront *= temp;
        }
        
        return answer;
    }
}