Matrix Island Perimeter

February 25, 2024

Problem Statement: #

Given a 2D grid of 0s and 1s, where 1 represents land and 0 represents water, find the perimeter of the island. The grid cells are connected horizontally/vertically (not diagonally). There is exactly one island, and it doesn’t have lakes (water inside that isn’t connected to the water around the island). The grid is surrounded by water, and there is exactly one island (i.e., one or more connected land cells).

Example: #

• 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 sides of the 1s in the diagram.

Solution Approach: #

The solution involves iterating over each cell in the grid and, for each cell that is land (1), adding to the perimeter for each side of the cell that is adjacent to water (0) or is on the edge of the grid.

Algorithm Steps: #

1. Iterate through each cell of the grid.
2. If the cell is land (1):
   • Check all four directions (up, down, left, right) from the cell.
   • For each direction, if the adjacent cell is water (0) or it is outside the grid (edge of the grid), add 1 to the perimeter count.
3. Return the total perimeter count after the entire grid has been processed.

Code: #

def islandPerimeter(grid):
    rows, cols = len(grid), len(grid[0])
    perimeter = 0
    
    def isWaterOrEdge(r, c):
        # Check if the current cell is out of bounds or water.
        return r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] == 0
        
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 1:
                # Check all four sides for water or edge.
                if isWaterOrEdge(r-1, c): perimeter += 1
                if isWaterOrEdge(r+1, c): perimeter += 1
                if isWaterOrEdge(r, c-1): perimeter += 1
                if isWaterOrEdge(r, c+1): perimeter += 1
                
    return perimeter

# Example usage
grid = [
  [0, 1, 0, 0],
  [1, 1, 1, 0],
  [0, 1, 0, 0],
  [1, 1, 0, 0]
]
print(islandPerimeter(grid))

Time Complexity: #

• O(N*M): Where N is the number of rows and M is the number of columns in the grid. Each cell is visited exactly once.

Space Complexity: #

• O(1): Constant space is used, except for the input grid itself. No additional data structures are required for computation.