12-liner C++ concise priority queue with global indexing, no self-defined struct (with explanation and comments)


  • 1

    As many fellow coders have posted here, the key to solve this problem is to start from boundary cells, look for lowest ones first, and BSF to search neighbors. Searching in this order is because we can only decide the trapped water height at boundary cells with lowest height first.

    No self-made struct is needed because C++ STL has provided enough container templates for manipulation to get what we want.

    Some key variables and treatment in my code below:

    1. A priority queue q of type priority_queue<pair<int, int>,vector<pair<int, int>>,greater<pair<int, int>>> is used to store currently searched pairs (h, i) with lowest h as priority, where i is the global index of a cell.
    2. Global index i of a cell at location (row, col) can be easily converted to local index:
      • row = i/n, col = i%n, where n is number of columns in the given height map h[][].
    3. maxh is the maximum height so far in BSF process. This variables is used to determined the height of water trapped at each current cell.
        typedef pair<int, int> PI;
        int trapRainWater(vector<vector<int>>& h) {
            int m, n, water = 0;
            if(!(m=h.size()) || !(n=h[0].size())) return 0; // check map bounds
            
            vector<int> visited(m*n,0); // if cell(i) is visited
            priority_queue<PI,vector<PI>,greater<PI>> q; // priority queue of (h,index) by min height
            
            for (int i = 0; i < m*n; ++i) // initialize queue with all boundary cells
              if (i%n*((i+1)%n)*(i/n)*(i/n-m+1)==0) q.emplace(h[i/n][i%n],i), visited[i] = 1;
    
            for(int i, maxh = INT_MIN; q.size(); ) { // BSF
                auto cur = q.top(); q.pop(); maxh = max(maxh, cur.first);
                for(int d : {n, -n, 1, -1})
                    if((i = cur.second+d)>=0 && i<m*n && !visited[i]) // a valid unvisited neighbor
                      water += max(maxh-h[i/n][i%n], 0), q.emplace(h[i/n][i%n], i), visited[i] = 1;
            }
            return water;        
        }
    

Log in to reply
 

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