Leetcode 463 - Island Perimeter

Problem Description

You are given row x col grid representing a map where grid[i][j] = 1 represents land and grid[i][j] = 0 represents water.

Grid cells are connected horizontally/vertically (not diagonally). The grid is completely surrounded by water, and there is exactly one island (i.e., one or more connected land cells).

The island doesn't have "lakes", meaning the water inside isn't connected to the water around the island. One cell is a square with side length 1. The grid is rectangular, width and height don't exceed 100. Determine the perimeter of the island.

Examples

Example 1:

Input:

grid = [
    [0,1,0,0],
    [1,1,1,0],
    [0,1,0,0],
    [1,1,0,0]
    ]

Output: 16

Example 2:

Input: grid = [[1]] Output: 4

Example 3:

Input: grid = [[1,0]] Output: 4

Intuition

I noticed that the perimeter of an island cell is 4, but if there is an island next to it, the perimeter of that cell is reduced by 1. So, for each cell, I counted the number of edges it had where it was connected to another island and subtracted that from 4 to get the perimeter of that cell. I then summed up the perimeters of all the cells to get the total perimeter of the island.

The faster way to do this would be to count the number of islands and the number of neighbours each island has. The number of neighbours would be the number of edges that are shared between two islands. The total perimeter would be the sum of the number of islands times 4 minus the number of neighbours times 2.

Approach

1. Create a helper function count_edges that takes in the row and column of a cell.
2. Inside the helper function, intialize the count to 4
3. Iterate through the four directions (up, down, left, right) and check if the cell in that direction is an island. If it is, decrement the count by 1.
4. Initialize a total (perimeter) variable to 0.
5. Iterate through the grid and for each cell that is an island, call the count_edges function and add the result to the total perimeter.

Solution

class Solution:
    def islandPerimeter(self, grid: List[List[int]]) -> int:
        def count_edges(r, c):
            count = 4
            for direction in [-1, 1]:
                if (r + direction >= n_rows or r + direction < 0) and (c + direction >= n_columns or c + direction < 0):
                    continue
                if r + direction >= n_rows or r + direction < 0:
                    if grid[r][c + direction] == 1:
                        count -= 1
                    continue
                if c + direction >= n_columns or c + direction < 0:
                    if grid[r + direction][c] == 1:
                        count -= 1
                    continue
                if grid[r + direction][c] == 1:
                    count -= 1
                if grid[r][c + direction] == 1:
                    count -= 1
            return count
        n_rows = len(grid)
        n_columns = len(grid[0])
        total = 0
        for i in range(n_rows):
            for j in range(n_columns):
                if grid[i][j] == 1:
                    total += count_edges(i, j)
        return total

Complexity Analysis

Time complexity: $O(m * n)$

• The time complexity is $O(m * n)$, where m is the number of rows and n is the number of columns in the grid.
• We iterate through each cell in the grid once to calculate the perimeter of the island.
• The helper function count_edges has a constant time complexity of $O(1)$ as it only checks the four directions from each cell.

Space complexity: $O(1)$

• The space complexity is $O(1)$ as we only use a constant amount of extra space for variables like count and total.

Shoutout to My Friends' Solutions

Kurt's Solution

Si Yuan's Solution