Clean java solution O(mn)


  • 4
    A
    Idea: Every side of a land-cell exposed to water-cell will be part of perimeter.
    
    public int islandPerimeter(int[][] grid) {
        int[][] d = new int[][] {{0,-1}, {-1,0}, {0,1}, {1,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] == 0)
                    continue;
                
                for(int k=0; k<d.length; k++) {
                    int x=i+d[k][0], y=j+d[k][1];
                    if(x<0 || x>=grid.length || y<0 || y>=grid[0].length || grid[x][y] == 0)
                        perimeter++;
                }
            }
        }
        
        return perimeter;
    }
    
    Time complexity:  O(mn)
    Space complexity: O(1)

  • 0
    H

    Thanks for sharing your solution. Can you explain a bit more?


  • 0
    A

    @Humandroid
    All the sides having water on one side and land on other side would be part of perimeter. Here are two ways to code this idea:

    • Iterate over all the cells, and if current cell is land-cell then check if there is water-cell adjacent to each sides of this land-cell

      or

    • Iterate over all the cells, and if current cell is water-cell then check if there is land-cell adjacent to each sides of this water-cell


  • 2
    H

    similar solution:

    public class Solution {
        public int islandPerimeter(int[][] grid) {
            int perimeter=0;
            for(int i=0;i<grid.length;i++){
                for(int j=0;j<grid[0].length;j++){
                    if(!isValid(grid,i,j)) continue;
                    if(!isValid(grid,i-1,j)) perimeter++; //left
                    if(!isValid(grid,i+1,j)) perimeter++; //right
                    if(!isValid(grid,i,j-1)) perimeter++; //top
                    if(!isValid(grid,i,j+1)) perimeter++; //bottom
                }
            }
            return perimeter;
        }
    
        private boolean isValid(int[][] grid, int p,int q){
            if(p<0||p>=grid.length||q<0||q>=grid[0].length||grid[p][q]==0) return false;
            return true;
        }
    }
    

Log in to reply
 

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