Island Perimeter — Grid Edge Counting

Problem

Return the perimeter of the island in grid (only one island, no lakes).

Example:

grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]
Output: 16

Approach — Counting Shared Edges

Each land cell contributes 4 to perimeter. Each shared edge with another land cell subtracts 2 (one from each cell). So: perimeter = 4*land - 2*shared.

Time: O(m*n) | Space: O(1)

Solutions

C

int islandPerimeter(int** grid, int R, int* cols) {
    int C=cols[0], p=0;
    for(int r=0;r<R;r++) for(int c=0;c<C;c++) {
        if(!grid[r][c]) continue;
        p+=4;
        if(r>0&&grid[r-1][c]) p-=2;
        if(c>0&&grid[r][c-1]) p-=2;
    }
    return p;
}

C++

class Solution {
public:
    int islandPerimeter(vector<vector<int>>& grid) {
        int R=grid.size(),C=grid[0].size(),p=0;
        for(int r=0;r<R;r++) for(int c=0;c<C;c++) {
            if(!grid[r][c]) continue;
            p+=4;
            if(r>0&&grid[r-1][c]) p-=2;
            if(c>0&&grid[r][c-1]) p-=2;
        }
        return p;
    }
};

Java

class Solution {
    public int islandPerimeter(int[][] grid) {
        int R=grid.length,C=grid[0].length,p=0;
        for(int r=0;r<R;r++) for(int c=0;c<C;c++) {
            if(grid[r][c]==0) continue;
            p+=4;
            if(r>0&&grid[r-1][c]==1) p-=2;
            if(c>0&&grid[r][c-1]==1) p-=2;
        }
        return p;
    }
}

JavaScript

var islandPerimeter = function(grid) {
    let p=0;
    for(let r=0;r<grid.length;r++) for(let c=0;c<grid[0].length;c++) {
        if(!grid[r][c]) continue;
        p+=4;
        if(r>0&&grid[r-1][c]) p-=2;
        if(c>0&&grid[r][c-1]) p-=2;
    }
    return p;
};

Python

class Solution:
    def islandPerimeter(self, grid: list[list[int]]) -> int:
        R,C=len(grid),len(grid[0])
        p=0
        for r in range(R):
            for c in range(C):
                if grid[r][c]:
                    p+=4
                    if r>0 and grid[r-1][c]: p-=2
                    if c>0 and grid[r][c-1]: p-=2
        return p

Complexity

Time: O(m*n) | Space: O(1)