Product Of Array Except Self - Leetcode Solution

Problem Statement:

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]

Note: Please solve it without division and in O(n).

Solution:

To solve this problem, we can use two additional arrays to store the product of all elements to the left and right of the current element respectively. Then, we can simply multiply the corresponding elements of these two arrays to get the final result.

Let's take the example of the input [1, 2, 3, 4].

1. Create a new array left of the same size as nums. Initialize left[0] to 1.

2. Iterate from 1 to n-1 and for each index i of nums, compute left[i] as nums[i-1] * left[i-1]. The value of left array after this operation would be [1, 1, 2, 6].

3. Create another new array right of the same size as nums. Initialize right[n-1] to 1.

4. Iterate from n-2 to 0 and for each index i of nums, compute right[i] as nums[i+1] * right[i+1]. The value of left array after this operation would be [24, 12, 4, 1].

5. Create the final output array output of the same size as nums.

6. Iterate from 0 to n-1 and for each index i of nums, compute output[i] as left[i] * right[i]. The value of output array after this operation would be [24, 12, 8, 6].

Here's the Python code for the solution:

def productExceptSelf(nums): n = len(nums) left = [1] * n right = [1] * n

for i in range(1, n):
    left[i] = nums[i-1] * left[i-1]
    
for i in range(n-2, -1, -1):
    right[i] = nums[i+1] * right[i+1]
    
output = [1] * n
for i in range(n):
    output[i] = left[i] * right[i]
    
return output

Time Complexity:

The time complexity of the solution is O(n) as we are iterating through the input array three times, once for left array, once for right array, and once for calculating the output array.

1