[Leetcode] 238. Product of Array Except Self

https://leetcode.com/problems/product-of-array-except-self/description/?envType=study-plan-v2&envId=top-interview-150

initial

i thought of getting product of all ements and dividing each value of the iterating index. The problem is 0, which makes my product 0 and give wrong ans

but if u think, we can sort to 3 cases
1) if there is no 0, we can use that methods
2) if there is 1 0s, then we need to find that index that has value 0 and put 0 as answer for that index.The product should skip multiplying this 0.
3) if there are 2 or more 0s, its just array of 0s

        //  O(N)
        int n = nums.length;
        int countZeroes = 0;
        int indexZero = -1;
        int productWithoutZero = 1;
        
        for(int i = 0 ; i < n ; i++) {
            if(nums[i] == 0) {
                countZeroes++;
                indexZero = i;
            }
            else {
                productWithoutZero *= nums[i];
            }
        }
        
        int [] output = new int [n];
        if(countZeroes == 0) {
            for(int i = 0 ; i < n ; i++) {
                output[i] = productWithoutZero / nums[i];
            }
        }
        else if(countZeroes == 1) {
            output[indexZero] = productWithoutZero;
        }
        return output;

sol

this is actually prefix sum. for index i, we update its value as prefix[i-1] multiplied by arr[i-1]. Why i-1? Cuz we dont want the value at index i since q is asking not to include that value. Same for suffix it is suffix[i+1] with arr[i+1]. Then, multiplying prefix and suffix that excludes the value at index i gives us the ans.

so if [1,2,3,4]
pre=[1, 1, 1x2, 1x2x3]
suf=[1432, ,143,14, 1]

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int pre[] = new int[n];
        int suff[] = new int[n];
        pre[0] = 1;
        suff[n - 1] = 1;
        
        for(int i = 1; i < n; i++) {
            pre[i] = pre[i - 1] * nums[i - 1];
        }
        for(int i = n - 2; i >= 0; i--) {
            suff[i] = suff[i + 1] * nums[i + 1];
        }
        
        int ans[] = new int[n];
        for(int i = 0; i < n; i++) {
            ans[i] = pre[i] * suff[i];
        }
        return ans;
    }
}

to save space eomplexity we can just use 1 array cuz we dont need 2 separate arrays

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int ans[] = new int[n];
        Arrays.fill(ans, 1);
        int curr = 1;
        for(int i = 0; i < n; i++) {
            ans[i] *= curr;
            curr *= nums[i];
        }
        curr = 1;
        for(int i = n - 1; i >= 0; i--) {
            ans[i] *= curr;
            curr *= nums[i];
        }
        return ans;
    }
}

revisited aug 22nd

yep solved it

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] forward = new int[n];
        int[] back = new int[n];
        for(int i=0;i<n;i++){
            if(i==0) forward[i]=nums[i];
            else{
                forward[i]= forward[i-1]*nums[i];
            }
        }
        for(int i=n-1;i>=0;i--){
            if(i==n-1) back[i]=nums[i];
            else{
                back[i]=back[i+1]*nums[i];
            }
        }
        // System.out.println(Arrays.toString(forward));
        // System.out.println(Arrays.toString(back));
        int[] ans = new int[n];
        for(int i=0;i<n;i++){
            if(i==0) ans[i]=back[i+1];
            else if (i==n-1) ans[i]=forward[n-2];
            else{
                ans[i]=forward[i-1]*back[i+1];
            }
        }
        return ans;
    }
}  

complexity

n time
1 space