Island Perimeter

To solve this coding challenge, we need to determine the perimeter of an island represented in a grid. The grid consists of cells that can either be land (1) or water (0). The island is surrounded by water and does not have any internal "lakes". The main idea to calculate the perimeter involves the following steps:
  1. Iterate through each cell in the grid.
  2. For each land cell found (value of 1), initially assume it contributes 4 to the perimeter.
  3. Deduct 2 for each neighboring land cell to account for shared edges, which should not count twice in the perimeter calculation.
  4. Explanation

    To determine the perimeter, consider that each land cell without any neighbouring land contributes a perimeter of 4. However, when land cells are adjacent (horizontally or vertically), they share edges, which reduces the total perimeter necessary. Therefore, for each land cell:
  5. Start by adding 4 to the perimeter.
  6. Subtract 2 from the perimeter for each adjacent land cell to avoid double-counting shared edges.
  7. Detailed Steps in Pseudocode:
  8. Initialize a variable
    perimeter
    to store the total perimeter.
  9. Loop through each cell in the grid using two nested loops:
    • The outer loop iterates over rows.
    • The inner loop iterates over columns.
  10. Check if the current cell is land (i.e.,
    grid[i][j] == 1
    ):
    • If true, add 4 to the perimeter.
    • Check above (i-1) and left (j-1) for neighboring land cells:
      • If the cell above is land, subtract 2 from the perimeter.
      • If the cell to the left is land, subtract 2 from the perimeter.
  11. After completing the loops, the variable
    perimeter
    contains the calculated perimeter of the island.
Let’s define this solution in pseudocode:
                                            
# Initialize perimeter counter
perimeter = 0

# Iterate over each cell in the grid
for row_index in range(length of grid):
    for col_index in range(length of grid[0]):
        
        # Check if current cell is land
        if grid[row_index][col_index] == 1:
            # Add 4 for the current land cell
            perimeter += 4
            
            # Check for land cell above the current cell
            if row_index > 0 and grid[row_index - 1][col_index] == 1:
                # Subtract 2 for the shared edge with the cell above
                perimeter -= 2
            
            # Check for land cell to the left of the current cell
            if col_index > 0 and grid[row_index][col_index - 1] == 1:
                # Subtract 2 for the shared edge with the cell to the left
                perimeter -= 2

# Return the computed perimeter
return perimeter

                                        
In summary, this pseudocode starts by initializing the perimeter counter to zero. It then iterates through each cell in the grid, and for each land cell, it adds 4 to the perimeter. If there is adjacent land either above or to the left, it subtracts 2 from the perimeter for each adjacency, effectively avoiding double-counting shared edges. Finally, it returns the computed perimeter.