java 2 solutions, dfs & naive


  • 0
    M

    DFS solution:
    Time: O(n^2). The actual runtime is the steps of find the first land plus the number of land grid.

        public int islandPerimeter(int[][] grid) {
            if(grid==null || grid.length==0) return 0;
            int perimeter = 0;
            for(int i=0; i<grid.length; i++){
                for(int j=0; j<grid[0].length; j++){
                    if(grid[i][j]==1){
                        perimeter = dfs(i, j, grid);
                        break;
                    }
                }
            }
            return perimeter;
        }
        int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};
        private int dfs(int x, int y, int[][] grid){
        	grid[x][y] = 2;
            int count = 0;
            for(int[] dir : dirs){
                int xx = x+dir[0];
                int yy = y+dir[1];
                if(xx<0 || yy<0 || xx>=grid.length || yy>=grid[0].length || grid[xx][yy]==0) {
                    count++; //border or water
                } else if(grid[xx][yy]==1){ // unvisited land
                    count += dfs(xx, yy, grid);
                }
            }
            return count;
        }
    
    

    The naive solution:
    Time: O(n^2)

        public int islandPerimeter(int[][] grid) {
            if(grid==null || grid.length==0) return 0;
            int perimeter = 0;
            int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};
            for(int i=0; i<grid.length; i++){
                for(int j=0; j<grid[0].length; j++){
                    if(grid[i][j]==1){
                        for(int[] dir : dirs){
                            int xx = i+dir[0], yy = j+dir[1];
                            if(xx<0 || yy<0 || xx>=grid.length || yy>=grid[0].length || grid[xx][yy]==0)
                                perimeter++; //border or water
                        }
                    }
                }
            }
            return perimeter;
        }
    

Log in to reply
 

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