Watch 10 video solutions for Island Perimeter, a easy level problem involving Array, Depth-First Search, Breadth-First Search. This walkthrough by NeetCode has 56,744 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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). The grid is completely surrounded by water, and there is exactly one island (i.e., one or more connected land cells).
The island doesn't have "lakes", meaning the water inside isn't connected to the water around the island. One cell is a square with side length 1. The grid is rectangular, width and height don't exceed 100. Determine the perimeter of the island.
Example 1:
Input: grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]] Output: 16 Explanation: The perimeter is the 16 yellow stripes in the image above.
Example 2:
Input: grid = [[1]] Output: 4
Example 3:
Input: grid = [[1,0]] Output: 4
Constraints:
row == grid.lengthcol == grid[i].length1 <= row, col <= 100grid[i][j] is 0 or 1.grid.Problem Overview: You receive an m x n binary grid where 1 represents land and 0 represents water. The grid contains exactly one island (connected horizontally or vertically). The task is to calculate the total perimeter of that island by counting the edges where land touches water or the grid boundary.
Approach 1: Iterative Grid Enumeration (O(m*n) time, O(1) space)
Scan every cell in the grid. Each land cell contributes up to four edges to the perimeter. For every grid[i][j] == 1, start with +4 edges, then subtract edges shared with neighboring land cells. Checking the top and left neighbors avoids double counting shared edges. The key insight: every adjacent land pair removes two perimeter edges. This approach relies on simple iteration across the array representing the grid and constant-time neighbor checks.
Approach 2: Depth-First Search (DFS) (O(m*n) time, O(m*n) space)
Start a DFS from the first land cell and explore the entire island using recursion. Whenever the DFS reaches water or goes out of bounds, that edge contributes +1 to the perimeter. If a land cell is already visited, return 0 because its edges were counted earlier. This approach treats the island as a connected component in a matrix and traverses it using depth-first search. It is conceptually clean because each recursive step directly models an edge check around the island boundary.
Recommended for interviews: Iterative grid enumeration is the expected solution. It runs in O(m*n) time with O(1) space and requires only simple neighbor checks. DFS also works and demonstrates strong graph traversal knowledge, but interviewers typically prefer the enumeration approach because it avoids recursion overhead and is easier to reason about during implementation.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Grid Enumeration | O(m*n) | O(1) | Best general solution. Simple iteration with neighbor checks and constant memory. |
| Depth-First Search (DFS) | O(m*n) | O(m*n) | Useful when treating the grid as a graph and exploring connected components. |