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.
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; }}Video 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.