LeetCode 463 - Island Perimeter

The problem asks us to calculate the perimeter of an island represented in a 2D grid. Each cell in the grid is either land (1) or water (0). The island consists of one or more connected land cells, where connectivity is strictly horizontal or vertical.

leetcodeeasyarraydepth-first-searchbreadth-first-searchmatrix

LeetCode Problem 463

Difficulty: 🟢 Easy
Topics: Array, Depth-First Search, Breadth-First Search, Matrix

Solution

Problem Understanding

The problem asks us to calculate the perimeter of an island represented in a 2D grid. Each cell in the grid is either land (1) or water (0). The island consists of one or more connected land cells, where connectivity is strictly horizontal or vertical. The grid is completely surrounded by water, and there are no lakes, meaning any water cell that is completely enclosed by land does not exist. The output is a single integer representing the total perimeter of the island.

The key constraints are that the grid dimensions are small (up to 100x100), the grid contains exactly one island, and each cell is either land or water. These constraints mean we can afford an O(mn) solution, where m and n are the number of rows and columns. Important edge cases include very small grids, a single land cell, or land cells on the grid boundary. The problem guarantees that the island is continuous and fully connected, so we do not need to handle multiple disconnected land masses.

Approaches

A naive, brute-force approach would involve examining each land cell and checking all four sides to see if it borders water or is on the grid boundary. We would sum all sides that meet this condition. While this works, it requires checking each cell individually and its neighbors, resulting in repeated calculations and slightly redundant logic.

The key observation for an optimal solution is that each land cell contributes 4 to the perimeter minus 2 for each adjacent land cell. Instead of checking all cells multiple times, we can iterate through the grid once, and for each land cell, subtract 2 from the perimeter for each adjacent land cell that has already been counted (top and left neighbors suffice). This reduces repeated neighbor checking and keeps the logic clean, achieving O(mn) time complexity with minimal extra space.

Approach Time Complexity Space Complexity Notes
Brute Force O(mn) O(1) Check all four neighbors of every land cell
Optimal O(mn) O(1) Count 4 for each land cell and subtract 2 for each neighbor already processed

Algorithm Walkthrough

  1. Initialize a perimeter variable to zero. This will accumulate the total perimeter of the island.
  2. Iterate through each row i and column j of the grid.
  3. If the current cell grid[i][j] is land (1), start with a contribution of 4 to the perimeter.
  4. Check the cell above (i-1, j) and to the left (i, j-1). For each neighboring land cell, subtract 2 from the perimeter. We only need top and left because bottom and right will be checked in later iterations.
  5. Continue iterating until all cells have been processed.
  6. Return the final perimeter value.

Why it works: Each land cell initially contributes four sides, representing the maximum possible perimeter for that cell. For each shared side with an adjacent land cell already counted, we subtract two, once for the current cell and once implicitly for the neighbor, ensuring each shared edge is only counted once. This guarantees correctness.

Python Solution

from typing import List

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

The implementation iterates through the grid once. Each land cell contributes four sides, then we check only the top and left neighbors. If either neighbor is land, it means this side is shared, so we subtract 2. This approach avoids double-counting shared edges and ensures O(mn) time complexity without using extra space beyond a few counters.

Go Solution

func islandPerimeter(grid [][]int) int {
    perimeter := 0
    rows := len(grid)
    cols := len(grid[0])
    
    for i := 0; i < rows; i++ {
        for j := 0; j < cols; j++ {
            if grid[i][j] == 1 {
                perimeter += 4
                if i > 0 && grid[i-1][j] == 1 {
                    perimeter -= 2
                }
                if j > 0 && grid[i][j-1] == 1 {
                    perimeter -= 2
                }
            }
        }
    }
    
    return perimeter
}

The Go solution mirrors the Python implementation. Differences include using len(grid) to determine dimensions, zero-based for-loops instead of Python range, and explicitly managing integer addition. No extra slices or maps are required.

Worked Examples

Example 1:

Grid:

[[0,1,0,0],
 [1,1,1,0],
 [0,1,0,0],
 [1,1,0,0]]

Step by step:

i j grid[i][j] perimeter notes
0 1 1 4 no neighbors above/left
1 0 1 8 no neighbors above/left
1 1 1 12 neighbor above -> -2, left -> -2 => total perimeter now 12
1 2 1 16 left neighbor -> -2, top neighbor -> 0 (already subtracted)
2 1 1 18 top neighbor -> -2, left neighbor 0 => perimeter = 16
3 0 1 20 top neighbor 0, left neighbor 0
3 1 1 24 top neighbor -> -2, left neighbor -> -2 => perimeter = 20

Final perimeter = 16

Example 2: [[1]] → perimeter = 4

Example 3: [[1,0]] → perimeter = 4

Complexity Analysis

Measure Complexity Explanation
Time O(mn) We iterate through each cell once
Space O(1) Only a few integer variables are used, no extra data structures

The solution is efficient because each cell is processed exactly once, and neighbor checks are limited to two directions.

Test Cases

# test cases
assert Solution().islandPerimeter([[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]) == 16  # example 1
assert Solution().islandPerimeter([[1]]) == 4  # single cell
assert Solution().islandPerimeter([[1,0]]) == 4  # horizontal single row
assert Solution().islandPerimeter([[0,1]]) == 4  # horizontal single row, land at end
assert Solution().islandPerimeter([[1],[0]]) == 4  # vertical single column
assert Solution().islandPerimeter([[1,1],[1,1]]) == 8  # small square island
assert Solution().islandPerimeter([[0,0,0],[0,1,0],[0,0,0]]) == 4  # land surrounded by water
Test Why
example 1 tests general multiple-cell island
single cell smallest possible island
horizontal single row island at start or end of row
vertical single column island at top or bottom of column
small square island with all neighbors filled
surrounded by water island not touching edges

Edge Cases

The first edge case is a single land cell in a grid, which could be at the edge or center. The perimeter must be 4, and our neighbor check ensures no subtraction occurs since no adjacent cells exist.

The second edge case is a line of land cells, either horizontal or vertical. Each cell in the middle shares two sides with neighbors, and the subtraction of 2 for each adjacent cell ensures the perimeter is calculated correctly.

The third edge case is an island that touches the boundaries of the grid. Our implementation correctly handles i == 0 or j == 0 without attempting to access negative indices, preventing out-of-bounds errors.

This approach handles all guaranteed input conditions efficiently and correctly.