Island Perimeter
EasyPrompt
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: 4Example 3:
Input: grid = [[1,0]]
Output: 4
Constraints:
row == grid.lengthcol == grid[i].length1 <= row, col <= 100grid[i][j]is0or1.- There is exactly one island in
grid.
Approaches
2 approaches with complexity analysis and trade-offs.
This straightforward approach iterates through every cell of the grid. For each land cell, it checks its four neighbors (up, down, left, right). If a neighbor is a water cell or is outside the grid boundary, it contributes one unit to the total perimeter.
Algorithm
- Initialize a variable
perimeterto 0. - Get the dimensions of the grid,
rowsandcols. - Iterate through each cell of the grid using nested loops, with
rfrom0torows-1andcfrom0tocols-1. - If the current cell
grid[r][c]is a land cell (value1):- Check the cell above: If
ris0(top boundary) orgrid[r-1][c]is0(water), incrementperimeter. - Check the cell below: If
risrows-1(bottom boundary) orgrid[r+1][c]is0, incrementperimeter. - Check the cell to the left: If
cis0(left boundary) orgrid[r][c-1]is0, incrementperimeter. - Check the cell to the right: If
ciscols-1(right boundary) orgrid[r][c+1]is0, incrementperimeter.
- Check the cell above: If
- After iterating through all cells, return the final
perimetervalue.
Walkthrough
The algorithm initializes a perimeter count to zero. It then scans the entire grid cell by cell. When it finds a land cell (value 1), it directly counts the exposed sides. For a land cell at (r, c), we check its top, bottom, left, and right sides. A side is exposed and contributes to the perimeter if the adjacent cell in that direction is either water (0) or off the grid. We sum these contributions for all land cells to get the final perimeter.
class Solution { public int islandPerimeter(int[][] grid) { if (grid == null || grid.length == 0 || grid[0].length == 0) { return 0; } int perimeter = 0; int rows = grid.length; int cols = grid[0].length; for (int r = 0; r < rows; r++) { for (int c = 0; c < cols; c++) { if (grid[r][c] == 1) { // Check top if (r == 0 || grid[r - 1][c] == 0) { perimeter++; } // Check bottom if (r == rows - 1 || grid[r + 1][c] == 0) { perimeter++; } // Check left if (c == 0 || grid[r][c - 1] == 0) { perimeter++; } // Check right if (c == cols - 1 || grid[r][c + 1] == 0) { perimeter++; } } } } return perimeter; }}Complexity
Time
O(R * C), where R is the number of rows and C is the number of columns. We must visit every cell in the grid.
Space
O(1), as no extra space proportional to the input size is used.
Trade-offs
Pros
Very intuitive and easy to understand.
Directly models the definition of a perimeter in this context.
Cons
Performs more checks than necessary. For each land cell, it looks at all four neighbors, leading to redundant considerations of shared borders.
This is a more efficient approach that avoids redundant checks. The core idea is that each land cell contributes 4 to the perimeter, and each shared border between two adjacent land cells subtracts 2 from the total. By iterating through the grid and only counting neighbors in two directions (e.g., right and down), we can calculate the total perimeter efficiently.
Algorithm
- Initialize
landCells = 0andsharedBorders = 0. - Get the grid dimensions
rowsandcols. - Loop through each row
rfrom0torows - 1. - Loop through each column
cfrom0tocols - 1. - If
grid[r][c]is1(land):- Increment
landCells. - Check Right: If
c + 1 < colsandgrid[r][c+1]is1, incrementsharedBorders. - Check Down: If
r + 1 < rowsandgrid[r+1][c]is1, incrementsharedBorders.
- Increment
- Return the result of the formula
landCells * 4 - sharedBorders * 2.
Walkthrough
The logic behind this approach is that each land cell initially contributes 4 sides to the perimeter. However, whenever two land cells are adjacent, they share a border. This shared border is internal to the island and should not be part of the perimeter. Since each shared border involves two cells, it removes two sides from the total potential perimeter (one from each cell). To implement this, we iterate through the grid once. We count the total number of land cells. To avoid double-counting shared borders, we only check for adjacent land cells in two directions from each cell: to the right and down. After iterating through the grid, we apply the formula (total land cells * 4) - (total shared borders * 2) to get the final result.
class Solution { public int islandPerimeter(int[][] grid) { if (grid == null || grid.length == 0 || grid[0].length == 0) { return 0; } int landCells = 0; int sharedBorders = 0; int rows = grid.length; int cols = grid[0].length; for (int r = 0; r < rows; r++) { for (int c = 0; c < cols; c++) { if (grid[r][c] == 1) { landCells++; // Count shared border with the right neighbor if (c < cols - 1 && grid[r][c + 1] == 1) { sharedBorders++; } // Count shared border with the bottom neighbor if (r < rows - 1 && grid[r + 1][c] == 1) { sharedBorders++; } } } } return landCells * 4 - sharedBorders * 2; }}Complexity
Time
O(R * C), where R is the number of rows and C is the number of columns. The grid is traversed once.
Space
O(1), as only a few variables are used for counting.
Trade-offs
Pros
More efficient in practice due to fewer checks per cell (at most 2 neighbor checks instead of 4).
Avoids redundant computations by counting each shared border only once.
Elegant mathematical formulation.
Cons
The logic might be slightly less direct to grasp initially compared to the brute-force method.
Solutions
Solution
class Solution {public int islandPerimeter(int[][] grid) { int ans = 0; int m = grid.length; int n = grid[0].length; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (grid[i][j] == 1) { ans += 4; if (i < m - 1 && grid[i + 1][j] == 1) { ans -= 2; } if (j < n - 1 && grid[i][j + 1] == 1) { ans -= 2; } } } } return ans; }}class Solution {public: int islandPerimeter(vector<vector<int>> &grid) { int m = grid.size(), n = grid[0].size(); int ans = 0; for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { if (grid[i][j] == 1) { ans += 4; if (i < m - 1 && grid[i + 1][j] == 1) ans -= 2; if (j < n - 1 && grid[i][j + 1] == 1) ans -= 2; } } } return ans; }};class Solution: def islandPerimeter(self, grid: List[List[int]]) -> int: m, n = len(grid), len(grid[0]) ans = 0 for i in range(m): for j in range(n): if grid[i][j] == 1: ans += 4 if i < m - 1 and grid[i + 1][j] == 1: ans -= 2 if j < n - 1 and grid[i][j + 1] == 1: ans -= 2 return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.