C++ 9 lines O(n log n) map, plus stack with binary search


  • 7
    V

    We populate right subtree if numbers are decreasing. If the current number is larger, the portion of the right subtree that is smaller will become a left subtree of the current number, thus making the current number the leaf/smallest in the right subtree.

    0_1514703799976_max_binary_tree.png

    I use map as it provides the convenient insert operation, that returns the position of the inserted element in O (log n).

    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        map<int, TreeNode*> q = { { nums[0], new TreeNode(nums[0]) } };
        for (auto i = 1; i < nums.size(); ++i) {
            auto it_b = q.insert({ nums[i], new TreeNode(nums[i]) });
            if (it_b.first != q.begin()) { // left tree.
                it_b.first->second->left = next(it_b.first, -1)->second;
                q.erase(q.begin(), it_b.first);
            }
            if (next(it_b.first, 1) != q.end()) // right tree.
                next(it_b.first, 1)->second->right = it_b.first->second;
        }
        return q.rbegin()->second;
    }
    

    As pointed out by @Mrsuyi, we can use stack instead of map, as map adds some overhead to maintain internal BST. Below is the solution based on the one proposed by @Mrsuyi, optimized to use the binary search (as our stack will be always sorted).

    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        vector<TreeNode*> s { new TreeNode(nums[0]) };
        for (int i = 1; i < nums.size(); ++i) {
            TreeNode* cur = new TreeNode(nums[i]);
            auto it = upper_bound(s.rbegin(), s.rend(), cur, 
                                  [](const TreeNode* a, const TreeNode* b) { return a->val < b->val; });
            if (it != s.rend()) (*it)->right = cur;
            if (it != s.rbegin()) cur->left = *next(it, -1);
            s.resize(distance(it, s.rend()));
            s.push_back(cur);
        }
        return s.front();
    }
    

  • 1
    M

    Brilliant idea !
    I optimized this solution slightly by using a stack and I hope you don't mind my posting it here
    https://discuss.leetcode.com/topic/98509/c-o-n-solution
    Thanks !


  • 0
    V

    @Mrsuyi good idea to use stack, I was considering it too but it was a little trickier to implement. In your solution, you could use binary search (as your stack is naturally sorted) instead of popping elements one by one. When you find a larger element, you can use vector.resize() to quickly remove all smaller elements. rbegin() and rend() can simplify the logic a bit, as the stack will be sorted in the descending order.

    I added another solution to my answer based on your code, optimized using the binary search.

    It looks like LeetCode OJ does not have a good test case to see the difference, so I ran both algorithms using a large random input, and the version with the binary search was 20% faster.

    My initial algorithm that uses set is several times slower. I am guessing that this is due to the overhead to maintain BST internally.


  • 0
    S

    Can somebody explain this solution in simple words?


  • 0

    Hi, @votrubac, could you please explain what you mean by

    The current number becomes a leaf of the right subtree.

    Isn't the current number the root of the right subtree?


  • 0
    V

    @jianchao.li.fighter said in C++ 9 lines O(n log n) map, plus stack with binary search:

    Hi, @votrubac, could you please explain what you mean by

    The current number becomes a leaf of the right subtree.

    Isn't the current number the root of the right subtree?

    Tried to re-read the description again, and I agree the wording is a bit confusing (will post a picture to clarify).The current number "breaks" the right subtree into two parts; it becomes the leaf of the first part, and the second part becomes it's left subtree.


Log in to reply
 

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