Problem 20.6 · Graph FundamentalsEasy

Island Perimeter

What it teaches: Grid as graph without a traversal: count land cells and shared sides.

Practise it on judges as “Island Perimeter”.

The problem

A grid has 1 for land and 0 for water, with exactly one island (no lakes inside). Return the island's perimeter.

Example 1

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

Constraints

1 ≤ rows, cols ≤ 100

Pattern clues in the wording

→ Grid, count boundary edges

These clues point to Matrix Traversal: Walk a 2D grid in a controlled order (rows, columns, spiral, diagonals) using boundaries or direction arrays.

Stuck? Take one hint at a time

Solution.java · starter

class Solution {
    public int islandPerimeter(int[][] grid) {
        return 0;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]	16
2	grid = [[1]]	4
3	grid = [[1,0]]	4

From slow to fast

Approaches

1. Count cells and shared sides · O(rows × cols)

Count cells and shared sides

Time O(rows × cols) Space O(1)

perimeter = 4 × land − 2 × (land cells with land below + land cells with land to the right).

▶ Dry run: Countinggrid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]

Step 1/37 land cells: 7 × 4 = 28 sides.

Approach 1

class Solution {
    public int islandPerimeter(int[][] grid) {
        int land = 0, shared = 0;
        for (int r = 0; r < grid.length; r++)
            for (int c = 0; c < grid[0].length; c++) {
                if (grid[r][c] == 0) continue;
                land++;
                if (r + 1 < grid.length && grid[r + 1][c] == 1) shared++;
                if (c + 1 < grid[0].length && grid[r][c + 1] == 1) shared++;
            }
        return 4 * land - 2 * shared;
    }
}

Verdict: No DFS needed.

Before you submit

Edge cases and common mistakes

Test these inputs

Single cell (4)
Island touching the grid edge

Mistakes people make

Counting shared sides in all four directions (double counting).

Interview

Follow-up questions

What if there could be lakes inside the island that don't count?

Command Palette

The problem

Approaches

Count cells and shared sides

Edge cases and common mistakes

Follow-up questions