Leetcode – Island Perimeter Solution in Python

The Island Perimeter problem is a classic algorithm problem that can be found on Leetcode. This problem is a good example of grid traversal and can be solved using different approaches. In this article, we will discuss the problem in detail and walk through various solutions in Python.

Problem Statement:

You are given a 2D array grid of 0‘s (water) and 1‘s (land). An island is a group of 1‘s (representing land) that are connected either horizontally or vertically. You can assume all four edges of the grid are surrounded by water.

Calculate the perimeter of the island.

Example:

Input:
[[0, 0, 1, 0],
 [1, 1, 1, 0],
 [0, 1, 0, 0],
 [1, 1, 0, 0]]

Output: 16

Intuitive Approach:

Before delving into the efficient algorithms, let’s discuss a brute-force approach to get a better understanding of the problem.

We can iterate through each cell in the grid. For every land cell, we can check its four neighbors (up, down, left, and right). If a neighbor is water or beyond the grid, it means this side contributes to the perimeter.

Here is the Python code for this approach:

def islandPerimeter(grid):
    if not grid:
        return 0
    
    rows, cols = len(grid), len(grid[0])
    perimeter = 0

    for i in range(rows):
        for j in range(cols):
            if grid[i][j] == 1:
                # Check the four neighbors
                for x, y in [(i-1, j), (i+1, j), (i, j-1), (i, j+1)]:
                    if x < 0 or x >= rows or y < 0 or y >= cols or grid[x][y] == 0:
                        perimeter += 1
    return perimeter

However, this approach is not very efficient as it checks all the neighbors for each land cell, leading to some redundancy.

Optimized Approach:

We can optimize the brute-force approach by realizing that every time we find a land cell, it must have contributed at least one side to the perimeter (unless it is completely surrounded by other land cells).

Additionally, every time a land cell has another adjacent land cell, it reduces the perimeter by 2 (one for each of the two adjacent cells). Therefore, for each land cell, we can add 4 to the perimeter count and then subtract 2 for each adjacent land cell.

def islandPerimeter(grid):
    if not grid:
        return 0
    
    rows, cols = len(grid), len(grid[0])
    perimeter = 0

    for i in range(rows):
        for j in range(cols):
            if grid[i][j] == 1:
                perimeter += 4
                
                # Check the left and upper neighbor
                if i > 0 and grid[i-1][j] == 1:
                    perimeter -= 2
                if j > 0 and grid[i][j-1] == 1:
                    perimeter -= 2
                    
    return perimeter

This optimized approach still traverses the entire grid but performs fewer checks for neighbors, which makes it more efficient.

Using Depth-First Search (DFS):

We can also solve this problem using a DFS algorithm. We traverse the grid, and each time we encounter a land cell, we perform a DFS traversal to visit all the connected land cells. For each land cell encountered during the DFS, we calculate the contribution to the perimeter.

def islandPerimeter(grid):
    if not grid:
        return 0
    
    rows, cols = len(grid), len(grid[0])

    def dfs(i, j):
        if i < 0 or i >= rows or j < 0 or j >= cols:
            return 1
        if grid[i][j] == 0:
            return 1
        if grid[i][j] == -1:
            return 0
        
        # Mark the cell as visited
        grid[i][j] = -1
        
        perimeter = 0
        # Check the four neighbors
        for x, y in [(i-1, j), (i+1, j), (i, j-1), (i, j+1)]:
            perimeter += dfs(x, y)
        
        return perimeter

    # Start DFS from the first land cell encountered
    for i in range(rows):
        for j in range(cols):
            if grid[i][j] == 1:
                return dfs(i, j)
    return 0

This DFS approach has the same time complexity as the previous methods but provides a different perspective on solving the problem.

Conclusion:

The Island Perimeter problem is a popular algorithm problem that requires analyzing a 2D grid. It can be solved using various approaches such as brute-force, optimization using an intuitive insight, and Depth-First Search. Each approach has its own educational value and provides different insights into grid traversal problems. It is recommended to understand and practice each of these methods to develop versatility in solving such problems.