c++, O(n) time, O(n * n) space not the best solution but with explanation


  • 0
    L
    // position: 0 1 2 3 4
    // output:     0 0 0 0
    //           1   1 1 1
    //           2 2   2 2  
    //           3 3 3   3     
    //           4 4 4 4 
    //the blank represents 1, and the number represents the number of the position in nums.
    // we could make the 2 triangle matrix for each position, every column could be iterated to get
    // actually, every position is these 2 triangle matrix elements multiplication 
    
    class Solution {
    public:
        vector<int> productExceptSelf(vector<int>& nums) {
             int n = nums.size();
             vector<int> uptri(n, 1), downtri(n, 1), res(n, 1);
             for(int i = 1; i < n; i++){
                 uptri[i] = uptri[i - 1] * nums[i - 1];
                 downtri[n - i - 1] = downtri[n - i] * nums[n - i];
             } 
             for(int i = 0; i < n; i++ ) res[i] = uptri[i] * downtri[i];
             return res;
         }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.