LeetCode/algorithms/java/productOfArrayExceptSelf.java at main · Lntck/LeetCode · 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
class Solution {
    // 1sr Approach O(n)
    // public int[] productExceptSelf(int[] nums) {
    //     int n = nums.length;
    //     int[] result = new int[n];
    //     int[] leftProduct = new int[n];
    //     int[] rightProduct = new int[n];

    //     leftProduct[0] = 1;
    //     rightProduct[n-1] = 1;


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

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


    //     for (int i=0; i<n; i++) {
    //         result[i] = leftProduct[i] * rightProduct[i];
    //     }

    //     return result;
    // }
    //
    // 2nd Approach O(n)
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];
        result[0] = 1;

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

        int right = 1;
        for (int i=n-1; i>=0; i--) {
            result[i] *= right;
            right *= nums[i];

        }

        return result;
    }
}