# Solution by ccwei

• #### Approach #0

If there's no restriction on solving it without division, a way to solve the problem is to compute a product of all `nums[i]` as `totalProduct`, and then `output[i] = totalProduct/nums[i]` to exclude `nums[i]`. However, we need to be careful when `nums[i] == 0`, also the problem explicitly prohibits the use of division, so this solution doesn't solve the problem according to the problem description.

#### Approach #1 Brute Force [Time Limit Exceeded]

The naive approach is to simply follow what the problem asks as to do. For all index `i`, loop through the entire array to calculate the product and only skips index `i` for that iteration to exclude self.

Approach #1 Naive approach [Time Limit Exceeded]

C#

``````public class Solution {
public int[] ProductExceptSelf(int[] nums) {
int[] result = new int[nums.Length];

for(int i = 0; i < nums.Length; i++) {
int product = 1;
for(int j = 0; j < nums.Length; j++) {
if(j != i) { // exclude self
product *= nums[j];
}
}
result[i] = product;
}

return result;
}
}
``````

Complexity Analysis

• Time complexity : \$\$O(n^2)\$\$. There are two loops nested and each with \$\$O(n)\$\$ running time

• Space complexity : \$\$O(1)\$\$. We only use extra constant space for `product` variable.

#### Approach #2 Two product arrays [Accepted]

Algorithm

We can keep two arrays, one is `productFromLeft` where `productFromLeft[i]` contains the product of `nums[0...i]`, i.e. `productFromLeft[i] = nums[0] * nums[1] * nums[2] * .... nums[i]`. Another one is similar but contains all the products from the right hand side, where `productFromRight[i]` contains the product of `nums[i...n-1]`, i.e. `productFromRight[i] = nums[i] * nums[i + 1] * nums[i + 2] * .... nums[n - 1]`.

Given array of `productFromLeft` and `productFromRight`, we can calucate `output[i] = productFromLeft[i - 1] * productFromRight[i + 1]`, which is `nums[0] * nums[1] * ... nums[i - 1] * nums[i + 1] * nums[i + 2] * ... nums[n - 1]`.

C#

``````public class Solution {
public int[] ProductExceptSelf(int[] nums) {
int n = nums.Length;

// Process edge cases first
if(n <= 1) {
return new int[0];
}

int[] productFromLeft = new int[nums.Length];
int[] productFromRight = new int[nums.Length];

// Populate productFromLeft, O(n) time, O(n) space
int product = 1;
for(int i = 0; i < n; i++) {
product *= nums[i];
productFromLeft[i] = product;
}

// Populate productFromRight, O(n) time, O(n) space
product = 1;
for(int i = n - 1; i >= 0; i--) {
product *= nums[i];
productFromRight[i] = product;
}

int[] output = new int[n];

// Special case boundary indices to avoid index out of range issues
output[0] = productFromRight[1];
output[n - 1] = productFromLeft[n - 2];

// Populate all other output[i]
for(int i = 1; i < n - 1; i++) {
output[i] = productFromLeft[i - 1] * productFromRight[i + 1];
}

return output;
}
}
``````

Complexity Analysis

• Time complexity : \$\$O(3n) = O(n)\$\$.

• Space complexity : \$\$O(2n) = O(n)\$\$.

#### Approach #3 Two passes use output array as temp memory [Accepted]

Algorithm

To further optimize the space complexity, as the hint suggested, we can use the output array as the temporary storage for interim calculation result. Similar idea of Approach#2, we are going to scan the input array twice, first time from the left and second time from the right.

The first time we scan it from left, we are going to calculate `output[i]` as product of `nums[0..i - 1]`, i.e. `output[i] = nums[0] * nums[1] * ... nums[i - 1]`, where `output[0] = 1`. As we scan it from the left, we can easily calculate `output[i] = output[i - 1] * nums[i - 1]` because `output[i - 1] = nums[0] * nums[1] * ... nums[i - 2]`.

The second pass we scan it from right, and we are trying to calculate `output[i]` as the final result, which means `output[i] = nums[0] * nums[1] * ... nums[i - 1] * nums[i + 1] * nums[i + 2] * ... nums[n - 1]`, in the first pass, we already calculate `output[i] = nums[0] * nums[1] * ... nums[i - 1]`, so we only need to focus on how to calculate `nums[i + 1] * nums[i + 2] * ... nums[n - 1]`. We can acheive this by keeping an `product` variable similar to the second pass in Approach #2 to keep track of the "product from right", i.e. when index = `i`, `product = nums[i + 1] * nums[i + 2] * ... nums[n - 1]`. So when the loop arrives at index `i`, we can calulcate `output[i] = output[i] * product` to get the final result for index `i`.

C#

``````public class Solution {
public int[] ProductExceptSelf(int[] nums) {
int n = nums.Length;
int[] output = new int[n];

// First pass, calculate output[i] = nums[0] * nums[1] * ... nums[i - 1]
output[0] = 1;
for (int i = 1; i < n; i++) {
output[i] = output[i - 1] * nums[i - 1];
}

// Second pass, calculate output[i] = nums[0] * nums[1] * ... nums[i - 1] * nums[i + 1] * nums[i + 2] * ... nums[n - 1]
int product = 1;  // Special case when i = n - 1, product = 1 since it's the right most element.
for (int i = n - 1; i >= 0; i--) {
output[i] *= product; // product = nums[i + 1] * nums[i + 2] * ... nums[n - 1]
product *= nums[i];
}
return output;
}
}
``````

Complexity Analysis

• Time complexity : \$\$O(2n) = O(n)\$\$.

• Space complexity : \$\$O(1)\$\$.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.