Island Perimeter

Problem Statement

In this challenge, you are provided with a grid, represented as a 2D array where each cell can be either land (1) or water (0). This grid forms a rectangular map, and each cell is directly connected to its adjacent cells horizontally or vertically but not diagonally. The entire grid is surrounded by water, ensuring there's a clear distinction between the edge of the island and the surrounding water.

Your task is to calculate the perimeter of the island within this grid. An island is defined as a group of connected land cells (1s) and it is guaranteed that there is exactly one such island in the given grid. This island does not contain any enclosed bodies of water ("lakes"). The perimeter is defined by the number of edges facing water or the grid boundary. You are to assume that each cell in the grid is a square with side length 1.

Examples

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.

Approach and Intuition

To determine the perimeter of the island described in the grid, you can follow these steps:

1. Traverse each cell of the grid.
2. For each land cell (1), check its surrounding cells (up, down, left, right).
   • If a surrounding cell is water (0) or it lies outside the boundary of the grid, it contributes 1 to the perimeter.
   • Otherwise, if the adjacent cell is also land (1), it does not add to the perimeter on that side.
3. Sum up the contributions from all sides of all land cells to get the total perimeter.

This approach checks each land cell's surroundings to account for edges that are adjacent to water or external boundaries, which essentially are boundary lines of the island. Examples provided illustrate how different configurations of the grid affect the calculation of the perimeter:

• In the first example, the arrangement of the cells creates multiple extensions and indentations, thereby lengthening the perimeter.
• In the second example, a single land cell on all sides is exposed to water, giving a straightforward perimeter of 4.
• The third example, similar to the second, has a single land cell alongside a water cell, also resulting in a perimeter of 4.

The constraints ensure that the perimeter calculation remains within computationally feasible limits, avoiding excessively large or complex grid structures. This method efficiently computes the island's perimeter using straightforward checks and accumulations based on the grid's immediate cellular environment.

Solutions

class Solution {
    public int calculateIslandPerimeter(int[][] grid) {
        int row_count = grid.length;
        int col_count = grid[0].length;
        
        int perimeter = 0;
        for (int row = 0; row < row_count; row++) {
            for (int col = 0; col < col_count; col++) {
                if (grid[row][col] == 1) {
                    perimeter += 4;
                    
                    if (row > 0 && grid[row-1][col] == 1) {
                        perimeter -= 2;
                    }
                    
                    if (col > 0 && grid[row][col-1] == 1) {
                        perimeter -= 2;
                    }
                }
            }
        }
        
        return perimeter;
    }
}

class Solution:
    def calculatePerimeter(self, matrix: List[List[int]]) -> int:
        height = len(matrix)
        width = len(matrix[0])
        
        perimeter = 0
        
        for i in range(height):
            for j in range(width):
                if matrix[i][j] == 1:
                    perimeter += 4
                    
                    if i > 0 and matrix[i-1][j] == 1:
                        perimeter -= 2
                        
                    if j > 0 and matrix[i][j-1] == 1:
                        perimeter -= 2
        
        return perimeter