Solution: Island Perimeter

Let’s solve the Island Perimeter problem using the Matrices pattern.

We'll cover the following

Statement

You are given a grid with dimensions row x col, where each cell represents either land (grid[i][j] = 1) or water (grid[i][j] = 0). The grid satisfies the following conditions:

  • Cells are connected only horizontally or vertically (not diagonally).

  • The grid is surrounded by water and contains exactly one island, consisting of one or more connected land cells.

  • The island has no lakes, meaning no water is enclosed within the island that connects to the surrounding water.

  • The grid is rectangular, and each cell is a square with a side length 1.

Your task is to calculate the perimeter of the island.

Constraints:

  • row ==== grid.length

  • col ==== grid[i].length

  • 1≤1\leq row, col ≤100\leq100

  • grid[i][j] is 00 or 11.

  • There is exactly one island in grid.

Solution

Each cell in the grid has a default perimeter of 4 as four edges surround it. However, when two land cells are adjacent (sharing an edge), each side where they touch reduces the perimeter by 2, as that edge no longer contributes to the island’s outer perimeter.

The steps of the algorithm are as follows:

  1. Initialize the variable’s rows and cols to store the dimensions of the grid.

  2. A variable perimeter is initialized to 0 and will accumulate the total perimeter as the grid is processed.

  3. Iterate through each row and column in the grid to process every cell:

    1. For each cell grid[r][c], if it’s equal to 1 (indicating land), add 4 to perimeter (assuming initially that this land cell is isolated).

    2. Check for adjacent land cells. We only check the top and left cells because the algorithm sequentially processes the grid row by row. When we process a cell, adjacent cells above it or to its left have already been visited.

      1. If another land cell is directly above the current cell, the top edge of the current cell is shared with the cell above it. So, we reduce the perimeter by 2 (remove the shared edge).

      2. If another land cell is directly to the left of the current cell, the left edge of the current cell is shared with the cell on its left. Again, reduce the perimeter by 2.

  4. After iterating through all cells, perimeter contains the total perimeter of the island, which is returned as the output.

Let’s look at the following illustration to get a better understanding of the solution:

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.