Mind palace

some thoughts

0%

238. Product of Array Except Self

Posted on Edited on In Disqus:
Symbols count in article: 1.3k Reading time ≈ 1 mins.

O(n) time O(1) space
input: 1 2 3 4
res: 1 1 1 1
-->

1
2
3
4
5
6
1 2 3 4
-------
1 1 1 1
  1 1 1
    2 2
      3

<–

1
2
3
4
5
6
1 2 3 4
-------
1 1 1 1
4 1 1 1
3 4 2 2
2 3 4 3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> res(n, 1);
        for (int i = 1; i < n; ++i) {
            res[i] = res[i - 1] * nums[i - 1];
        }
        for (int i = n - 1, p = 1; i >= 0; p *= nums[i--]) {
            res[i] *= p;
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> res(n, 1);
        for (int i = 0, p = 1; i < n; p *= nums[i++]) {
            res[i] *= p;
        }
        for (int i = n - 1, p = 1; i >= 0; p *= nums[i--]) {
            res[i] *= p;
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> res(n, 1);
        for (int i = 1, p = nums[i - 1]; i < n; p *= nums[i++]) {
            res[i] *= p;
        }
        for (int i = n - 2, p = nums[i + 1]; i >= 0; p *= nums[i--]) {
            res[i] *= p;
        }
        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 n = nums.size();
        vector<int> res(n, 1);
        int p = 1;
        for (int i = 1; i < n; ++i) {
            p *= nums[i - 1];
            res[i] = p;
        }
        p = 1;
        for (int i = n - 2; i >= 0; --i) {
            p *= nums[i + 1];
            res[i] *= p;
        }
        return res;
    }
};