Blind 75 - Product of Array Except Self

Link

Learning From

NeetCode

Asked at

19 times.

AmazonAppleAsanaBloombergMicrosoftAdobeAmerican ExpressLyftOracleFacebookUberWalmart Global TechYahooGoogleSalesforceDE ShawPaypalGoldman SachsGrouponQualtricsTikTokZillowIBM

Source

Video

https://youtu.be/7KHKFqLPMbs

Problem and Constraints

All Approaches and Explanations in English

O(n) time complexity. O(1) space complexity

loop twice. first right to left while multiplying. then second left to right while multiplying. this can be done in a single array and one extra product variable

Code, if any

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int[] outputArray = new int[nums.length];
        int product=1;
        for(int i = 0; i< nums.length; i++){
            outputArray[i]=product;
            product = product * nums[i];
        }
        product=1;
        for(int i = nums.length-1; i>=0; i--){
            outputArray[i]*=product;
            product*=nums[i];
        }
        return outputArray;
    }
}