Trapping Rain Water II

This question also screams breadth-first search. To be honest, anything with a grid structure that wants you to visit each square is probably breadth-first search. Leetcode also tends to consequtively release daily problems that are of the same genre, so that is something to keep note of (last week was bit manipulation).

In my algorithm, I realised immediately that any of the cells that are exposed to any side of the grid is incapable of holding water, meaning not only does the grid have to be at least 2 cells long and 2 cells wide for it to be possible to hold water, but the exterior cells form a sort of 'outline' or 'border', surrounding the cells that potentially will be able to hold water. From this point onwards, we will be calling the exterior cells (and cells that we have seen), border cells, and the remaining cells that we have not seen yet, interior cells.

The hardest part of this question is probably figuring out what you are meant to search. In my case, since for a cell to hold water it has to be surrounded by cells that have a higher height than it, with the amount of water it holds being dependent on the min height of the surrounding cells.

Intuitively, it makes sense to start the search from the 'border' cells with the min height, as:

• if the neighbouring interior cells have height greater than or equal to the border cell, then obviously no water is trapped and the neighbouring interior cells become the new border cells
• if the neighbouring interior cells have height smaller than the border cell, then we know the neighbouring interior cells must trap water up to the height of the border cell (as we are always searching from the min height border cell) and can therefore 'inherit' the height of the border cell for the next iteration.

Now, we just repeat this procedure until all cells have been visited, keeping track of the total volume of water trapped on every iteration.

code

class Solution {
private:
    class Cell {
        public:
            int h, x, y;

            Cell(int h, int x, int y): h(h), x(x), y(y){};

            bool operator>(const Cell &externalCell) const {
                return h >= externalCell.h;
            }
    };
    int direction[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    void convertValidNeighbour(vector<vector<int>> &heightMap,
                               vector<vector<int>> &seen,
                               auto &boundaryHeights,
                               Cell &currentCell, int &n, int &m,
                               int &ans, int &cellsRemaining) {
        int tempHeight;

        for (int i = 0; i < 4; ++i) {
            int new_x = currentCell.x + direction[i][0];
            int new_y = currentCell.y + direction[i][1];
            if (new_x > 0 && new_x < n-1
                && new_y > 0 && new_y < m-1 && seen[new_y][new_x] == 0) {
                int prevHeight = heightMap[new_y][new_x];
                int newHeight = max(prevHeight, currentCell.h);

                seen[new_y][new_x] = 1;
                heightMap[new_y][new_x] = newHeight;
                boundaryHeights.push(Cell(newHeight, new_x, new_y));
                ans += max(0, currentCell.h-prevHeight);
                --cellsRemaining;
            }
        }
    }
public:
    int trapRainWater(vector<vector<int>>& heightMap) {
        int m = heightMap.size(), n = heightMap[0].size();

        if (m <= 2 or n <= 2) return 0;

        priority_queue<Cell, vector<Cell>, greater<Cell>> boundaryHeights;
        int cellsRemaining = (n-2)*(m-2);
        int ans = 0;

        vector<vector<int>> seen(m, vector<int>(n, 0));
        for (int i = 0; i < m; ++i) {
            if (i == 0 or i == m-1) {
                for (int j = 0; j < n; ++j) {
                    seen[i][j] = 1;
                    boundaryHeights.push(Cell(heightMap[i][j], j, i));
                }
            } else {
                seen[i][0] = 1;
                boundaryHeights.push(Cell(heightMap[i][0], 0, i));
                seen[i][n-1] = 1;
                boundaryHeights.push(Cell(heightMap[i][n-1], n-1, i));
            }
        }

        while(cellsRemaining > 0) {
            Cell temp = boundaryHeights.top();
            boundaryHeights.pop();
            convertValidNeighbour(heightMap, seen, boundaryHeights,
                                  temp, n, m, ans, cellsRemaining);
        }

        return ans;
    }
};

complexity

• time: O(mn)
• space: O(mn)

any learnings?

• need to revisit class in cpp

private:
class Cell {
    public:
        int h, x, y;

        // class constructor
        Cell(int h, int x, int y): h(h), x(x), y(y){};

        // define std::greater or > between Cell
        // needs the two `const` values
        bool operator>(const Cell &externalCell) const {
            return h >= externalCell.h;
        }
};

• need to revisit priority_queue in cpp

// simplest way to initialize priority_queue
priority_queue<Cell> boundaryHeights;

// which is equivalent to
priority_queue<Cell, vector<Cell>, less<Cell>> boundaryHeights;
// Cell = type of stored element
// vector<Cell> = type of container to store the elements
// less<Cell> = the Compare type to provide ordering within the priority_queue (e.g. for min-heap / max-heap)

// since I am using a custom class, I have to define std::less with
bool operator<(const Cell &other) const {
    return ...;
}

// but in my case, to make a min-heap, it is syntactically more correct to define
bool operator>(const Cell &other) const {
    return ...;
}

// and use:
priority_queue<Cell, vector<Cell>, greater<Cell>> boundaryHeights;