238. Product of Array Except Self

#array

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].

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

Space Complexity	Time Complexity
$\text{O}(n)$	$\text{O}(n)$

• 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;
    }
}