Island Perimeter
Each land cell contributes 4 minus 2 per shared edge with a neighboring land cell.
4 min read
matrix counting
Problem#
Given a grid where 1 is land and 0 is water (a single island, no lakes), return the island’s perimeter.
Examples#
[[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]→16[[1]]→4[[1,0]]→4
Constraints#
m == grid.length,n == grid[i].length,1 <= m, n <= 100.
Approach#
Each land cell has 4 sides. Each pair of adjacent land cells shares one edge that’s interior to the island, costing 2 from the total perimeter. Counting only right and down neighbors avoids double-counting.
Solution#
class Solution {public: int islandPerimeter(vector<vector<int>>& grid) { int m = grid.size(), n = grid[0].size(); int land = 0, shared = 0; for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { if (grid[i][j] != 1) continue; ++land; if (i + 1 < m && grid[i + 1][j] == 1) ++shared; if (j + 1 < n && grid[i][j + 1] == 1) ++shared; } } return 4 * land - 2 * shared; }};func islandPerimeter(grid [][]int) int { m, n := len(grid), len(grid[0]) land, shared := 0, 0 for i := 0; i < m; i++ { for j := 0; j < n; j++ { if grid[i][j] != 1 { continue } land++ if i+1 < m && grid[i+1][j] == 1 { shared++ } if j+1 < n && grid[i][j+1] == 1 { shared++ } } } return 4*land - 2*shared}from typing import List
class Solution: def islandPerimeter(self, grid: List[List[int]]) -> int: m, n = len(grid), len(grid[0]) land = shared = 0 for i in range(m): for j in range(n): if grid[i][j] != 1: continue land += 1 if i + 1 < m and grid[i + 1][j] == 1: shared += 1 if j + 1 < n and grid[i][j + 1] == 1: shared += 1 return 4 * land - 2 * sharedfunction islandPerimeter(grid) { const m = grid.length, n = grid[0].length; let land = 0, shared = 0; for (let i = 0; i < m; i++) { for (let j = 0; j < n; j++) { if (grid[i][j] !== 1) continue; land++; if (i + 1 < m && grid[i + 1][j] === 1) shared++; if (j + 1 < n && grid[i][j + 1] === 1) shared++; } } return 4 * land - 2 * shared;}class Solution { public int islandPerimeter(int[][] grid) { int m = grid.length, n = grid[0].length; int land = 0, shared = 0; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (grid[i][j] != 1) continue; land++; if (i + 1 < m && grid[i + 1][j] == 1) shared++; if (j + 1 < n && grid[i][j + 1] == 1) shared++; } } return 4 * land - 2 * shared; }}function islandPerimeter(grid: number[][]): number { const m = grid.length, n = grid[0].length; let land = 0, shared = 0; for (let i = 0; i < m; i++) { for (let j = 0; j < n; j++) { if (grid[i][j] !== 1) continue; land++; if (i + 1 < m && grid[i + 1][j] === 1) shared++; if (j + 1 < n && grid[i][j + 1] === 1) shared++; } } return 4 * land - 2 * shared;}Editorial#
Avoiding DFS sidesteps recursion overhead and gives a clean closed-form O(m*n) sweep. The trick is to count each shared edge exactly once — pick a canonical direction pair (right/down).
Complexity#
- Time: O(m*n).
- Space: O(1).
Concept revision#
Related#