Simple solution without using DFS


  • 0
    M

    First find the number of 1s in the grid. Each cell contributes 4 units to the perimeter.
    However, in shared blocks scenario, one border is shared with another cell and this will always be an internal boundary. We need to subtract these shared borders.

    Consider 2 cells adjacent to each other (Left and Right)
    They have 3 outer borders each and one shared internal border.
    Effectively, each contributes only 3 walls towards the perimeter.
    i.e. from the total perimeter of 2 * 4 , 2 shared borders are missing. So, total perimeter becomes 8 - 1*2 = 6

    To put it simply,
    total perimeter= (number of 1s * 4) - (number of shared borders * 2)

    public class Solution {
        public int islandPerimeter(int[][] grid) {
            
            if(grid==null ||grid.length==0){
                return 0;
            }
            
            int oneCount=0;
            int sharedBorder=0;
            
            for(int i=0;i<grid.length;i++){
                for(int j=0;j<grid[0].length;j++){
                    if(grid[i][j]==1){
                        oneCount++;
                        
                        if(i<grid.length-1 && grid[i+1][j]==1){
                            sharedBorder++;
                        }
                        if( j<grid[0].length-1 && grid[i][j+1]==1){
                            sharedBorder++;
                        }
                    }
                }
            }
            return (oneCount*4) - (sharedBorder*2);
        }
    }
    

Log in to reply
 

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