238. Product of Array Except Self

Given an array of n integers where n > 1, nums, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Solve it without division and in O(n).

For example, given [1,2,3,4], return [24,12,8,6].

Follow up:
Could you solve it with constant space complexity? (Note: The output array does not count as extra space for the purpose of space complexity analysis.)

Solution:

Intuitive way, use an array A to track all the products from starting index to current position. Use another array B to maintain all the products from ending index to current position. 

For result array res[i]= A[i-1]* B[i+1].

While we are asked to solve it without using extra space, so the idea is use the result array as array A. Update result array when we calculate product from ending index to current position. 

So res[i]=res[i-1] * products(ending-> i+1) in the second iteration.

 public int[] productExceptSelf(int[] nums) {  
     int n=nums.length;  
     int[] res=new int[n];      
     res[0]=nums[0];  
     for(int i=1;i<nums.length-1;i++){  
       res[i]=res[i-1]*nums[i];  
     }  
     int pro=1;  
     for(int i=n-1;i>=1;i--){  
       res[i]=res[i-1]*pro;  
       pro*=nums[i];  
     }  
     res[0]=pro;  
     return res;  
   }