Island Perimeter Finder

Island Perimeter Finder

January 14, 2024
medium
graph, DFS

Problem #

You are given a 2D grid map of '1's (land) and '0's (water). An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are surrounded by water. Write an algorithm to find the perimeter of the island in the grid. If there are multiple islands, calculate the perimeter of the largest one.

Example: #

Input:

111
110
000

Output: 8

Solution Approach: #

The solution involves iterating over each cell in the grid. When a land cell ('1') is found, its contribution to the perimeter is calculated based on the number of its adjacent water cells. To optimize, we can also track the largest island size while iterating and calculate the perimeter only for the largest island.

Algorithm Steps: #

  1. Initialize a variable to keep track of the maximum island size and a variable for the current island size.
  2. Iterate over each cell in the grid.
    • If the cell is land ('1'), perform a Depth-First Search (DFS) or Breadth-First Search (BFS) to calculate the size of the island and its perimeter.
    • During DFS/BFS, for each land cell, calculate the number of adjacent water cells and add it to the perimeter.
    • Update the maximum island size if the current island size is greater.
  3. Return the perimeter of the largest island.

Code: # 

def islandPerimeter(grid):
    rows, cols = len(grid), len(grid[0])
    visited = set()

    def dfs(r, c):
        if (r, c) in visited or r < 0 or c < 0 or r >= rows or c >= cols or grid[r][c] == 0:
            return 1 if r >= 0 and c >= 0 and r < rows and c < cols else 0
        visited.add((r, c))
        perimeter = dfs(r + 1, c) + dfs(r - 1, c) + dfs(r, c + 1) + dfs(r, c - 1)
        return perimeter

    max_perimeter = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 1 and (r, c) not in visited:
                max_perimeter = max(max_perimeter, dfs(r, c))

    return max_perimeter

# Example usage
print(islandPerimeter([[1,1,1],[1,1,0],[0,0,0]]))  # Output: 8

Space Complexity: #

The space complexity is O(R*C) in the worst case due to the recursion stack in DFS, where R is the number of rows and C is the number of columns in the grid.