Island Perimeter
Description
You are given a 2D grid of size row × col that represents a map. Each cell in the grid is either 1 (land) or 0 (water).
The grid has the following properties:
- Land cells connect horizontally and vertically (not diagonally)
- There is exactly one island (one connected group of land cells)
- The grid is completely surrounded by water on all edges
- The island contains no lakes (no water cells enclosed inside the island)
Your task is to calculate the perimeter of the island. The perimeter is the total length of the boundary where land meets water or the edge of the grid. Each cell is a unit square with side length 1.
Examples
Example 1
Input: grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]
Output: 16
Explanation: The island is formed by 7 land cells connected horizontally and vertically. The perimeter consists of 16 edges where land meets water or the grid boundary. For example, the cell at (0,1) has 3 perimeter edges (top, left, right are all water/boundary) and 1 internal edge shared with (1,1) below it.
Example 2
Input: grid = [[1]]
Output: 4
Explanation: A single land cell is a 1×1 square. All four of its sides face the grid boundary, giving a perimeter of 4.
Example 3
Input: grid = [[1,0]]
Output: 4
Explanation: There is one land cell at position (0,0). Its top edge faces the grid boundary, its bottom edge faces the grid boundary, its left edge faces the grid boundary, and its right edge faces the water cell at (0,1). All four edges contribute to the perimeter, totaling 4.
Constraints
- row == grid.length
- col == grid[i].length
- 1 ≤ row, col ≤ 100
- grid[i][j] is 0 or 1
- There is exactly one island in the grid
Editorial
Brute Force
Intuition
Imagine you are walking along the shore of an island. Every time the land touches water or the edge of the world, that is a perimeter edge. The natural way to explore an island is to start at any land cell and walk to all connected land cells — this is exactly what Depth-First Search (DFS) does.
The clever trick with DFS is how we count the perimeter: whenever we try to move from a land cell and step off the grid or into water, that failed step tells us we found a perimeter edge. When we step into an already-visited land cell, that is an internal edge we already counted. When we step into an unvisited land cell, we explore it recursively.
So the DFS function returns:
- 1 if we stepped out of bounds or onto water (a perimeter edge)
- 0 if we stepped onto a visited cell (already explored, no new edge)
- sum of 4 recursive calls if we are on a new land cell
Step-by-Step Explanation
Let's trace the DFS on Example 1: grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]:
Step 1: Scan the grid to find the first land cell. Found at (0,1). Start DFS from (0,1).
Step 2: DFS at (0,1): mark visited. Check 4 neighbors:
- Up (-1,1): out of bounds → perimeter +1
- Down (1,1): land, unvisited → explore next
- Left (0,0): water → perimeter +1
- Right (0,2): water → perimeter +1
- Cell (0,1) contributes 3 perimeter edges.
Step 3: DFS at (1,1): mark visited. Check 4 neighbors:
- Up (0,1): visited → 0
- Down (2,1): land → explore next
- Left (1,0): land → explore later
- Right (1,2): land → explore later
- Cell (1,1) contributes 0 perimeter edges (surrounded by land on all sides).
Step 4: DFS at (2,1): mark visited. Check neighbors:
- Up (1,1): visited → 0
- Down (3,1): land → explore next
- Left (2,0): water → perimeter +1
- Right (2,2): water → perimeter +1
- Cell (2,1) contributes 2 perimeter edges.
Step 5: DFS at (3,1): mark visited. Check neighbors:
- Up (2,1): visited → 0
- Down (4,1): out of bounds → perimeter +1
- Left (3,0): land → explore next
- Right (3,2): water → perimeter +1
- Cell (3,1) contributes 2 perimeter edges.
Step 6: DFS at (3,0): mark visited. Check neighbors:
- Up (2,0): water → perimeter +1
- Down (4,0): out of bounds → perimeter +1
- Left (3,-1): out of bounds → perimeter +1
- Right (3,1): visited → 0
- Cell (3,0) contributes 3 perimeter edges.
Step 7: Backtrack to (1,1). Explore left neighbor (1,0).
Step 8: DFS at (1,0): mark visited. Check neighbors:
- Up (0,0): water → perimeter +1
- Down (2,0): water → perimeter +1
- Left (1,-1): out of bounds → perimeter +1
- Right (1,1): visited → 0
- Cell (1,0) contributes 3 perimeter edges.
Step 9: Backtrack to (1,1). Explore right neighbor (1,2).
Step 10: DFS at (1,2): mark visited. Check neighbors:
- Up (0,2): water → perimeter +1
- Down (2,2): water → perimeter +1
- Left (1,1): visited → 0
- Right (1,3): water → perimeter +1
- Cell (1,2) contributes 3 perimeter edges.
Step 11: All cells visited. Total perimeter = 3 + 0 + 2 + 2 + 3 + 3 + 3 = 16.
DFS Traversal — Counting Perimeter Edges of the Island — Watch the DFS explore each land cell and count perimeter edges. Edges facing water or the grid boundary contribute to the perimeter, while edges shared with other land cells do not.
Algorithm
- Scan the grid to find any land cell
- Start DFS from that land cell
- In the DFS function
dfs(row, col):- If
(row, col)is out of bounds or water: return 1 (perimeter edge) - If
(row, col)is already visited: return 0 (internal edge) - Mark
(row, col)as visited - Recursively call DFS on all 4 neighbors (up, down, left, right)
- Return the sum of all 4 recursive calls
- If
- The return value of the initial DFS call is the total perimeter
Code
class Solution {
public:
int islandPerimeter(vector<vector<int>>& grid) {
int rows = grid.size(), cols = grid[0].size();
vector<vector<bool>> visited(rows, vector<bool>(cols, false));
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (grid[i][j] == 1) {
return dfs(grid, visited, i, j, rows, cols);
}
}
}
return 0;
}
private:
int dfs(vector<vector<int>>& grid, vector<vector<bool>>& visited,
int r, int c, int rows, int cols) {
// Out of bounds or water = perimeter edge
if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] == 0)
return 1;
// Already visited = internal edge
if (visited[r][c]) return 0;
visited[r][c] = true;
int perimeter = 0;
perimeter += dfs(grid, visited, r - 1, c, rows, cols);
perimeter += dfs(grid, visited, r + 1, c, rows, cols);
perimeter += dfs(grid, visited, r, c - 1, rows, cols);
perimeter += dfs(grid, visited, r, c + 1, rows, cols);
return perimeter;
}
};class Solution:
def islandPerimeter(self, grid: List[List[int]]) -> int:
rows, cols = len(grid), len(grid[0])
visited = set()
def dfs(r: int, c: int) -> int:
# Out of bounds or water = perimeter edge
if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] == 0:
return 1
# Already visited = internal edge
if (r, c) in visited:
return 0
visited.add((r, c))
perimeter = 0
perimeter += dfs(r - 1, c) # up
perimeter += dfs(r + 1, c) # down
perimeter += dfs(r, c - 1) # left
perimeter += dfs(r, c + 1) # right
return perimeter
for i in range(rows):
for j in range(cols):
if grid[i][j] == 1:
return dfs(i, j)
return 0class Solution {
private boolean[][] visited;
private int rows, cols;
public int islandPerimeter(int[][] grid) {
rows = grid.length;
cols = grid[0].length;
visited = new boolean[rows][cols];
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (grid[i][j] == 1) {
return dfs(grid, i, j);
}
}
}
return 0;
}
private int dfs(int[][] grid, int r, int c) {
// Out of bounds or water = perimeter edge
if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] == 0)
return 1;
// Already visited = internal edge
if (visited[r][c]) return 0;
visited[r][c] = true;
int perimeter = 0;
perimeter += dfs(grid, r - 1, c);
perimeter += dfs(grid, r + 1, c);
perimeter += dfs(grid, r, c - 1);
perimeter += dfs(grid, r, c + 1);
return perimeter;
}
}Complexity Analysis
Time Complexity: O(m × n)
We scan the grid once to find the first land cell (O(m × n) in the worst case). The DFS visits each land cell exactly once and checks its 4 neighbors, so the total work for DFS is proportional to the number of land cells, which is at most m × n. Overall: O(m × n).
Space Complexity: O(m × n)
The visited array (or set) stores whether each cell has been explored, requiring O(m × n) space. Additionally, the recursion stack can grow as deep as the number of land cells in the worst case (e.g., a snake-shaped island), which is also O(m × n). This extra space is the main drawback of this approach.
Why This Approach Is Not Efficient
While the DFS approach correctly computes the perimeter, it uses O(m × n) extra space for the visited array and the recursion stack. For a 100×100 grid, this means allocating up to 10,000 booleans and potentially 10,000 stack frames.
More importantly, DFS introduces unnecessary complexity for this problem. We do not actually need to "explore" the island by following connected paths — the problem guarantees exactly one island, so every land cell we encounter belongs to the same island.
A key observation simplifies everything: each land cell contributes exactly 4 edges to the perimeter. When two land cells are adjacent, they share an edge, and that shared edge removes 2 edges from the total (one from each cell). So the perimeter is simply:
Perimeter = 4 × (number of land cells) − 2 × (number of shared edges)
This formula lets us compute the perimeter in a single grid scan with zero extra space — no visited array, no recursion, no stack.
Optimal Approach - Direct Counting
Intuition
Think about building the island one cell at a time on a tabletop. When you place the very first 1×1 square, it has 4 exposed edges — perimeter is 4. Now place a second square right next to it. The second square also starts with 4 edges, but where the two squares touch, both of those edges become internal. So the perimeter changes by +4 (new square) − 2 (shared edge) = net +2.
This leads to a simple counting formula:
- For every land cell: add 4 (all edges initially exposed)
- For every pair of adjacent land cells: subtract 2 (their shared edge is internal, not perimeter)
To avoid double-counting shared edges, we only check two directions for each cell: right and down. When we check cell (i,j) against (i,j+1) and (i+1,j), we handle each shared edge exactly once as we scan the grid from top-left to bottom-right.
This approach requires no recursion, no visited tracking, and no extra data structures — just a simple loop and a counter.
Step-by-Step Explanation
Let's trace through Example 1: grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]:
Step 1: Initialize perimeter = 0. Begin scanning the grid row by row.
Step 2: Cell (0,1) = land. Add 4 → perimeter = 4. Check down: (1,1) is land → subtract 2 → perimeter = 2. Check right: (0,2) is water → no change. Perimeter = 2.
Step 3: Cell (1,0) = land. Add 4 → perimeter = 6. Check down: (2,0) is water → no change. Check right: (1,1) is land → subtract 2 → perimeter = 4. Perimeter = 4.
Step 4: Cell (1,1) = land. Add 4 → perimeter = 8. Check down: (2,1) is land → subtract 2 → perimeter = 6. Check right: (1,2) is land → subtract 2 → perimeter = 4. Perimeter = 4. (This cell is surrounded by land, so both checks remove shared edges.)
Step 5: Cell (1,2) = land. Add 4 → perimeter = 8. Check down: (2,2) is water → no change. Check right: (1,3) is water → no change. Perimeter = 8. (No adjacent land to the right or below.)
Step 6: Cell (2,1) = land. Add 4 → perimeter = 12. Check down: (3,1) is land → subtract 2 → perimeter = 10. Check right: (2,2) is water → no change. Perimeter = 10.
Step 7: Cell (3,0) = land. Add 4 → perimeter = 14. Check down: out of bounds → no change. Check right: (3,1) is land → subtract 2 → perimeter = 12. Perimeter = 12.
Step 8: Cell (3,1) = land. Add 4 → perimeter = 16. Check down: out of bounds → no change. Check right: (3,2) is water → no change. Perimeter = 16.
Result: Perimeter = 16. Verification: 7 land cells × 4 = 28, minus 6 shared edges × 2 = 12, gives 28 − 12 = 16. ✓
Direct Counting — Add 4, Subtract 2 for Shared Edges — Watch how we scan each cell, add 4 for every land cell, and subtract 2 whenever a land cell has an adjacent land cell to its right or below. Only checking right and down avoids double-counting shared edges.
Algorithm
- Initialize
perimeter = 0 - For each cell
(i, j)in the grid:- If
grid[i][j] == 1(land cell):- Add 4 to perimeter (all edges initially exposed)
- If the cell below
(i+1, j)exists and is land: subtract 2 (shared horizontal edge) - If the cell to the right
(i, j+1)exists and is land: subtract 2 (shared vertical edge)
- If
- Return
perimeter
Why only check right and down? Each shared edge involves two cells. By only checking from the top-left cell of each pair (i.e., the cell that comes first in row-major order), we count every shared edge exactly once.
Code
class Solution {
public:
int islandPerimeter(vector<vector<int>>& grid) {
int rows = grid.size(), cols = grid[0].size();
int perimeter = 0;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (grid[i][j] == 1) {
// Each land cell contributes 4 edges
perimeter += 4;
// Subtract 2 for shared edge with cell below
if (i + 1 < rows && grid[i + 1][j] == 1)
perimeter -= 2;
// Subtract 2 for shared edge with cell to the right
if (j + 1 < cols && grid[i][j + 1] == 1)
perimeter -= 2;
}
}
}
return perimeter;
}
};class Solution:
def islandPerimeter(self, grid: List[List[int]]) -> int:
rows, cols = len(grid), len(grid[0])
perimeter = 0
for i in range(rows):
for j in range(cols):
if grid[i][j] == 1:
# Each land cell contributes 4 edges
perimeter += 4
# Subtract 2 for shared edge with cell below
if i + 1 < rows and grid[i + 1][j] == 1:
perimeter -= 2
# Subtract 2 for shared edge with cell to the right
if j + 1 < cols and grid[i][j + 1] == 1:
perimeter -= 2
return perimeterclass Solution {
public int islandPerimeter(int[][] grid) {
int rows = grid.length, cols = grid[0].length;
int perimeter = 0;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (grid[i][j] == 1) {
// Each land cell contributes 4 edges
perimeter += 4;
// Subtract 2 for shared edge with cell below
if (i + 1 < rows && grid[i + 1][j] == 1)
perimeter -= 2;
// Subtract 2 for shared edge with cell to the right
if (j + 1 < cols && grid[i][j + 1] == 1)
perimeter -= 2;
}
}
}
return perimeter;
}
}Complexity Analysis
Time Complexity: O(m × n)
We iterate through every cell in the grid exactly once. For each cell, we perform at most 3 constant-time operations: check if it is land, check the cell below, and check the cell to the right. Total work: O(m × n).
This is the same time complexity as the DFS approach, but the constant factor is smaller because we avoid the overhead of recursive function calls and visited-set lookups.
Space Complexity: O(1)
We use only a single integer variable (perimeter) regardless of grid size. No visited array, no recursion stack, no hash set. This is the key advantage over the DFS approach, which required O(m × n) extra space.