share my fast C++ solution using std::map (99~100%, 40+ ms)


  • 1

    This is not a new algorithm, just a performance-aware implementation.

    I have tried 2 versions, binary min heap and simply std::map; surprisingly using std::map brings more performance gain rather than binary heap (60+ ms).

    I added my comment in the codes, and here I am pointing out some effort I have done.

    1. Instead of using another new matrix to record the node traversal, I abuse the original input height map.
    2. There are quite a few times that the newly inserted node has the same height of the current one; in this case my implementation make new insertion in constant time.
    3. (Minor) I found the corner of the height map is irrelevant, so I don't put them into the std::map initially.

    The code:

    class Solution {
    public:
        int trapRainWater(vector<vector<int>>& heightMap) {
            int w = heightMap.size();
            
            //check the dimension...otherwise gotta do boundary checking in the next step anyway
            if(w<=2)return 0;
            int h = heightMap[0].size();
            if(h <=2)return 0;
            
            map<int,vector<pair<int,int>>> m;
            //initiate the map : push the posisions on the 4 edges except corners
            //abuse the input :P
            //setting heightMap[x][y] to 0 means the node is in the map or traversed
            for(int i=1;i+1<w;++i) {
                m[heightMap[i][0]].push_back({i,0});
                m[heightMap[i][h-1]].push_back({i,h-1});
                heightMap[i][0] = heightMap[i][h-1] = 0;
            }
            for(int i=1;i+1<h;++i) {
                m[heightMap[0][i]].push_back({0,i});
                m[heightMap[w-1][i]].push_back({w-1,i});
                heightMap[0][i] = heightMap[w-1][i] = 0;
            }
            
            //not wanna process the 4 corners, for they are irrelevant to the problem, right?
            heightMap[0][0] = heightMap[0].back() = heightMap.back()[0] = heightMap.back().back() = 0;
            
            int ret = 0;
    #define X first
    #define Y second
            while(!m.empty()) {
                auto b = m.begin();
                int height = b->first;
                auto& v = b->second;
                for(int i = 0;i<v.size();++i) {
                    auto p = v[i];
                    pair<int,int> nodes[4] = {p,p,p,p};
                    --nodes[0].X;
                    ++nodes[1].X;
                    --nodes[2].Y;
                    ++nodes[3].Y;
                    for(int i=0;i<4;++i) {
                        p = nodes[i];
                        if(p.X<0||p.Y<0||p.X>=w||p.Y>=h || !heightMap[p.X][p.Y]) continue;
                        ret += max(0,height-heightMap[p.X][p.Y]);
                        heightMap[p.X][p.Y] = max(heightMap[p.X][p.Y],height);
                        //push to map
                        //if the new height is the same, we can save some time on BST insertion
                        if(heightMap[p.X][p.Y] == height)v.push_back(p);
                        else m[heightMap[p.X][p.Y]].push_back(p);
                        heightMap[p.X][p.Y] = 0; // mark it as traverse
                    }
                }
                m.erase(b);
            }
            return ret;
        }
    };
    

  • 0
    S

    @leo.lai.944 said in share my fast C++ solution using std::map (99~100%, 40+ ms):

    class Solution {
    public:
    int trapRainWater(vector<vector<int>>& heightMap) {
    int w = heightMap.size();

        //check the dimension...otherwise gotta do boundary checking in the next step anyway
        if(w<=2)return 0;
        int h = heightMap[0].size();
        if(h <=2)return 0;
        
        map<int,vector<pair<int,int>>> m;
        //initiate the map : push the posisions on the 4 edges except corners
        //abuse the input :P
        //setting heightMap[x][y] to 0 means the node is in the map or traversed
        for(int i=1;i+1<w;++i) {
            m[heightMap[i][0]].push_back({i,0});
            m[heightMap[i][h-1]].push_back({i,h-1});
            heightMap[i][0] = heightMap[i][h-1] = 0;
        }
        for(int i=1;i+1<h;++i) {
            m[heightMap[0][i]].push_back({0,i});
            m[heightMap[w-1][i]].push_back({w-1,i});
            heightMap[0][i] = heightMap[w-1][i] = 0;
        }
        
        //not wanna process the 4 corners, for they are irrelevant to the problem, right?
        heightMap[0][0] = heightMap[0].back() = heightMap.back()[0] = heightMap.back().back() = 0;
        
        int ret = 0;
    

    #define X first
    #define Y second
    while(!m.empty()) {
    auto b = m.begin();
    int height = b->first;
    auto& v = b->second;
    for(int i = 0;i<v.size();++i) {
    auto p = v[i];
    pair<int,int> nodes[4] = {p,p,p,p};
    --nodes[0].X;
    ++nodes[1].X;
    --nodes[2].Y;
    ++nodes[3].Y;
    for(int i=0;i<4;++i) {
    p = nodes[i];
    if(p.X<0||p.Y<0||p.X>=w||p.Y>=h || !heightMap[p.X][p.Y]) continue;
    ret += max(0,height-heightMap[p.X][p.Y]);
    heightMap[p.X][p.Y] = max(heightMap[p.X][p.Y],height);
    //push to map
    //if the new height is the same, we can save some time on BST insertion
    if(heightMap[p.X][p.Y] == height)v.push_back(p);
    else m[heightMap[p.X][p.Y]].push_back(p);
    heightMap[p.X][p.Y] = 0; // mark it as traverse
    }
    }
    m.erase(b);
    }
    return ret;
    }
    };

    Submission Result: Wrong Answer More Details

    Input:
    [[9,9,9,9,9,9,8,9,9,9,9],[9,0,0,0,0,0,1,0,0,0,9],[9,0,0,0,0,0,0,0,0,0,9],[9,0,0,0,0,0,0,0,0,0,9],[9,9,9,9,9,9,9,9,9,9,9]]
    Output:
    7
    Expected:
    215


  • 0

    @simonwoo Thanks for letting me know.

    I think what is wrong is the testcase, not my solution, which I have pointed out. so please check my new post:

    https://discuss.leetcode.com/topic/69785/new-testcases-are-inconsistent-with-problem-constraint


Log in to reply
 

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