Skip to main content
Talentd

Island Perimeter - Solution & Explanation

EasyArrayDepth-First SearchBreadth-First SearchMatrix14 min readAsked at: Amazon, Microsoft, Apple +6
Practice this problem

Problem Statement

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.

 

Example 1:

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.

Example 2:

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

Example 3:

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.

Approach Overview

Problem Overview: You receive an m x n binary grid where 1 represents land and 0 represents water. The grid contains exactly one island (connected horizontally or vertically). The task is to calculate the total perimeter of that island by counting the edges where land touches water or the grid boundary.

Approach 1: Iterative Grid Enumeration (O(m*n) time, O(1) space)

Scan every cell in the grid. Each land cell contributes up to four edges to the perimeter. For every grid[i][j] == 1, start with +4 edges, then subtract edges shared with neighboring land cells. Checking the top and left neighbors avoids double counting shared edges. The key insight: every adjacent land pair removes two perimeter edges. This approach relies on simple iteration across the array representing the grid and constant-time neighbor checks.

Approach 2: Depth-First Search (DFS) (O(m*n) time, O(m*n) space)

Start a DFS from the first land cell and explore the entire island using recursion. Whenever the DFS reaches water or goes out of bounds, that edge contributes +1 to the perimeter. If a land cell is already visited, return 0 because its edges were counted earlier. This approach treats the island as a connected component in a matrix and traverses it using depth-first search. It is conceptually clean because each recursive step directly models an edge check around the island boundary.

Recommended for interviews: Iterative grid enumeration is the expected solution. It runs in O(m*n) time with O(1) space and requires only simple neighbor checks. DFS also works and demonstrates strong graph traversal knowledge, but interviewers typically prefer the enumeration approach because it avoids recursion overhead and is easier to reason about during implementation.

Approach 1: Iterative Grid Enumeration

This approach involves iterating over every cell in the grid. For each land cell (grid[i][j] == 1), we assume it initially contributes 4 to the perimeter. We then check its neighboring cells (up, down, left, right). If a neighboring cell is also land, we reduce the perimeter by one for each connection to another land cell, since that edge does not contribute to the perimeter.

This C program defines a function that calculates the island perimeter by checking adjacent cells for land. If an adjacent cell is land, the corresponding side does not contribute to the perimeter.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n*m) where n is the number of rows and m is the number of columns in the grid.
Space Complexity: O(1) as we only use a constant amount of extra space.

Try this approach in the editor β†’

Approach 2: Depth-First Search (DFS)

This approach leverages Depth-First Search to traverse the land cells. Starting from any land cell, we recursively visit all connected land cells and calculate the perimeter contribution for each by checking the edges. If an edge points to water or out of bounds, it contributes to the perimeter.

This C solution uses a DFS approach to calculate the perimeter by tracking visited cells and counting the contribution of each land cell.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n*m), each cell is visited once.
Space Complexity: O(n*m) for the recursion stack.

Try this approach in the editor β†’

Approach 3: Default Approach

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor β†’

Complexity Comparison

ApproachComplexity
Iterative Grid Enumeration

Time Complexity: O(n*m) where n is the number of rows and m is the number of columns in the grid.
Space Complexity: O(1) as we only use a constant amount of extra space.

Depth-First Search (DFS)

Time Complexity: O(n*m), each cell is visited once.
Space Complexity: O(n*m) for the recursion stack.

Default Approachβ€”

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Iterative Grid EnumerationO(m*n)O(1)Best general solution. Simple iteration with neighbor checks and constant memory.
Depth-First Search (DFS)O(m*n)O(m*n)Useful when treating the grid as a graph and exploring connected components.

Video Solution

Island Perimeter - Graph - Leetcode 463 β€’ NeetCode β€’ 59,712 views views

Watch 9 more video solutions β†’

Frequently Asked Questions

Is Island Perimeter easy or hard?
Island Perimeter is classified as an Easy problem. The challenge mainly involves careful boundary checks and understanding how adjacent land cells affect the total perimeter.
Island Perimeter Python/Java solution
Python and Java implementations typically iterate through the grid and check neighbors to count exposed edges. The core logic is identical across languages: add 4 per land cell and subtract edges shared with adjacent land cells for an O(m*n) solution.
How to solve Island Perimeter in O(n)?
Treat the grid as a collection of land cells and count exposed edges. For each cell with value 1, add 4 to the perimeter and subtract 2 for each adjacent land neighbor (typically checking top and left). Since every cell is processed once, the total runtime is O(m*n).
What is the best approach for Island Perimeter?
Iterative grid enumeration is the best approach. Traverse the grid and add 4 for every land cell, then subtract 2 for each adjacent land neighbor to avoid double counting shared edges. This runs in O(m*n) time and O(1) space and is the most common interview solution.
Is Island Perimeter asked at Google/Amazon/Meta?
Island Perimeter appears frequently in coding interviews at large tech companies and is common practice material for companies like Amazon and Google. It tests grid traversal, boundary conditions, and basic graph concepts on matrices.
What data structure is used in Island Perimeter?
The problem primarily uses a 2D array (matrix). Some solutions also treat the grid as a graph and use depth-first search or breadth-first search to traverse connected land cells.
What is the time complexity of Island Perimeter?
The optimal time complexity is O(m*n), where m and n are the grid dimensions. Every cell is visited once and each neighbor check takes constant time. DFS solutions also run in O(m*n) but may use additional recursion stack space.

Ready to solve this problem?

Practice Island Perimeter with our built-in code editor and test cases.

Practice on FleetCode
Previous

Coloring A Border

Next

Flood Fill