Problem description:

Given an array of n integers where n > 1, nums, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Solve it without division and in O(n).

For example, given [1,2,3,4], return [24,12,8,6].

Follow up:
Could you solve it with constant space complexity? (Note: The output array does not count as extra space for the purpose of space complexity analysis.)

Solution:

Given numbers [2, 3, 4, 5], regarding the third number 4, the product of array except 4 is 2*3*5 which consists of two parts: left 2*3 and right 5. The product is left*right. We can get lefts and rights:

1
2
3
Numbers:     2    3    4     5
Lefts:            2  2*3 2*3*4
Rights:  3*4*5  4*5    5

Let’s fill the empty with 1:

1
2
3
Numbers:     2    3    4     5
Lefts:       1    2  2*3 2*3*4
Rights:  3*4*5  4*5    5     1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        res = [1]*n
        
        for i in range(1, n):
            res[i] = res[i-1]*nums[i-1]
        
        right = 1
        for i in range(n-1, -1, -1):
            res[i] = right*res[i]
            right *= nums[i]

        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
        int length = nums.size();
        vector<int> res(length, 1);
        for(int i= 1; i< length; i++){
            res[i] = res[i-1]*nums[i-1];
        }
        
        int right= 1;
        for(int i= length-1; i>=0; i--){
            res[i]*= right;
            right*= nums[i];
        }
        return res;
        
    }
};

second time:

based on the previous thought, but modify the code to make it more intuitive.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/*

        3   4   5   6
left=1 1*1  
        -> 1*3  
            ->3*4  
                -> 3*4*5

        3   4   5   6
                  1*1  right=1
              1*6 <-
          5*6  <-
      4*5*6  <-
      
do same work, can use one for loop
      
*/
class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int length = nums.size();
        vector<int> res(length, 1);
        int left= 1, right= 1;;
        
        for(int i= 0, j= length-1; i< length; i++, j--){
            res[i]*= left;
            left*= nums[i];
            res[j]*= right;
            right*= nums[j];
        }
        return res;
    }
};

time: O(n)

Third time

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        //use two array separately start from 1 and n-2
        int n= nums.size();
        vector<int> res(n, 1);
        
        for(int i= 1; i< n; i++)
            res[i]= res[i-1]*nums[i-1];
        
        int right= 1;
        for(int i= n-2; i>= 0; i--){
            right*= nums[i+1];
            res[i]*= right;
        }
        
        return res;
    }
};

reference: