Java Solution Based on Wooden Barrel Theory


  • 0

    Basically, the whole idea is inspired from Wooden Barrel Theory.

    In the matrix heightMap, only those points whose height are smaller or equal to its neighbors are likely to trap water.

    The whole procedure is as follows:


    First, we calculate the sum of heightMap, named sum0

    Then, we initialize a queue with all points whose height are smaller or equal to its 4 adjacent points.

    Loop until queue is empty:

    • Let h be the very front element of queue

    • Use BFS to find out a point set named vs, whose points share the same height with h, and are directly/indirectly adjacent to h. We can also get the min neighbor height of vs, called minh.

    • Remove all points in vs from queue. Update the height of points in vs with minh if minh is larger than h, and then add h to the rear of queue.

    Calculate the sum of heightMap again, named sum1

    The final answer is sum1 - sum0


    Java Code:

    import java.awt.Point;
    
    public class Solution {
    
        private int m, n;
        private int[][] heightMap;
        private int dx[] = {1, 0, -1, 0};
        private int dy[] = {0, 1, 0, -1};
        
        public int trapRainWater(int[][] heightMap) {
            this.heightMap = heightMap;
            this.m = heightMap.length;
            if (this.m > 0) this.n = heightMap[0].length;
            
            int sum = calcHeightMapSum();
            
            LinkedHashSet<Point> queue = new LinkedHashSet<Point>();
            for (int i = 1; i < m - 1; i++) {
                for (int j = 1; j < n - 1; j++) {
                    if (minNeighborHeight(i, j) >= heightMap[i][j]) {
                        queue.add(new Point(i, j));
                    }
                }
            }
            
            while (!queue.isEmpty()) {
                Point h = queue.iterator().next();
                HashSet<Point> vs = new HashSet<Point>();
                int minh = bfs(h, vs);
                if (minh > heightMap[h.x][h.y]) {
                    for (Point e : vs) {
                        heightMap[e.x][e.y] = minh;
                        queue.remove(e);
                    }
                    queue.add(h);
                } else {
                    for (Point e : vs) {
                        queue.remove(e);
                    }
                }
            }
            
            return calcHeightMapSum() - sum;
        }
        
        private int bfs(Point p, HashSet<Point> vs) {
            int ans = Integer.MAX_VALUE;
            int height = heightMap[p.x][p.y];
    
            LinkedList<Point> queue = new LinkedList<Point>();
            vs.add(p);
            queue.add(p);
    
            while (!queue.isEmpty()) {
                Point h = queue.removeFirst();
                if (h.x == 0 || h.y == 0 || h.x == m - 1 || h.y == n - 1) {
                    ans = Math.min(heightMap[h.x][h.y], ans);
                    continue;
                }
                int minh = minNeighborHeight(h.x, h.y);
                if (minh != height) {
                    ans = Math.min(minh, ans);
                    continue;
                }
                for (int k = 0; k < dx.length; k++) {
                    Point np = new Point(h.x + dx[k], h.y + dy[k]);
                    if (heightMap[np.x][np.y] != height) {
                        ans = Math.min(ans, heightMap[np.x][np.y]);
                    } else if (!vs.contains(np)) {
                        vs.add(np);
                        queue.add(np);
                    }
                }
            }
            return ans;
        }
        
        private int minNeighborHeight(int i, int j) {
            int minh = Integer.MAX_VALUE;
            for (int k = 0; k < dx.length; k++) {
                int di = i + dx[k];
                int dj = j + dy[k];
                minh = Math.min(minh, heightMap[di][dj]);
            }
            return minh;
        }
        
        public int calcHeightMapSum() {
            int sum = 0;
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    sum += heightMap[i][j];
                }
            }
            return sum;
        }
       
    }
    
    

    Blog link: http://bookshadow.com/weblog/2016/09/25/leetcode-trapping-rain-water-ii/


  • 0
    V

    The time complexity is O( (mn)^2 log (mn) ) in worst case?


  • 0

    @vanyee Yes, that's right. In the worst case, the heightMap is ascendant in a zigzag way. Each round in the loop, only one cell could be updated.


Log in to reply
 

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