Island Perimeter

easy array matrix dfs

Problem

You are given row-by-row a grid where 1 is land and 0 is water. There is exactly one island (a 4-connected group of 1s). Return the perimeter of the island.

Inputgrid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]

Output16

Each land cell contributes 4, minus 2 for each shared edge with another land cell.

grid (rows separated by ;, cells by ,)

def island_perimeter(grid):
    rows, cols = len(grid), len(grid[0])
    p = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 1:
                p += 4
                if r > 0 and grid[r-1][c] == 1: p -= 2
                if c > 0 and grid[r][c-1] == 1: p -= 2
    return p

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

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

int islandPerimeter(vector<vector<int>>& grid) {
    int rows = grid.size(), cols = grid[0].size(), p = 0;
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (grid[r][c] == 1) {
                p += 4;
                if (r > 0 && grid[r-1][c] == 1) p -= 2;
                if (c > 0 && grid[r][c-1] == 1) p -= 2;
            }
        }
    }
    return p;
}

Explanation

Instead of tracing the island's outline, we use a clever counting trick: every land cell is a square that contributes 4 sides, and whenever two land cells touch, the shared wall between them is not part of the perimeter.

So we sweep the grid cell by cell. Each time we hit a land cell (1) we add 4 to the perimeter p. Then we check if it borders land we've already counted.

The neat part: we only look up and left. If the cell above is land, that shared edge was double-counted (once by each cell), so we subtract 2. Same for a land cell to the left. Looking only backward means every shared wall is handled exactly once across the whole sweep.

Example: in [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]] there are 7 land cells giving 7 × 4 = 28, and 6 internal shared edges removing 6 × 2 = 12, for a perimeter of 16.

Because we touch each cell once and do constant work per cell, this is a fast single pass with no extra memory.

Time: O(R · C) Space: O(1)