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...n1]
, 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)$$.