Use layered approach from bottom to up to accumulate water


  • 1
    J

    My algorithm is from bottom to top, layer by layer, in each layer, we can find the empty interior areas. Then accumulate those areas to get the result. To reduce the number of layers, instead of one layer for each height number, we just look at the sorted distinct height values.

    For each new layer, we can calculate the empty areas incrementally based on the lower layer. We start create single point areas for the new heigh value, then merge those areas with existing neighbor areas.

        static class Point {
            int x, y;
            Point(int x, int y) {this.x = x; this.y = y;}
            Point add(Point p) {return new Point(x + p.x, y + p.y);}
            boolean inside(int width, int height) {
                return x >= 0 && x <width && y >= 0 && y < height;
            }
            boolean isBorder(int width, int height) {
                return x ==0 || x == width-1 || y == 0 || y == height -1;
            }
        }
        
        static Point[] directions = {new Point(-1,0), new Point(0, -1), new Point(1, 0), new Point(0, 1)};
    
        class Area {
            boolean interior;
            List<Point> points = new ArrayList<>();
            Area(boolean interior, Point p) {
                this.interior = interior;
                areas.add(this);
                points.add(p);
                point2AreaMap[p.y][p.x] = this;
            }
            void merge(Area a) {
                interior = interior && a.interior;
                points.addAll(a.points);
                for(Point p : a.points)
                    point2AreaMap[p.y][p.x] = this;
                areas.remove(a);
            }
        }
    
        int width, height;
        Set<Area> areas;
        Area[][] point2AreaMap;
        
        public int trapRainWater(int[][] heightMap) {
            height = heightMap.length;
            if(height == 0)
                return 0;
            width = heightMap[0].length;
            if(width == 0)
                return 0;
    
            areas = new HashSet<>();
            point2AreaMap = new Area[height][width];
            TreeMap<Integer, List<Point>> sortedPoints = buildSortedPoints(heightMap);
            
            int result = 0;
            int previousHeight = 0;
            int previousArea = 0;
            for(Map.Entry<Integer, List<Point>> entry : sortedPoints.entrySet()) {
                result += (entry.getKey() - previousHeight) * previousArea;
                entry.getValue().forEach(p -> mergeAreas(p));
                previousArea = getArea();
                previousHeight = entry.getKey();
            }
            return result;
        }
        
        int getArea() {        
            int result = 0;
            
            for(Area a : areas) {
                if(a.interior)
                    result += a.points.size();
            }        
            return result;
        }
        
        void mergeAreas(Point p) {
            Area area = new Area(!p.isBorder(width, height), p);
            for(Point d : directions) {
                Point pn = p.add(d);
                if(!pn.inside(width, height))
                    continue;
                Area nArea = point2AreaMap[pn.y][pn.x];
                if(nArea == null || nArea == area)
                    continue;
                
                if(area.points.size() > nArea.points.size())
                    area.merge(nArea);
                else { 
                    nArea.merge(area);
                    area = nArea;
                }
            }
        }
        
        TreeMap<Integer, List<Point>> buildSortedPoints(int[][] heightMap) {
            TreeMap<Integer, List<Point>> result = new TreeMap<>();
            for(int y=0; y<height; y++)
                for(int x=0; x<width; x++) {
                    int h = heightMap[y][x];
                    List<Point> points = result.get(h);
                    if(points == null) {
                        points = new ArrayList<>();
                        result.put(h, points);
                    }
                    points.add(new Point(x,y));
                }
            return result;
        }
    

Log in to reply
 

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