238. Product of Array Except Self

/**

 * 238. Product of Array Except Self

 * Given an array nums of n integers where n > 1,  return an array output such that output[i] is equal to the

 * product of all the elements of nums except nums[i].

 * Example:

 * Input:  [1,2,3,4]

 * Output: [24,12,8,6]

 * Constraint: It’s guaranteed that the product of the elements of any prefix or suffix of the array

 * (including the whole array) fits in a 32 bit integer.

*/

See the solution to the problem on github here: https://github.com/zcoderz/leetcode/blob/main/src/main/java/frequent/medium/ProductArrayExceptSelf.java

The algorithm is rather straightforward; I have included the problem here since it’s a common interview question.

The algorithm is:

  1. Create an array that stores the product of array one left of the current index
  2. Loop from the right most index to left
    1. Create a variable right product that signifies product of array to right of current index
    1. Multiply the array value (out[i]) of the array created in step 1 above with the right product

Update the right product with current array value as you iterate left

Here is the code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int[] productExceptSelf(int[] nums) {
    int [] out = new int[nums.length];
    int product = 1;
    //save product one left of the given index in out
    for (int i =0; i < nums.length; i++) {
        out[i] = product;
        product *= nums[i];
    }
    //iterate  over product from right
    int rightProduct = 1;
    for (int i =out.length-1; i > -1; i--) {
        out[i] = out[i] * rightProduct;
        rightProduct = nums[i] * rightProduct;
    }
    return out;
}