LeetCode 463: Island Perimeter Solution in Python – A Step-by-Step Guide

What Is LeetCode 463: Island Perimeter?

In LeetCode 463: Island Perimeter, you’re given a 2D grid grid where 1s represent land cells and 0s represent water cells, forming a single island (connected horizontally or vertically). Your task is to calculate the perimeter—the total number of edges of land cells that border water or the grid’s boundary. For example, in [[1,1], [1,1]], the perimeter is 8 (all edges are outer). It’s like measuring the shoreline of a pixelated island.

Problem Statement

• Input: grid (List[List[int]])—2D grid of 0s and 1s.
• Output: int—perimeter of the island.
• Rules:
• 1s form one island (4-directionally connected).
• Perimeter = edges bordering water (0) or grid boundary.
• Grid is rectangular, no diagonal connections.

Constraints

• 1 <= grid.length, grid[0].length <= 100.
• grid[i][j] is 0 or 1.
• Exactly one island exists.

Examples to Get Us Started

• Input: grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]
• Output: 16 (Count edges around the island).
• Input: grid = [[1]]
• Output: 4 (Single cell, all 4 edges).
• Input: grid = [[1,0]]
• Output: 4 (One cell, 4 edges).

Understanding the Problem: Tracing the Shoreline

To solve LeetCode 463: Island Perimeter in Python, we need to count the perimeter of a single island in a grid—each land cell (1) contributes edges that aren’t shared with another land cell. A naive approach—checking every cell’s neighbors—works but can be optimized. Each land cell starts with 4 edges, and we subtract shared edges with adjacent land. We’ll explore:

• Best Solution (Grid Traversal with Edge Counting): O(m * n) time, O(1) space—fast and simple.
• Alternative Solution (DFS with Boundary Checking): O(m * n) time, O(m * n) space—intuitive but heavier.

Let’s dive into the grid traversal solution—it’s the cartographer’s trusty compass we need.

Best Solution: Grid Traversal with Edge Counting

Why This Is the Best Solution

The grid traversal with edge counting is the top pick because it’s O(m * n) time (m = rows, n = cols) and O(1) space, efficiently computing the perimeter by scanning each cell once and adjusting for shared edges. It counts 4 edges per land cell, then subtracts 2 for each land-land adjacency (since each pair shares an edge). It’s like walking the grid, tallying shorelines while noting neighborly overlaps—straightforward and optimal!

How It Works

Here’s the strategy:

• Step 1: Iterate over each cell in the grid.
• Step 2: For each land cell (1):
• Add 4 to perimeter (all edges).
• Check left and up neighbors:
• If land, subtract 2 (shared edge).
• Step 3: Return total perimeter.
• Why It Works:
• Each land cell’s 4 edges are potential perimeter.
• Subtracting 2 per adjacency accounts for double-counted shared edges.

Step-by-Step Example

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

• Grid:

0 1 0 0 1 1 1 0 0 1 0 0 1 1 0 0

• Traversal:
• (0,1): 4 edges, left=0, up=n/a, perimeter = 4.
• (1,0): 4, left=n/a, up=0, perimeter = 8.
• (1,1): 4, left=1 (-2), up=1 (-2), perimeter = 8 + 4 - 4 = 8.
• (1,2): 4, left=1 (-2), up=0, perimeter = 8 + 4 - 2 = 10.
• (2,1): 4, left=0, up=1 (-2), perimeter = 10 + 4 - 2 = 12.
• (3,0): 4, left=n/a, up=0, perimeter = 12 + 4 = 16.
• (3,1): 4, left=1 (-2), up=1 (-2), perimeter = 16 + 4 - 4 = 16.
• Result: 16.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, broken down clearly:

Copy codeclass Solution:
    def islandPerimeter(self, grid: List[List[int]]) -> int:
        if not grid:
            return 0

        rows = len(grid)
        cols = len(grid[0])
        perimeter = 0

        # Step 1: Traverse grid
        for i in range(rows):
            for j in range(cols):
                if grid[i][j] == 1:  # Land cell
                    # Step 2: Add 4 edges
                    perimeter += 4

                    # Check left neighbor
                    if j > 0 and grid[i][j-1] == 1:
                        perimeter -= 2

                    # Check up neighbor
                    if i > 0 and grid[i-1][j] == 1:
                        perimeter -= 2

        return perimeter

