# Solution For Product Of Array Except Self

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.

## Step by Step Implementation For Product Of Array Except Self

```public int[] productExceptSelf(int[] nums) {

// The length of the input array
int length = nums.length;

// The left and right arrays have the product of the elements to the left and right of the index, respectively
int[] left = new int[length];
int[] right = new int[length];

// Final answer array to be returned

// First element of left array is always 1
left[0] = 1;

// First element of right array is always 1
right[length - 1] = 1;

// Construct the left array
for (int i = 1; i < length; i++) {
left[i] = nums[i - 1] * left[i - 1];
}

// Construct the right array
for (int j = length - 2; j >= 0; j--) {
right[j] = nums[j + 1] * right[j + 1];
}

for (int k = 0; k < length; k++) {
}

}```
```class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
# The length of the input array
length = len(nums)

# The answer array to be returned

# answer[i] contains the product of all the elements to the left
# Note: for the element at index '0', there are no elements to the left,
# so the answer[0] would be 1
for i in range(1, length):

# answer[i - 1] already contains the product of elements to the left of 'i - 1'
# Simply multiplying it with nums[i - 1] would give the product of all
# elements to the left of index 'i'

# R contains the product of all the elements to the right
# Note: for the element at index 'length - 1', there are no elements to the right,
# so the R would be 1
R = 1;
for i in reversed(range(length)):

# For the index 'i', R would contain the
# product of all elements to the right. We update R accordingly
R *= nums[i]

```/**
* @param {number[]} nums
* @return {number[]}
*/
var productExceptSelf = function(nums) {
// create an empty array with same length as input array
let output = new Array(nums.length);

// fill the output array with 1's
output.fill(1);

// initialize two variables for tracking left side product and right side product
let left = 1;
let right = 1;

// loop through input array from left to right
for (let i = 0; i < nums.length; i++) {
// at each iteration, update left side product and store it in output array
output[i] = left;
// update left side product for next iteration
left *= nums[i];
}

// loop through input array from right to left
for (let j = nums.length - 1; j >= 0; j--) {
// at each iteration, update right side product
right *= nums[j];
// update output array with right side product
output[j] *= right;
}

return output;
};```
```vector productExceptSelf(vector& nums) {
int n = nums.size();
vector res(n);
int left = 1;
for (int i = 0; i < n; ++i) {
if (i > 0)
left = left * nums[i - 1];
res[i] = left;
}
int right = 1;
for (int i = n - 1; i >= 0; --i) {
if (i < n - 1)
right = right * nums[i + 1];
res[i] *= right;
}
return res;
}```
```public int[] ProductExceptSelf(int[] nums) { // The length of the input array
int length = nums.Length;

// The left and right arrays have the product of all the elements to the left and right of the index, respectively
int[] left = new int[length];
int[] right = new int[length];

// Final answer array to be returned

// L[i] contains the product of all the elements to the left
// Note: for the element at index '0', there are no elements to the left, so L[0] would be 1
left[0] = 1;
for (int i = 1; i < length; i++) {
left[i] = nums[i - 1] * left[i - 1];
}

// R[i] contains the product of all the elements to the right
// Note: for the element at index 'length - 1', there are no elements to the right, so R[length - 1] would be 1
right[length - 1] = 1;
for (int i = length - 2; i >= 0; i--) {
right[i] = nums[i + 1] * right[i + 1];
}

for (int i = 0; i < length; i++) {
// For the first element, R[i] would be product except self
// For the last element of the array, product except self would be L[i]
// Else, multiple product of all elements to the left and to the right