Island Perimeter

Difficulty: Easy | Acceptance: 74.40% | Paid: No Topics: Array, Depth-First Search, Breadth-First Search, Matrix

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
• Constraints
• Iterative Counting
• Depth-First Search (DFS)
• Breadth-First Search (BFS)

Examples

Input: grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]
Output: 16
Explanation: The perimeter is the 16 yellow stripes in the image above.

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

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

Constraints

row == grid.length
col == grid[i].length
1 <= row, col <= 100
grid[i][j] is 0 or 1.
There is exactly one island in grid.

Iterative Counting

Intuition Every land cell contributes 4 sides to the perimeter. For every adjacent neighbor (up, down, left, right), we lose 2 sides (one from the current cell and one from the neighbor).

Steps

• Iterate through every cell in the grid.
• If the cell is land (1), add 4 to the perimeter.
• Check the top and left neighbors. If a neighbor is also land, subtract 2 from the perimeter (since the shared edge is not part of the perimeter).
• Return the total perimeter.

class Solution:
    def islandPerimeter(self, grid: list[list[int]]) -> int:
        rows = len(grid)
        cols = len(grid[0])
        perimeter = 0
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == 1:
                    perimeter += 4
                    if r > 0 and grid[r-1][c] == 1:
                        perimeter -= 2
                    if c > 0 and grid[r][c-1] == 1:
                        perimeter -= 2
        return perimeter

Complexity

• Time: O(m * n) where m is the number of rows and n is the number of columns.
• Space: O(1) as we only use a few variables for counting.
• Notes: This is the most optimal approach for this specific problem.

Depth-First Search (DFS)

Intuition We can traverse the island using DFS. For every land cell, we check its 4 boundaries. If a boundary is water or out of bounds, it contributes to the perimeter.

Steps

• Iterate through the grid to find the first land cell.
• Start a DFS from that cell.
• In the DFS function:
  • If the current cell is out of bounds or water, return 1 (this counts as a perimeter edge).
  • If the current cell is already visited (marked as 2), return 0.
  • Mark the current cell as visited (set to 2).
  • Recursively call DFS for all 4 neighbors and sum the results.
• Return the total sum.

class Solution:
    def islandPerimeter(self, grid: list[list[int]]) -> int:
        rows, cols = len(grid), len(grid[0])
        
        def dfs(r, c):
            if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] == 0:
                return 1
            if grid[r][c] == 2:
                return 0
            grid[r][c] = 2
            return dfs(r+1, c) + dfs(r-1, c) + dfs(r, c+1) + dfs(r, c-1)
        
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == 1:
                    return dfs(r, c)
        return 0

Complexity

• Time: O(m * n) where m is the number of rows and n is the number of columns.
• Space: O(m * n) in the worst case for the recursion stack (if the grid is all land).
• Notes: Modifies the input grid to mark visited cells.

Breadth-First Search (BFS)

Intuition Similar to DFS, we traverse the island level by level using a queue. We check boundaries for every cell we process.

Steps

• Iterate through the grid to find the first land cell.
• Add this cell to a queue and mark it as visited (set to 2).
• While the queue is not empty:
  • Dequeue a cell.
  • Check its 4 neighbors.
  • If a neighbor is out of bounds or water, increment perimeter.
  • If a neighbor is land and not visited, mark it as visited and enqueue it.
• Return the total perimeter.

from collections import deque

class Solution:
    def islandPerimeter(self, grid: list[list[int]]) -> int:
        rows, cols = len(grid), len(grid[0])
        queue = deque()
        perimeter = 0
        
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == 1:
                    queue.append((r, c))
                    grid[r][c] = 2
                    while queue:
                        cr, cc = queue.popleft()
                        for dr, dc in [(1,0), (-1,0), (0,1), (0,-1)]:
                            nr, nc = cr + dr, cc + dc
                            if nr < 0 or nr >= rows or nc < 0 or nc >= cols or grid[nr][nc] == 0:
                                perimeter += 1
                            elif grid[nr][nc] == 1:
                                queue.append((nr, nc))
                                grid[nr][nc] = 2
                    return perimeter
        return 0

Complexity

• Time: O(m * n) where m is the number of rows and n is the number of columns.
• Space: O(min(m, n)) for the queue in the worst case (for a diamond shape) or O(m * n) depending on the shape, though generally less than DFS stack depth for wide islands.
• Notes: Modifies the input grid to mark visited cells.