C++ HashMap O(n) 6ms


  • 0
    B

    we use a 2 levels HashMap, the first level key is level, the second level key is position in its level, and the value is a pair, whose left is the sum value from root to current node and right is a flag indicates if the node has child (leaf node or not).

    for each number in input, we find its parent node, mark it as not leaf, and add its value to current node, so that each leaf node contains value sum from root to the leaf.

    in the end, we traverse the HashMap to sum up the value of all leaf node.

    class Solution {
    public:
        int pathSum(vector<int>& nums) {
            unordered_map<int,unordered_map<int, pair<int,int>>>pool;
            pool[0][0] = make_pair(0,0);
            for(auto & e : nums)
            {
                int lvl = e/100;
                int pos = e%100/10;
                pool[lvl-1][(pos-1)/2].second = 0;
                pool[lvl][pos-1] = make_pair(e%10 + pool[lvl-1][(pos-1)/2].first,1);
            }
            int ans = 0;
            for(auto & e : pool)
                for(auto & f : e.second)
                    ans += f.second.first * f.second.second;
            return ans;
        }
    };

Log in to reply
 

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