Island Perimeter - Leetcode Solution

Problem Statement:

You are given a 2D grid of 1s (land) and 0s (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 all surrounded by water.

Calculate the perimeter of the island.

Solution:

A simple approach to solve this problem is to count the number of edges on the boundary of the island. To do that, we can traverse the entire grid and check if the current cell is a land cell. If it is a land cell, we would increment the perimeter count by the number of adjacent water cells (top, bottom, left, right) since each water cell forms an edge with the current land cell. Here is the detailed solution:

1. Initialize a variable perimeter to 0.
2. Traverse the entire grid and for each cell, do the following: a. If the current cell is a land cell, check its adjacent cells to see if they are water cells. b. If an adjacent cell is a water cell (or if the current cell is at the boundary of the grid), increment the perimeter count by 1.
3. Return the perimeter count.

Here is the Python implementation of the above solution:

class Solution:
    def islandPerimeter(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        perimeter = 0
        
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    # check left
                    if j == 0 or grid[i][j-1] == 0:
                        perimeter += 1
                    # check right
                    if j == n-1 or grid[i][j+1] == 0:
                        perimeter += 1
                    # check top
                    if i == 0 or grid[i-1][j] == 0:
                        perimeter += 1
                    # check bottom
                    if i == m-1 or grid[i+1][j] == 0:
                        perimeter += 1
        
        return perimeter

Time Complexity: O(mn) where m and n are the dimensions of the grid

Space Complexity: O(1) as we are not using any extra space.

The above solution gave a runtime faster than 86% solutions on LeetCode and space usage lesser than 96% of solutions.

1