• Line 3-4: Handle empty grid.
• Line 6-7: Get grid dimensions.
• Line 10-12: Loop over cells, check for land.
• Line 14: Add 4 edges per land cell.
• Line 16-17: Subtract 2 if left neighbor is land.
• Line 19-20: Subtract 2 if up neighbor is land.
• Line 22: Return total.
• Time Complexity: O(m * n)—single pass.
• Space Complexity: O(1)—no extra space.

It’s like a shoreline tally machine!

Alternative Solution: DFS with Boundary Checking

Why an Alternative Approach?

The DFS (Depth-First Search) method explores the island recursively—O(m * n) time, O(m * n) space—counting edges by checking boundaries and water around each land cell. It’s more complex but intuitive, like tracing the island’s edge step-by-step. Good for understanding or graph-like problems!

How It Works

• Step 1: Find a land cell to start DFS.
• Step 2: DFS visits each land cell:
• Count edges (4) minus adjacent land cells.
• Mark visited to avoid cycles.
• Step 3: Return total perimeter.

Step-by-Step Example

Example: grid = [[1,1], [1,1]]

• Start (0,0):
• Edges: 4, left=n/a, up=n/a, right=1, down=1, add 4-2=2.
• Visit (0,1): 4, left=1, up=n/a, right=n/a, down=1, add 2.
• Visit (1,0): 4, left=n/a, up=1, right=1, down=n/a, add 2.
• Visit (1,1): 4, left=1, up=1, right=n/a, down=n/a, add 2.
• Result: 2 + 2 + 2 + 2 = 8.

Code for DFS

Copy codeclass Solution:
    def islandPerimeter(self, grid: List[List[int]]) -> int:
        if not grid:
            return 0

        rows = len(grid)
        cols = len(grid[0])
        visited = set()

        def dfs(i, j):
            if (i, j) in visited or i < 0 or i >= rows or j < 0 or j >= cols or grid[i][j] == 0:
                return 0
            visited.add((i, j))
            perimeter = 4
            # Check 4 directions
            for di, dj in [(-1,0), (1,0), (0,-1), (0,1)]:
                ni, nj = i + di, j + dj
                if 0 <= ni < rows and 0 <= nj < cols and grid[ni][nj] == 1:
                    perimeter -= 1
            return perimeter + dfs(i-1, j) + dfs(i+1, j) + dfs(i, j-1) + dfs(i, j+1)

        # Find first land cell
        for i in range(rows):
            for j in range(cols):
                if grid[i][j] == 1:
                    return dfs(i, j)
        return 0

• Line 10-18: DFS counts edges, subtracts for land neighbors.
• Line 21-25: Start DFS from first land cell.
• Time Complexity: O(m * n)—visit each cell once.
• Space Complexity: O(m * n)—visited set.

It’s an island-tracing explorer!

Comparing the Two Solutions

• Grid Traversal (Best):
• Pros: O(m * n), O(1) space, simple.
• Cons: Less graph-like.
• DFS (Alternative):
• Pros: O(m * n), intuitive for connectivity.
• Cons: O(m * n) space, complex.

Traversal wins for efficiency.

Edge Cases and Examples

• Input: [[1]] → 4.
• Input: [[0]] → 0.
• Input: [[1,0],[0,1]] → Invalid (one island rule).

Traversal handles valid cases well.

Complexity Recap

• Traversal: Time O(m * n), Space O(1).
• DFS: Time O(m * n), Space O(m * n).

Traversal’s the champ.

Key Takeaways

• Traversal: Count and adjust.
• DFS: Explore and tally.
• Python Tip: Grids love loops—see [Python Basics](/python/basics).

Final Thoughts: Map That Coast

LeetCode 463: Island Perimeter in Python is a grid-mapping adventure. Grid traversal is your fast compass, while DFS is a scenic trek. Want more grid fun? Try LeetCode 200: Number of Islands or LeetCode 695: Max Area of Island. Ready to measure some shores? Head to Solve LeetCode 463 on LeetCode and chart it today—your coding skills are coastal-ready!