#463

Easy

auto_awesomeArray plus Depth-First Search

LeetCode Problem Workspace

Island Perimeter

Determine the perimeter of an island in a grid of land and water cells using DFS or BFS.

array depth first search breadth first search matrix

Problem Statement

You are given a grid of size row x col, where each cell is either water (0) or land (1). The grid contains exactly one island, and it is surrounded entirely by water. The task is to compute the perimeter of the island, which is determined by the number of land cell edges that are adjacent to water or the grid boundary.

The grid is rectangular, with row and column lengths not exceeding 100. You are to compute the perimeter of the island, considering only the connected land cells that do not form lakes inside the island. Cells are connected horizontally and vertically, not diagonally.

Examples

Example 1

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

Output: 16

The perimeter is the 16 yellow stripes in the image above.

Example 2

Input: grid = [[1]]

Output: 4

Example details omitted.

Example 3

Input: grid = [[1,0]]

Output: 4

Example details omitted.

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.

Solution Approach

DFS Approach

Use Depth-First Search (DFS) to traverse the grid and explore each land cell. For each land cell, check its four neighboring cells (up, down, left, right). If a neighboring cell is either water (0) or out of bounds, it contributes to the perimeter. The DFS ensures all connected land cells are explored.

BFS Approach

Alternatively, you can use Breadth-First Search (BFS) to explore the grid. This approach processes each land cell in layers, and for each land cell, its neighboring water cells or grid boundaries contribute to the perimeter. BFS ensures all land cells are processed systematically.

Perimeter Calculation

Regardless of whether you use DFS or BFS, each land cell has at most four edges that might contribute to the perimeter. For each land cell, check all four possible directions to see if it is adjacent to water or the grid boundary. Count the contributing edges to compute the total perimeter.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the method used. Both DFS and BFS have a time complexity of O(row * col), where row and col are the dimensions of the grid. The space complexity also depends on the approach, with DFS having O(row * col) due to recursion stack depth, while BFS requires O(row * col) space for the queue.

What Interviewers Usually Probe

Look for the candidate’s ability to efficiently implement DFS or BFS on a grid.
Pay attention to their handling of boundary conditions and grid traversal.
Check for optimizations, such as early termination or pruning in the search algorithms.

Common Pitfalls or Variants

Common pitfalls

Not handling grid boundaries correctly, which might cause index errors or incorrect perimeter calculation.
Failing to account for the fact that only water cells or boundaries contribute to the perimeter.
Misunderstanding the concept of a single island, leading to incorrect grid exploration.

Follow-up variants

What if the grid contains multiple disconnected islands? (The problem specifies exactly one island.)
How would the solution change if the grid had diagonal connectivity?
Can this problem be solved in O(1) space?

FAQ

What is the best way to solve the Island Perimeter problem?

Using DFS or BFS to traverse the grid, checking each land cell’s neighbors to determine if they contribute to the perimeter.

What are the key concepts to focus on for the Island Perimeter problem?

Focus on Depth-First Search or Breadth-First Search for grid traversal and properly counting the edges contributing to the perimeter.

How can I optimize the space complexity in the Island Perimeter problem?

Optimizing space can be achieved by using BFS with a queue or DFS with an iterative stack instead of recursion to reduce the recursion stack depth.

Does the grid always contain one island in the Island Perimeter problem?

Yes, the problem guarantees exactly one island in the grid, which simplifies the traversal process.

What if the grid has a diagonal connection between land cells?

The current problem does not allow diagonal connections; only horizontal and vertical connections between land cells are considered.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def islandPerimeter(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        ans = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    ans += 4
                    if i < m - 1 and grid[i + 1][j] == 1:
                        ans -= 2
                    if j < n - 1 and grid[i][j + 1] == 1:
                        ans -= 2
        return ans

Continue Practicing

#417 pacific atlantic water flow #529 minesweeper #329 longest increasing path in a matrix