Array-1/ProductArraySelf.java at f375544fd106b4f38f26da6731a6c46d6e87741a · super30admin/Array-1 · GitHub

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
// Prefix sum O(n) time, O(n) space
// class Solution {
//     public int[] productExceptSelf(int[] nums) {
//         int n = nums.length;
//         int[] prefix = new int[n];
//         int[] postfix = new int[n];
//         int[] ans = new int[n];

//         prefix[0] = 1;
//         postfix[n-1] = 1;

//         for (int i = 0; i < n; i++) {
//             prefix[i] = prefix[i-1] * nums[i-1];
//         }

//         for (int i = n-2; i >= 0; i--) {
//             postfix[i] = postfix[i+1] * nums[i+1];
//         }

//         for (int i = 0; i < n; i++) {
//             ans[i] = prefix[i] * postfix[i];
//         }

//         return ans;
//     }
// }

// Prefix sum O(n) time, O(1) space
class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] ans = new int[n];

        ans[0] = 1;
        int runningProduct = 1;

        for (int i = 0; i < n; i++) {
            runningProduct = runningProduct * nums[i-1];
            ans[i] = runningProduct;
        }

        runningProduct = 1;
        for (int i = n-2; i >= 0; i--) {
            runningProduct = runningProduct * ans[i+1];
            ans[i] = ans[i] * runningProduct;
        }

        return ans;
    }
}