Island Perimeter solution and explanation
Google
9 more videos on this problem
Island Perimeter - Graph - Leetcode 463NeetCode · 12:53 · 59K views
LeetCode Island Perimeter Solution Explained - JavaNick White · 7:28 · 18K views
463. Island Perimeter | Popular interview question Leetcode | Competitive programming | CityCoderCity Coder · 7:43 · 6K views
Leetcode - Island Perimeter (Python)Timothy H Chang · 6:01 · 1K views
Island Perimeter | Leetcode 463 | Live coding session 🔥🔥🔥Coding Decoded · 8:47 · 882 views
island perimeter | island perimeter leetcode | leetcode 463 |iterate gridNaresh Gupta · 8:35 · 645 views
How to Solve "463 Island Perimeter" on LeetCode? - JavascriptBecoming A Better Dev (with David) · 6:42 · 493 views
Leetcode 463 - Island Perimeter (JAVA Solution Explained!)LC Bear · 11:34 · 426 views
LeetCode 463. Island Perimeter | No BFS Needed!CodingNinja · 12:49 · 382 views
LeetCode 463. Island Perimeter | JavaScript & AlgorithmJSer · 8:13 · 363 views
The problem
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.lengthcol == grid[i].length1 <= row, col <= 100grid[i][j]is0or1.- 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.
class Solution:
def islandPerimeter(self, grid: List[List[int]]) -> int:
perimeter = 0
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == 1:
perimeter += 4
if i > 0 and grid[i-1][j] == 1:
perimeter -= 1
if i < len(grid) - 1 and grid[i+1][j] == 1:
perimeter -= 1
if j > 0 and grid[i][j-1] == 1:
perimeter -= 1
if j < len(grid[0]) - 1 and grid[i][j+1] == 1:
perimeter -= 1
return perimeterclass Solution {
public int islandPerimeter(int[][] grid) {
int perimeter = 0;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[i].length; j++) {
if (grid[i][j] == 1) {
perimeter += 4;
if (i > 0 && grid[i-1][j] == 1) perimeter--;
if (i < grid.length - 1 && grid[i+1][j] == 1) perimeter--;
if (j > 0 && grid[i][j-1] == 1) perimeter--;
if (j < grid[i].length - 1 && grid[i][j+1] == 1) perimeter--;
}
}
}
return perimeter;
}
}#include <vector>
using namespace std;
class Solution {
public:
int islandPerimeter(vector<vector<int>>& grid) {
int perimeter = 0;
int rows = grid.size();
int cols = grid[0].size();
for (int i = 0; i < rows; ++i) {
for (int j = 0; j < cols; ++j) {
if (grid[i][j] == 1) {
perimeter += 4;
if (i > 0 && grid[i-1][j] == 1) perimeter--;
if (i < rows - 1 && grid[i+1][j] == 1) perimeter--;
if (j > 0 && grid[i][j-1] == 1) perimeter--;
if (j < cols - 1 && grid[i][j+1] == 1) perimeter--;
}
}
}
return perimeter;
}
};var islandPerimeter = function(grid) {
let perimeter = 0;
for (let i = 0; i < grid.length; i++) {
for (let j = 0; j < grid[i].length; j++) {
if (grid[i][j] === 1) {
perimeter += 4;
if (i > 0 && grid[i-1][j] === 1) perimeter--;
if (i < grid.length - 1 && grid[i+1][j] === 1) perimeter--;
if (j > 0 && grid[i][j-1] === 1) perimeter--;
if (j < grid[i].length - 1 && grid[i][j+1] === 1) perimeter--;
}
}
}
return perimeter;
};#include <stdio.h>
int islandPerimeter(int** grid, int gridSize, int* gridColSize) {
int perimeter = 0;
for (int i = 0; i < gridSize; i++) {
for (int j = 0; j < gridColSize[i]; j++) {
if (grid[i][j] == 1) {
perimeter += 4;
if (i > 0 && grid[i-1][j] == 1) perimeter--;
if (i < gridSize - 1 && grid[i+1][j] == 1) perimeter--;
if (j > 0 && grid[i][j-1] == 1) perimeter--;
if (j < gridColSize[i] - 1 && grid[i][j+1] == 1) perimeter--;
}
}
}
return perimeter;
}public class Solution {
public int IslandPerimeter(int[][] grid) {
int perimeter = 0;
for (int i = 0; i < grid.Length; i++) {
for (int j = 0; j < grid[i].Length; j++) {
if (grid[i][j] == 1) {
perimeter += 4;
if (i > 0 && grid[i-1][j] == 1) perimeter--;
if (i < grid.Length - 1 && grid[i+1][j] == 1) perimeter--;
if (j > 0 && grid[i][j-1] == 1) perimeter--;
if (j < grid[i].Length - 1 && grid[i][j+1] == 1) perimeter--;
}
}
}
return perimeter;
}
}This Python solution calculates the perimeter by iteratively updating the perimeter count according to the presence of adjacent land cells.
Time Complexity: O(n*m).
Space Complexity: O(1).
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.
class Solution:
def dfs(self, grid, i, j):
if i < 0 or j < 0 or i >= len(grid) or j >= len(grid[0]) or grid[i][j] == 0:
return 1
if grid[i][j] == -1:
return 0
grid[i][j] = -1
return self.dfs(grid, i-1, j) + self.dfs(grid, i+1, j) + \
self.dfs(grid, i, j-1) + self.dfs(grid, i, j+1)
def islandPerimeter(self, grid: List[List[int]]) -> int:
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == 1:
return self.dfs(grid, i, j)
return 0class Solution {
private int dfs(int[][] grid, int i, int j) {
if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] == 0) return 1;
if (grid[i][j] == -1) return 0;
grid[i][j] = -1;
return dfs(grid, i-1, j) + dfs(grid, i+1, j) +
dfs(grid, i, j-1) + dfs(grid, i, j+1);
}
public int islandPerimeter(int[][] grid) {
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[i].length; j++) {
if (grid[i][j] == 1) {
return dfs(grid, i, j);
}
}
}
return 0;
}
}#include <vector>
using namespace std;
class Solution {
public:
int dfs(vector<vector<int>>& grid, int i, int j) {
if (i < 0 || j < 0 || i >= grid.size() || j >= grid[0].size() || grid[i][j] == 0) return 1;
if (grid[i][j] == -1) return 0;
grid[i][j] = -1;
return dfs(grid, i-1, j) + dfs(grid, i+1, j) +
dfs(grid, i, j-1) + dfs(grid, i, j+1);
}
int islandPerimeter(vector<vector<int>>& grid) {
for (int i = 0; i < grid.size(); i++) {
for (int j = 0; j < grid[0].size(); j++) {
if (grid[i][j] == 1) {
return dfs(grid, i, j);
}
}
}
return 0;
}
};var islandPerimeter = function(grid) {
const dfs = (i, j) => {
if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] === 0) return 1;
if (grid[i][j] === -1) return 0;
grid[i][j] = -1;
return dfs(i-1, j) + dfs(i+1, j) + dfs(i, j-1) + dfs(i, j+1);
};
for (let i = 0; i < grid.length; i++) {
for (let j = 0; j < grid[i].length; j++) {
if (grid[i][j] === 1) {
return dfs(i, j);
}
}
}
return 0;
};#include <stdio.h>
int dfs(int** grid, int i, int j, int rows, int cols) {
if (i < 0 || j < 0 || i >= rows || j >= cols || grid[i][j] == 0) return 1;
if (grid[i][j] == -1) return 0;
grid[i][j] = -1;
return dfs(grid, i-1, j, rows, cols) + dfs(grid, i+1, j, rows, cols) +
dfs(grid, i, j-1, rows, cols) + dfs(grid, i, j+1, rows, cols);
}
int islandPerimeter(int** grid, int gridSize, int* gridColSize) {
for (int i = 0; i < gridSize; i++) {
for (int j = 0; j < gridColSize[i]; j++) {
if (grid[i][j] == 1) {
return dfs(grid, i, j, gridSize, gridColSize[i]);
}
}
}
return 0;
}public class Solution {
private int Dfs(int[][] grid, int i, int j) {
if (i < 0 || j < 0 || i >= grid.Length || j >= grid[0].Length || grid[i][j] == 0) return 1;
if (grid[i][j] == -1) return 0;
grid[i][j] = -1;
return Dfs(grid, i-1, j) + Dfs(grid, i+1, j) +
Dfs(grid, i, j-1) + Dfs(grid, i, j+1);
}
public int IslandPerimeter(int[][] grid) {
for (int i = 0; i < grid.Length; i++) {
for (int j = 0; j < grid[i].Length; j++) {
if (grid[i][j] == 1) {
return Dfs(grid, i, j);
}
}
}
return 0;
}
}This Python solution employs DFS to traverse and count the perimeter for each encountered land cell, backtracking as necessary.
Time Complexity: O(n*m).
Space Complexity: O(n*m).
Approach 3: Default Approach
function islandPerimeter(grid: number[][]): number {
let m = grid.length,
n = grid[0].length;
let ans = 0;
for (let i = 0; i < m; ++i) {
for (let j = 0; j < n; ++j) {
let top = 0,
left = 0;
if (i > 0) {
top = grid[i - 1][j];
}
if (j > 0) {
left = grid[i][j - 1];
}
let cur = grid[i][j];
if (cur != top) ++ans;
if (cur != left) ++ans;
}
}
// 最后一行， 最后一列
for (let i = 0; i < m; ++i) {
if (grid[i][n - 1] == 1) ++ans;
}
for (let j = 0; j < n; ++j) {
if (grid[m - 1][j] == 1) ++ans;
}
return ans;
}func islandPerimeter(grid [][]int) int {
m, n := len(grid), len(grid[0])
ans := 0
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if grid[i][j] == 1 {
ans += 4
if i < m-1 && grid[i+1][j] == 1 {
ans -= 2
}
if j < n-1 && grid[i][j+1] == 1 {
ans -= 2
}
}
}
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Iterative Grid Enumeration | Time Complexity: O(n*m). |
| Depth-First Search (DFS) | Time Complexity: O(n*m). |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Grid Enumeration | O(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. |
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.