clear and easy java solution


  • 117
    1. loop over the matrix and count the number of islands;
    2. if the current dot is an island, count if it has any right neighbour or down neighbour;
    3. the result is islands * 4 - neighbours * 2
    public class Solution {
        public int islandPerimeter(int[][] grid) {
            int islands = 0, neighbours = 0;
    
            for (int i = 0; i < grid.length; i++) {
                for (int j = 0; j < grid[i].length; j++) {
                    if (grid[i][j] == 1) {
                        islands++; // count islands
                        if (i < grid.length - 1 && grid[i + 1][j] == 1) neighbours++; // count down neighbours
                        if (j < grid[i].length - 1 && grid[i][j + 1] == 1) neighbours++; // count right neighbours
                    }
                }
            }
    
            return islands * 4 - neighbours * 2;
        }
    }
    

  • 1

    great solution! just curious how did you find out this pattern?


  • 45

    @cpmvp

    just math, man. ;-P

    1. descriptions of this problem implies there may be an "pattern" in calculating the perimeter of the islands.
    2. and the pattern is islands * 4 - neighbours * 2, since every adjacent islands made two sides disappeared(as picture below).
    3. the next problem is: how to find the neighbours without missing or recounting? i was inspired by the problem: https://leetcode.com/problems/battleships-in-a-board/
    +--+     +--+                   +--+--+
    |  |  +  |  |          ->       |     |
    +--+     +--+                   +--+--+
    
    4 + 4 - ? = 6  -> ? = 2
    

  • 1

    @liupangzi
    pretty cool!!
    thx so much!


  • 10
    D

    @cpmvp I was giving this pattern a lot of thought. The most intuitive way I could understand it was this.

    Each island or cell has 4 sides and to get the total potential number of sides you would need to multiply the total number of islands by 4. Easy enough...

    For the subtraction half...

    Let's define what a side can possibly mean.
    (1) A side that belongs to the perimeter count is required to belong to only one island.
    (2) A side which is not included in the perimeter count is a side that belongs to two islands.

    We are looking for a side that satisfies two requirements -
    (a) It's a side of an island
    (b) It's a side that belongs to only one island (see #1)

    Why check only right and down neighbors?
    The reason why the above solution checks the right and down neighbors because it prevents counting or checking a side twice (go ahead and visually try it).

    Why multiply neighbors by 2?
    We are checking if a side is #2. The side is shared by two islands and so we have to multiply the neighbors by two.


  • 0

    @dthai92
    thx a lot!
    @liupangzi has also given a great explanation, thank you both so much!
    upvoted :)


  • 0
    L

    Nice Solution. I like especially that you only checked right and down neighbors to avoid double counting. Smart way to avoid counting all sides


  • 0
    R

    HI,pretty!!
    First ,i occuered to this patten:

    island*4-neighours&2

    but the problem is that i didn't know how to achieve this solution,just didnt konw how to begain until i saw your solution .THANKS!!


  • 16

    DFS, no math tricky.

      public int islandPerimeter(int[][] grid) {
        if(grid.length == 0) return 0;
        for(int i = 0; i < grid.length; i++){
          for(int j = 0; j < grid[0].length; j++){
            if(grid[i][j] == 1){
              return helper(grid, i, j);
            }
          }  
        } 
        return 0;
      }
      
      private int helper(int[][] grid, int i, int j){
        grid[i][j] = -1;
        int count = 0;
        
        if(i - 1 < 0 || grid[i - 1][j] == 0) count++;
        else if(grid[i - 1][j] == 1) count += helper(grid, i - 1, j);
        
        if(i + 1 >= grid.length || grid[i + 1][j] == 0) count++;
        else if(grid[i + 1][j] == 1) count += helper(grid, i + 1, j);
        
        if(j - 1 < 0 || grid[i][j - 1] == 0) count++;
        else if(grid[i][j - 1] == 1) count += helper(grid, i, j - 1); 
        
        if(j + 1 >= grid[0].length || grid[i][j + 1] == 0) count++;
        else if(grid[i][j + 1] == 1) count += helper(grid, i, j + 1);
        
        return count;
      }

  • 0
    C

    @hot13399 , Very good solution.


  • 0
    S

    @hot13399 This solution is really intuitive!


  • 0
    G

    Above answer is very simple and clear. Including my answer below which skips columns as there cannot be any lakes. The same optimization can be applied on @liupangzi answer

    Complexity is still O(mn)

    public int islandPerimeter(int[][] grid) {
            int perimeter = 0, lastRowLength=0;
            for (int i = 0; i <= grid.length; i++) {
                boolean visitedAlandOnThisRow = false;
                int j = 0;
                for (; j <= grid[0].length; j++) {
                    int current = isLand(grid, i, j);
                    //count area only for top and left edges
                    if (current == 1) { 
                       //when we are on land flip the values of top and left cells to consider or ignore the edge.
                        perimeter += (isLand(grid, i - 1, j) == 0 ? 1 : 0);
                        perimeter += (isLand(grid, i, j - 1) == 0 ? 1 : 0);
                        visitedAlandOnThisRow = true;
                    } else {
                        perimeter += isLand(grid, i, j - 1); //left
                        int top = isLand(grid, i - 1, j);
                        perimeter += top;
                        /*
                          optimization: 
                          when land ends on this row, no need to visit rest of the water if we 
                          dont have a land on the previous row whose j > current j in order to count it's bottom
                        */
                        if (visitedAlandOnThisRow && top == 0 && i > 0 && j > lastRowLength) {
                              break;
                        }
                    }
                }
                lastRowLength = j-1;
            }
            return perimeter;
        }
    
        /* 
           Method to address boundary cells
           returns 0 for water and 1 for land for a given location i,j
        */
        private int isLand(int[][] grid, int i, int j) {
            return (i < 0 || j < 0 || i == grid.length || j == grid[0].length) ? 0 : grid[i][j];
        }
    

  • 0
    L

    @hot13399 nice DFS,it is concise! Thank u for your sharing!


  • 7

    Easy solution without dfs, just iterate each cell and count how many edges we need to add : )

        public int islandPerimeter(int[][] grid) {
            int sum = 0;
            if (grid == null || grid.length == 0 || grid[0].length == 0) return sum;
            for (int i = 0; i < grid.length; i++) {
                for (int j = 0; j < grid[0].length; j++) {
                    if (grid[i][j] == 0)
                        continue;
                    if (i == 0 || grid[i-1][j] == 0) sum++;
                    if (i == grid.length - 1 || grid[i+1][j] == 0) sum++;
                    if (j == 0 || grid[i][j-1] == 0) sum++;
                    if (j == grid[0].length - 1 || grid[i][j+1] == 0) sum++;
                }
            }
            return sum;
        }
    

  • 0

    @alanwang I like your idea! At first I try to count toward 4 directions like yours, at each 0 cell though. But your solution is much simpler. Thanks for sharing!


  • 0
    Y

    What a great idea! The reason why we only count the right and down neighbors is that if
    one cell has a left or up neighbor, it must have been counted by other cells as their right or down neighbors, and in the end, we just decrease the two sides of those adjacent islands.


  • 2

    A land grid surrounded by water needs the border on that side. So count that as 1.

    A similar question asked at Google was "Trees Fencing - how much fencing is needed to cover tree groups (similar to island)".
    If the requirement is to give fencing for each group of trees, then you might need to apply dfs and find the group of trees. If it's just the total fencing, then below code should be good enough(even with land gaps in the middle of trees).

    public int islandPerimeter(int[][] grid) {
        int border = 0;
        for(int i = 0; i < grid.length; i++) {
            for(int j = 0; j < grid[i].length; j++) {
                if(grid[i][j] == 1) {
                    if(i == 0 || grid[i-1][j] == 0) border++; // above water
                    if(j == 0 || grid[i][j-1] == 0) border++; // left water
                    if(j+1 == grid[i].length || grid[i][j+1] == 0) border++; // right water
                    if(i+1 == grid.length || grid[i+1][j] == 0) border++; // below water
                }
            }
        }
        return border;
    }

  • 0
    H
    This post is deleted!

  • 0
    I

  • 0

    @hot13399 First, appreciate for your solution, but i still have a little confusion:
    why does the else statement still need considering the if condition? the grid has only two value 0 or 1.When i try to remove the if statment, it turns out StackOverflowError.


Log in to reply
 

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