Island Perimeter

EASY

Description

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.length
col == grid[i].length
1 <= row, col <= 100
grid[i][j] is 0 or 1.
There is exactly one island in grid.

Approaches

Checkout 2 different approaches to solve Island Perimeter. Click on different approaches to view the approach and algorithm in detail.

Brute-Force Iteration

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 perimeter to 0.
Get the dimensions of the grid, rows and cols.
Iterate through each cell of the grid using nested loops, with r from 0 to rows-1 and c from 0 to cols-1.
If the current cell grid[r][c] is a land cell (value 1):
- Check the cell above: If r is 0 (top boundary) or grid[r-1][c] is 0 (water), increment perimeter.
- Check the cell below: If r is rows-1 (bottom boundary) or grid[r+1][c] is 0, increment perimeter.
- Check the cell to the left: If c is 0 (left boundary) or grid[r][c-1] is 0, increment perimeter.
- Check the cell to the right: If c is cols-1 (right boundary) or grid[r][c+1] is 0, increment perimeter.
After iterating through all cells, return the final perimeter value.

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 Analysis

Time Complexity: 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 Complexity: O(1), as no extra space proportional to the input size is used.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Island Perimeter. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Island Perimeter

Algorithms:

Depth-First SearchBreadth-First Search

Data Structures:

ArrayMatrix

Companies:

Cadence |