Array-1/Leetcode_238.java at a0b198a86c76628629a9d93d6251b533c15cf496 · 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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
//way1
//linear-o(n^2)
class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n=nums.length;

        int[] ans=new int[n];

        for(int i=0;i<n;i++){
            int p=1;
            for(int j=0;j<n;j++){
                if(i!=j){
                    p*=nums[j];
                }
            }
            ans[i]=p;
        }

        return ans;
    }
}

//way2
//for every index:
//identify left product--leftproduct array
//identify right product--right product array
//multiply leftproduct and right product
//TC: O(3n)--> 3 constant; SC: O(n)
class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n=nums.length;

        //left product array
        int[] leftp=new int[n];
        leftp[0]=1;
        int p=1;

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

        //right product array
        int[] rightp=new int[n];
        rightp[n-1]=1;
        p=1;

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

        //product at every place
        int[] ans=new int[n];

        for(int i=0;i<n;i++){
            ans[i]=(leftp[i]*rightp[i]);
        }

        return ans;
    }
}

//way3
//for every index:
//identify left product--leftproduct array
//identify right product--right product array
//multiply leftproduct and right product
//TC: O(2n)--> 2 constant; SC: O(n)
class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n=nums.length;

        //left product array
        int[] leftp=new int[n];
        leftp[0]=1;
        int p=1;

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

        //right product array--instead of this, let's go with a constant product variable
        // int[] rightp=new int[n];
        // rightp[n-1]=1;
        // p=1;

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

        //product at every place
        int[] ans=new int[n];
        int pd=1;
        ans[n-1]=leftp[n-1];

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

        return ans;
    }
}