Island Perimeter

Problem Description

You are given row x col grid representing a map where grid[i][j] = 1 represents land and grid[i][j] = 0 represents water.

Grid cells are connected horizontally/vertically (not diagonally). There is exactly one island (or none), and there are no lakes.

Return the perimeter of the island.

Examples

Constraints

• row == grid.length
• col == grid[i].length
• 1 ≤ row, col ≤ 100
• grid[i][j] is 0 or 1
• There is exactly one island

Count Edges, Not Cells

Each land cell contributes 4 edges to the potential perimeter. For each neighbor that is also a land cell, that shared edge is internal and not part of the perimeter. Subtract 2 for each land-land adjacency (once for each cell’s perspective).

No DFS or BFS needed. One pass over the grid is sufficient.

Solution

class Solution {
    public int islandPerimeter(int[][] grid) {
        int perimeter = 0;
        for (int r = 0; r < grid.length; r++) {
            for (int c = 0; c < grid[0].length; c++) {
                if (grid[r][c] == 1) {
                    perimeter += 4;
                    // subtract for each adjacent land cell
                    if (r > 0 && grid[r-1][c] == 1) perimeter -= 2;
                    if (c > 0 && grid[r][c-1] == 1) perimeter -= 2;
                }
            }
        }
        return perimeter;
    }
}

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

#include <vector>

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

Complexity Analysis:

• Time Complexity: O(m * n). Single pass over all cells.
• Space Complexity: O(1).

Where it breaks: the optimization of only checking up and left (instead of all 4 directions) works because we process cells top-to-bottom, left-to-right. When we process cell (r, c), cells (r+1, c) and (r, c+1) haven’t been processed yet, so we’ll handle those shared edges when we get to those cells.

← All Problems