Product Except Self

Medium

Python

def product(nums):
    n=len(nums); res=[1]*n; l=1
    for i in range(n): res[i]=l; l*=nums[i]
    r=1
    for i in range(n-1,-1,-1): res[i]*=r; r*=nums[i]
    return res

Java

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

Key Insight

[1]*n vs Arrays.fill(). Two-pass technique identical.

Python → Java Differences

[1]*n vs Arrays.fill()
range(n-1,-1,-1) vs i--
Two-pass identical

Python

def product(nums):
    n=len(nums); res=[1]*n; l=1
    for i in range(n): res[i]=l; l*=nums[i]
    r=1
    for i in range(n-1,-1,-1): res[i]*=r; r*=nums[i]
    return res

Java

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

Algorithm Steps

1. Left pass prefix products
2. Right pass suffix products

← Previous All Arrays Next →