Code Implementation

class Solution:
    def islandPerimeter(self, grid: List[List[int]]) -> int:
        rows = len(grid)
        cols = len(grid[0])
        perimeter = 0

        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == 1:
                    # Each land cell has 4 sides, subtract sides shared with other land
                    perimeter += 4
                    if r > 0 and grid[r-1][c] == 1:
                        perimeter -= 2  # shared with top neighbor
                    if c > 0 and grid[r][c-1] == 1:
                        perimeter -= 2  # shared with left neighbor
        return perimeter
      

class Solution {
public:
    int islandPerimeter(vector<vector<int>>& grid) {
        int rows = grid.size();
        int cols = grid[0].size();
        int perimeter = 0;
        for (int r = 0; r < rows; ++r) {
            for (int c = 0; c < cols; ++c) {
                if (grid[r][c] == 1) {
                    perimeter += 4;
                    if (r > 0 && grid[r-1][c] == 1)
                        perimeter -= 2;
                    if (c > 0 && grid[r][c-1] == 1)
                        perimeter -= 2;
                }
            }
        }
        return perimeter;
    }
};
      

class Solution {
    public int islandPerimeter(int[][] grid) {
        int rows = grid.length;
        int cols = grid[0].length;
        int perimeter = 0;
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == 1) {
                    perimeter += 4;
                    if (r > 0 && grid[r-1][c] == 1)
                        perimeter -= 2;
                    if (c > 0 && grid[r][c-1] == 1)
                        perimeter -= 2;
                }
            }
        }
        return perimeter;
    }
}
      

var islandPerimeter = function(grid) {
    let rows = grid.length;
    let cols = grid[0].length;
    let perimeter = 0;
    for (let r = 0; r < rows; r++) {
        for (let c = 0; c < cols; c++) {
            if (grid[r][c] === 1) {
                perimeter += 4;
                if (r > 0 && grid[r-1][c] === 1)
                    perimeter -= 2;
                if (c > 0 && grid[r][c-1] === 1)
                    perimeter -= 2;
            }
        }
    }
    return perimeter;
};
      

Problem Description

You are given a 2D grid map where each cell is either land (1) or water (0). The grid represents a map containing exactly one island (a group of connected lands), with no lakes (water inside that isn't connected to the water around the island). The island is surrounded by water, and there are no diagonally connected lands (only horizontal or vertical connections are valid).

Your task is to compute the perimeter of the island. The perimeter is defined as the total length of the island's boundary—the number of edges that are adjacent to water or the grid boundary.

Constraints:

• There is exactly one island.
• The island does not contain any lakes.
• The island is made up of connected lands (horizontally or vertically).
• Input grid is rectangular (all rows have the same length).

Thought Process

At first glance, it might seem like we need to traverse the entire grid and check every possible edge of every land cell. The brute-force way would be to look at every land cell and, for each of its four sides, check if that side is either at the edge of the grid or adjacent to water. If so, we count it as part of the perimeter.

However, we can optimize this process. Instead of checking all four neighbors for every land cell, we can notice that each land cell contributes 4 edges to the perimeter. But whenever two land cells are adjacent (either vertically or horizontally), they share an edge, which means we count that edge twice if we just sum 4 for every cell. So, for every shared edge, we need to subtract 2 from the total perimeter (since both cells would have counted it once).

Therefore, by only checking the top and left neighbors for each land cell (to avoid double counting), we can efficiently compute the perimeter in a single pass through the grid.

Solution Approach

Let's break down the steps to solve the problem efficiently:

1. Initialize a perimeter variable to 0.
2. Iterate through each cell in the grid using nested loops (for rows and columns).
3. For each land cell (1):
   • Add 4 to the perimeter (since it has 4 sides).
   • Check the cell above (if it exists and is also land). If so, subtract 2 from the perimeter (since the top edge is shared).
   • Check the cell to the left (if it exists and is also land). If so, subtract 2 from the perimeter (since the left edge is shared).
4. Return the final perimeter value after finishing the iteration.

This approach ensures we only count each shared edge once, and we don't double-count any boundaries.

Example Walkthrough

Let's use the following grid as an example:

    grid = [
      [0,1,0,0],
      [1,1,1,0],
      [0,1,0,0],
      [1,1,0,0]
    ]
  

Let's walk through the algorithm:

• Start with perimeter = 0
• For each cell, check if it's land (1):
  • For cell (0,1): It's land. Add 4 (perimeter = 4). No top or left neighbors to subtract.
  • For cell (1,0): It's land. Add 4 (perimeter = 8). No top or left neighbors to subtract.
  • For cell (1,1): It's land. Add 4 (perimeter = 12). Top neighbor (0,1) is land, subtract 2 (perimeter = 10). Left neighbor (1,0) is land, subtract 2 (perimeter = 8).
  • For cell (1,2): It's land. Add 4 (perimeter = 12). Left neighbor (1,1) is land, subtract 2 (perimeter = 10).
  • For cell (2,1): It's land. Add 4 (perimeter = 14). Top neighbor (1,1) is land, subtract 2 (perimeter = 12).
  • For cell (3,0): It's land. Add 4 (perimeter = 16). No top or left neighbors to subtract.
  • For cell (3,1): It's land. Add 4 (perimeter = 20). Left neighbor (3,0) is land, subtract 2 (perimeter = 18). Top neighbor (2,1) is land, subtract 2 (perimeter = 16).
• All other cells are water, so we skip them.

The final perimeter is 16.

Time and Space Complexity

• Brute-force approach: For each land cell, check all four neighbors (up, down, left, right), leading to O(4*N*M) = O(N*M) time, where N and M are the number of rows and columns.
• Optimized approach (as above): We still visit every cell once and do constant work per cell, so the time complexity is O(N*M).
• Space complexity: We use only a constant amount of extra space (perimeter variable), so it's O(1).

Summary

The key to solving the Island Perimeter problem efficiently is to recognize that each land cell contributes 4 to the perimeter, but each shared edge between two lands should only be counted once (by subtracting 2 for each shared edge). By only checking the top and left neighbors for each land cell, we avoid double-counting and can compute the perimeter in a single pass. This approach is simple, efficient, and easy to understand, making it an elegant solution to the problem.