C++ why insert() is much slower than push_back() + reverse()


  • 0
    Z
    class Solution {
    public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        //return solution1(root); 
        return solution2(root);   
    }
    private:
    vector<vector<int>> v;
    vector<vector<int>> solution1(TreeNode *root){
        subSol2(root, 0);
        return v;
    }
    void subSol1(TreeNode *root, int depth){
        if(!root) return;
        if(v.size() <= depth) v.insert(v.begin(), vector<int>());
        v[v.size() - 1 - depth].push_back(root->val);
        subSol1(root->left, depth + 1);
        subSol1(root->right, depth + 1);
    vector<vector<int>> solution2(TreeNode *root){
        subSol2(root, 0);
        reverse(v.begin(), v.end());
        return v;
    }
    void subSol2(TreeNode *root, int depth){
        if(!root) return;
        if(v.size() <= depth) v.push_back(vector<int>());
        v[depth].push_back(root->val);
        subSol2(root->left, depth + 1);
        subSol2(root->right, depth + 1);
    }
    };
    

    solution1 takes up to 56ms but solution2 only uses 8 ms. Why insert() is so much slower than push_back() + reverse function?


  • -1
    X

    /**

    • Definition for a binary tree node.

    • struct TreeNode {

    • int val;
      
    • TreeNode *left;
      
    • TreeNode *right;
      
    • TreeNode(int x) : val(x), left(NULL), right(NULL) {}
      
    • };
      /
      class Solution {
      public:
      vector<vector<int>> levelOrderBottom(TreeNode
      root) {
      vector<vector<int>> res;
      if(!root) return res;
      vector<TreeNode*> nodes;
      nodes.push_back(root);

       while(!nodes.empty())
       {
           res.push_back(std::vector<int>());
           vector<TreeNode*> tmp;
           for(int i = 0 ; i < nodes.size() ; ++i)
           {
               res.back().push_back(nodes[i]->val);
               if(nodes[i]->left)
               tmp.push_back(nodes[i]->left);
               if(nodes[i]->right)
               tmp.push_back(nodes[i]->right);
           }
           tmp.swap(nodes);
       }
       
       for(int i = 0 ; i < res.size()/2 ; ++i)
       {
           res[i].swap(res[res.size() - 1 - i]);
       }
      

      }
      };


  • 0
    Z

    sorry, I don't get your point. can you please explain a little bit?


  • 0
    G

    I have same problem, can anybody explian why?


  • 0
    G

    I have same problem, can anybody explian why?


  • 0

    Read documentation for insert and push_back?

    Inserting at the start takes linear time, appending averages constant time.


  • 2

    insert at the beginning of vector will shift all the subsequent elements, so insert N times, it takes O(N^2) time complexity. However, append to the end, insert N times, the amortized time complexity is O(N) and reverse will take O(N) as well.


Log in to reply
 

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