2-pass O(1) space Java solution


  • 0

    This solution may not be the best (or efficient) one. I just found it is different with most solutions posted. So I'm posting it just to share another idea.
    Let's say we are scanning a row, and we found a LAND (row[i]==LAND). Then we are thinking whether we should count its bound (Here we only consider left and right bound because we are scanning horizontally).
    So when should we count its left bound as perimeter? The answer is: either it is the leftmost cell, or its left cell is WATER. (i==0 || row[i-1]==WATER). Similarly, when (i==row.length-1 || row[i+1]==WATER) we should count its right bound. By scanning all rows, we will be able to count all "horizontal boundary". Similarly, we can do the same thing on all columns, and we will find the perimeter of the entire island.
    The entire process will scan the entire grid twice, and the space complexity is O(1).

    public class Solution {
        private static final int LAND = 1, WATER = 0;
        public int islandPerimeter(int[][] grid) {
            int res = 0;
            for(int[] row:grid){
                for(int i=0; i<row.length; ++i){
                    if(row[i]==LAND){
                        // **01*** or 1***, add left bound
                        if(i==0 || row[i-1]==WATER){
                            ++res;
                        }
                        // ***10** or ***1, add right bound
                        if(i==row.length-1 || row[i+1]==WATER){
                            ++res;
                        }
                    }
                }
            }
            for(int c=0; c<grid[0].length; ++c){
                // for each column
                for(int r=0; r<grid.length; ++r){
                    if(grid[r][c]==LAND){
                        if(r==0 || grid[r-1][c]==WATER){
                            ++res;
                        }
                        if(r==grid.length-1 || grid[r+1][c]==WATER){
                            ++res;
                        }
                    }
                }
            }
            return res;
        }
    }

Log in to reply
 

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