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]

Problem link: Product of Array Except Self

Solution:

Let’s start with a brute-force solution.

public int[] productExceptSelf(int[] nums) {
    int[] arr = new int[nums.length];
    for(int i = 0; i < nums.length; i++) {
        int mul = 1;
        for (int j = 0; j < nums.length; j++) {
            if(i == j) {
                continue;
            }
            mul *= nums[j];
        }
        arr[i] = mul;
    }
    return arr;
}

Clearly, this is not an efficient solution and the time complexity for this solution is O(n²)

We can improve the implementation using the help of division. We can get the total multiplication value and for each element we divide the item.

public int[] productExceptSelf(int[] nums) {
    int mul = 1;
    for(int i = 0; i < nums.length; i++) {
        mul *= nums[i];
    }
    
    for (int i = 0; i < nums.length; i++) {
        nums[i] = mul / nums[i];
    }
    return nums;
}