Three different solutions (C++)


  • 0
    T
    /* Stupid O(N^2) algorithm, Time Limit Exceed
    class Solution {
    public:
        vector<int> productExceptSelf(vector<int>& nums) {
            vector<int> res;
      
            for (int i = 0; i < nums.size(); ++i) {
                long product = 1;   
                for (int j = 0; j < nums.size(); ++j) {
                    if ( j != i)
                        product *= nums[j];
                }
                
                res.push_back(product);
            }
            
            return res;
        }
    };
    
    */
    
    /* Good O(N) time and O(N) space algorithm
    class Solution {
    public:
        vector<int> productExceptSelf(vector<int>& nums) {
            vector<int> res;
            int n = nums.size();
            vector<int> forwardProduct(n);
            vector<int> backwardProduct(n);
            forwardProduct[0] = 1;
            backwardProduct[0] = 1;
            
            for(int i = 1; i < nums.size(); ++i) {
                forwardProduct[i] = forwardProduct[i - 1] * nums[i - 1];
                backwardProduct[i] = backwardProduct[i - 1] * nums[n - i];
            } 
        
            for (int j = 0; j < nums.size(); ++j)
                res.push_back(forwardProduct[j] * backwardProduct[n - j - 1]);
           
            return res;
        }
    };*/
    
    /* Very smart algorithm:  O(N) time and O(1) space */
    class Solution {
    public:
        vector<int> productExceptSelf(vector<int>& nums) {
            int n = nums.size();
            vector<int> res(n, 1);
            int forwardProduct = 1;
            int backwardProduct = 1;
            
            for(int i = 0; i < n; ++i) {
                res[i] *= forwardProduct;
                forwardProduct = forwardProduct * nums[i];
                res[n - i - 1] *= backwardProduct;
                backwardProduct = backwardProduct * nums[n - i -1];
            } 
        
           
            return res;
        }
    };
    

Log in to reply
 

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