Similar Problems
Similar Problems not available
Product Of Array Except Self  Leetcode Solution
LeetCode: Product Of Array Except Self Leetcode Solution
Difficulty: Medium
Topics: prefixsum array
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].

Create a new array
left
of the same size asnums
. Initializeleft[0]
to 1. 
Iterate from 1 to n1 and for each index i of nums, compute
left[i]
asnums[i1] * left[i1]
. The value ofleft
array after this operation would be [1, 1, 2, 6]. 
Create another new array
right
of the same size asnums
. Initializeright[n1]
to 1. 
Iterate from n2 to 0 and for each index i of nums, compute
right[i]
asnums[i+1] * right[i+1]
. The value ofleft
array after this operation would be [24, 12, 4, 1]. 
Create the final output array
output
of the same size asnums
. 
Iterate from 0 to n1 and for each index i of nums, compute
output[i]
asleft[i] * right[i]
. The value ofoutput
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[i1] * left[i1]
for i in range(n2, 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.
Product Of Array Except Self Solution Code
1