Product of Array Except Self - LeetCode Daily Challenge

Problem Statement

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].

The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

You must write an algorithm that runs in O(n) time and without using the division operation.

Example 1

Input: nums = [1,2,3,4]
Output: [24,12,8,6]

Example 2

Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]

Try here before watching the video.

Video Explanation

Java Code

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

        int rightProduct = 1;
        for(int i = nums.length - 1; i >= 0; i--) {
            leftProduct[i] = leftProduct[i] * rightProduct;
            rightProduct = rightProduct * nums[i];
        }

        return leftProduct;
    }
}

C++ Code

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        vector<int> leftProduct(nums.size());
        leftProduct[0] = 1;
        for(int i = 1; i < nums.size(); i++) {
            leftProduct[i] = leftProduct[i - 1] * nums[i - 1];
        }

        int rightProduct = 1;
        for(int i = nums.size() - 1; i >= 0; i--) {
            leftProduct[i] *= rightProduct;
            rightProduct *= nums[i];
        }

        return leftProduct;
    }
};

Python Code

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        left_product = [0] * len(nums)
        left_product[0] = 1
        for i in range(1, len(nums)):
            left_product[i] = left_product[i - 1] * nums[i - 1]

        right_product = 1
        for i in range(len(nums) - 1, -1, -1):
            left_product[i] *= right_product
            right_product *= nums[i]

        return left_product

Javascript Code

var productExceptSelf = function(nums) {
    const leftProduct = new Array(nums.length).fill(0);
    leftProduct[0] = 1;
    for(let i = 1; i < nums.length; i++) {
        leftProduct[i] = leftProduct[i - 1] * nums[i - 1];
    }

    let rightProduct = 1;
    for(let i = nums.length - 1; i >= 0; i--) {
        leftProduct[i] *= rightProduct;
        rightProduct *= nums[i];
    }

    return leftProduct;
};

Go Code

func productExceptSelf(nums []int) []int {
    leftProduct := make([]int, len(nums))
    leftProduct[0] = 1
    for i := 1; i < len(nums); i++ {
        leftProduct[i] = leftProduct[i-1] * nums[i-1]
    }

    rightProduct := 1
    for i := len(nums) - 1; i >= 0; i-- {
        leftProduct[i] *= rightProduct
        rightProduct *= nums[i]
    }

    return leftProduct
}

Complexity Analysis

Time Complexity: O(N), we are iterating nums array twice.
Space Complexity: O(1), we are not taking any extra space except the leftProduct array which is an answer array itself.