Number of Closed Islands solution and explanation
Google
9 more videos on this problem
Number of Closed Islands - Leetcode 1254 - PythonNeetCodeIO · 13:48 · 25K views
LeetCode 1254. Number of Closed IslandsHappy Coding · 12:01 · 3K views
Number of Closed Islands | LeetCode 1254Michael Vandi · 15:38 · 3K views
Leetcode 1254: Number of Closed IslandsAlgorithms Casts · 24:02 · 1K views
1254. Number of Closed Islands - JAVA (DFS - Detailed explanation)Sourin Majumdar · 9:31 · 486 views
Leetcode 1254. Number of Closed Islands (dfs)LetsCode · 7:23 · 212 views
LeetCode 1254 - Number of Closed Islands - Python SolutionCode with Carter · 12:32 · 182 views
Number of Closed Islands - Leetcode 1254 - DFS - PythonEffective Coder · 12:06 · 119 views
1254. Number of Closed Islands Leetcode Problem | Detailed ExplanationThe Stylish Coder · 18:50 · 116 views
LEETCODE 1254. Number of Closed Islands | DFS approach explained | C++ TutorialCoding Intuition · 5:35 · 110 views
The problem
Given a 2D grid consists of 0s (land) and 1s (water). An island is a maximal 4-directionally connected group of 0s and a closed island is an island totally (all left, top, right, bottom) surrounded by 1s.
Return the number of closed islands.
Example 1:
Input: grid = [[1,1,1,1,1,1,1,0],[1,0,0,0,0,1,1,0],[1,0,1,0,1,1,1,0],[1,0,0,0,0,1,0,1],[1,1,1,1,1,1,1,0]] Output: 2 Explanation: Islands in gray are closed because they are completely surrounded by water (group of 1s).
Example 2:
Input: grid = [[0,0,1,0,0],[0,1,0,1,0],[0,1,1,1,0]] Output: 1
Example 3:
Input: grid = [[1,1,1,1,1,1,1],
[1,0,0,0,0,0,1],
[1,0,1,1,1,0,1],
[1,0,1,0,1,0,1],
[1,0,1,1,1,0,1],
[1,0,0,0,0,0,1],
[1,1,1,1,1,1,1]]
Output: 2
Constraints:
1 <= grid.length, grid[0].length <= 1000 <= grid[i][j] <=1
Approach overview
Problem Overview: You are given a 2D grid where 0 represents land and 1 represents water. A closed island is a group of land cells completely surrounded by water and not touching the grid boundary. The task is to count how many such islands exist.
Approach 1: Depth-First Search (DFS) with Edge Checking (Time: O(m*n), Space: O(m*n))
This approach treats the grid as a graph and performs a DFS traversal from every unvisited land cell. During the DFS, you recursively explore four directions (up, down, left, right) and mark cells as visited. If any part of the island touches the grid boundary, the island cannot be closed. The key idea is to propagate a boolean flag during recursion that tracks whether the exploration ever reaches the edge. After the traversal finishes, only islands that never touched the boundary are counted. DFS works well because it naturally explores connected components in a matrix using Depth-First Search. This approach is concise and commonly expected in interviews.
Approach 2: Breadth-First Search (BFS) with Queue (Time: O(m*n), Space: O(m*n))
The BFS solution follows the same connected-component idea but replaces recursion with an explicit queue. When you find an unvisited land cell, push it into a queue and perform level-order exploration across its neighbors. While processing cells, track whether any coordinate lies on the boundary. If the component touches the grid edge, mark the island as open; otherwise, increment the closed island count after the traversal completes. BFS avoids recursion depth issues and can be easier to reason about in large grids. This method uses Breadth-First Search for systematic exploration and is equally optimal in terms of complexity.
Recommended for interviews: DFS with edge checking is usually the fastest to implement and easier to explain during interviews. It demonstrates your understanding of connected components in grids and recursive traversal. BFS is equally correct and useful when recursion depth might be a concern. Interviewers mainly expect you to recognize the problem as a graph traversal on a grid and solve it using DFS or BFS flood fill.
Approach 1: Depth-First Search (DFS) with Edge Checking
The grid can be viewed as a graph where each cell is a node connected to its four possible neighbors. To identify closed islands, we can use a DFS approach starting from any cell containing 0 (cell of land). This DFS should mark the entire island by changing those 0s to a visited flag, such as -1. During the traversal, if any part of the island reaches the grid's boundary, it cannot be a closed island.
For each unvisited 0, if it forms a complete island (i.e., it does not reach the boundary), we increment the closed island count. We examine cells systematically, ensuring that all possible islands are accounted for.
class Solution:
def closedIsland(self, grid) -> int:
def dfs(x, y):
if x < 0 or y < 0 or x >= len(grid) or y >= len(grid[0]):
return False
if grid[x][y] == 1 or grid[x][y] == -1:
return True
grid[x][y] = -1
top = dfs(x - 1, y)
bottom = dfs(x + 1, y)
left = dfs(x, y - 1)
right = dfs(x, y + 1)
return top and bottom and left and right
count = 0
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == 0:
if dfs(i, j):
count += 1
return countclass Solution {
public int closedIsland(int[][] grid) {
int count = 0;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j] == 0) {
if (dfs(grid, i, j)) {
count++;
}
}
}
}
return count;
}
private boolean dfs(int[][] grid, int x, int y) {
if (x < 0 || y < 0 || x >= grid.length || y >= grid[0].length) {
return false;
}
if (grid[x][y] == 1 || grid[x][y] == -1) return true;
grid[x][y] = -1;
boolean isClosed = true;
isClosed &= dfs(grid, x + 1, y);
isClosed &= dfs(grid, x - 1, y);
isClosed &= dfs(grid, x, y + 1);
isClosed &= dfs(grid, x, y - 1);
return isClosed;
}
}#include <vector>
#include <iostream>
using namespace std;
void dfs(vector<vector<int>>& grid, int x, int y, bool& isClosed) {
int rows = grid.size();
int cols = grid[0].size();
if (x < 0 || y < 0 || x >= rows || y >= cols) {
isClosed = false;
return;
}
if (grid[x][y] == 1 || grid[x][y] == -1) return;
grid[x][y] = -1;
dfs(grid, x + 1, y, isClosed);
dfs(grid, x - 1, y, isClosed);
dfs(grid, x, y + 1, isClosed);
dfs(grid, x, y - 1, isClosed);
}
int closedIsland(vector<vector<int>>& grid) {
int count = 0;
for (int i = 0; i < grid.size(); i++) {
for (int j = 0; j < grid[0].size(); j++) {
if (grid[i][j] == 0) {
bool isClosed = true;
dfs(grid, i, j, isClosed);
if (isClosed) {
count++;
}
}
}
}
return count;
}
int main() {
vector<vector<int>> grid = {{1,1,1,1,1,1,1,0}, {1,0,0,0,0,1,1,0}, {1,0,1,0,1,1,1,0},
{1,0,0,0,0,1,0,1}, {1,1,1,1,1,1,1,0}};
cout << closedIsland(grid) << endl;
return 0;
}var closedIsland = function(grid) {
const dfs = (x, y) => {
if (x < 0 || y < 0 || x >= grid.length || y >= grid[0].length) return false;
if (grid[x][y] === 1 || grid[x][y] === -1) return true;
grid[x][y] = -1;
const top = dfs(x - 1, y);
const bottom = dfs(x + 1, y);
const left = dfs(x, y - 1);
const right = dfs(x, y + 1);
return top && bottom && left && right;
}
let count = 0;
for (let i = 0; i < grid.length; i++) {
for (let j = 0; j < grid[0].length; j++) {
if (grid[i][j] === 0) {
if (dfs(i, j)) {
count++;
}
}
}
}
return count;
};#include <stdbool.h>
void dfs(int** grid, int x, int y, int rows, int cols, bool* isClosed) {
if (x < 0 || y < 0 || x >= rows || y >= cols) {
*isClosed = false;
return;
}
if (grid[x][y] == 1 || grid[x][y] == -1) return;
grid[x][y] = -1;
dfs(grid, x + 1, y, rows, cols, isClosed);
dfs(grid, x - 1, y, rows, cols, isClosed);
dfs(grid, x, y + 1, rows, cols, isClosed);
dfs(grid, x, y - 1, rows, cols, isClosed);
}
int closedIsland(int** grid, int rows, int* colsPtr) {
int cols = *colsPtr;
int count = 0;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (grid[i][j] == 0) {
bool isClosed = true;
dfs(grid, i, j, rows, cols, &isClosed);
if (isClosed) {
count++;
}
}
}
}
return count;
}public class Solution {
public int ClosedIsland(int[][] grid) {
int count = 0;
for (int i = 0; i < grid.Length; i++) {
for (int j = 0; j < grid[0].Length; j++) {
if (grid[i][j] == 0) {
if (DFS(grid, i, j)) {
count++;
}
}
}
}
return count;
}
private bool DFS(int[][] grid, int x, int y) {
if (x < 0 || y < 0 || x >= grid.Length || y >= grid[0].Length) {
return false;
}
if (grid[x][y] == 1 || grid[x][y] == -1) return true;
grid[x][y] = -1;
bool isClosed = true;
isClosed &= DFS(grid, x + 1, y);
isClosed &= DFS(grid, x - 1, y);
isClosed &= DFS(grid, x, y + 1);
isClosed &= DFS(grid, x, y - 1);
return isClosed;
}
}The Python version makes use of a recursive function dfs, which explores each island. Each exploration that passes the edge check increments the closed island count. Visited landmasses are marked to ensure no re-evaluation.
Time Complexity: O(m * n), where m is the number of rows, and n is the number of columns. Each cell is processed once.
Space Complexity: O(m * n) due to maximum depth of recursion stack.
Approach 2: Breadth-First Search (BFS) with Queue
This approach employs BFS to traverse the islands. By leveraging a queue, we can iteratively explore all 0-connected land cells starting from each unvisited land cell. If during any BFS iteration, we find ourselves at the boundary or edge of the grid, the ongoing island is not closed.
Using BFS here can make iterative exploration more intuitive and can be preferred in languages where managing stacks explicitly is a common challenge, although the core logic of edge-checking remains similar.
from collections import deque
class Solution:
def closedIsland(self, grid) -> int:
def bfs(x, y):
queue = deque([(x, y)])
isClosed = True
grid[x][y] = -1
while queue:
cx, cy = queue.popleft()
for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
nx, ny = cx + dx, cy + dy
if nx < 0 or ny < 0 or nx >= len(grid) or ny >= len(grid[0]):
isClosed = False
elif grid[nx][ny] == 0:
grid[nx][ny] = -1
queue.append((nx, ny))
return isClosed
count = 0
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == 0:
if bfs(i, j):
count += 1
return countimport java.util.LinkedList;
import java.util.Queue;
class Solution {
public int closedIsland(int[][] grid) {
int count = 0;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j] == 0) {
if (bfs(grid, i, j)) {
count++;
}
}
}
}
return count;
}
private boolean bfs(int[][] grid, int startX, int startY) {
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{startX, startY});
int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
grid[startX][startY] = -1;
boolean isClosed = true;
while (!queue.isEmpty()) {
int[] cell = queue.poll();
for (int[] dir : directions) {
int nx = cell[0] + dir[0];
int ny = cell[1] + dir[1];
if (nx < 0 || ny < 0 || nx >= grid.length || ny >= grid[0].length) {
isClosed = false;
} else if (grid[nx][ny] == 0) {
grid[nx][ny] = -1;
queue.offer(new int[]{nx, ny});
}
}
}
return isClosed;
}
}#include <vector>
#include <queue>
using namespace std;
bool bfs(vector<vector<int>>& grid, int x, int y) {
int rows = grid.size(), cols = grid[0].size();
vector<pair<int, int>> directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
queue<pair<int, int>> q;
q.push({x, y});
grid[x][y] = -1;
bool isClosed = true;
while (!q.empty()) {
auto [cx, cy] = q.front(); q.pop();
for (const auto& [dx, dy] : directions) {
int nx = cx + dx, ny = cy + dy;
if (nx < 0 || ny < 0 || nx >= rows || ny >= cols) {
isClosed = false;
continue;
}
if (grid[nx][ny] == 0) {
grid[nx][ny] = -1;
q.push({nx, ny});
}
}
}
return isClosed;
}
int closedIsland(vector<vector<int>>& grid) {
int count = 0;
for (int i = 0; i < grid.size(); i++) {
for (int j = 0; j < grid[0].size(); j++) {
if (grid[i][j] == 0) {
if (bfs(grid, i, j)) {
count++;
}
}
}
}
return count;
}var closedIsland = function(grid) {
const bfs = (startX, startY) => {
const queue = [[startX, startY]];
let isClosed = true;
grid[startX][startY] = -1;
const directions = [[1, 0], [-1, 0], [0, 1], [0, -1]];
while (queue.length > 0) {
const [x, y] = queue.shift();
for (const [dx, dy] of directions) {
const nx = x + dx, ny = y + dy;
if (nx < 0 || ny < 0 || nx >= grid.length || ny >= grid[0].length) {
isClosed = false;
} else if (grid[nx][ny] === 0) {
grid[nx][ny] = -1;
queue.push([nx, ny]);
}
}
}
return isClosed;
};
let count = 0;
for (let i = 0; i < grid.length; i++) {
for (let j = 0; j < grid[0].length; j++) {
if (grid[i][j] === 0) {
if (bfs(i, j)) {
count++;
}
}
}
}
return count;
};#include <stdbool.h>
#include <stdlib.h>
typedef struct {
int x, y;
} Point;
void enqueue(Point** queue, int* rear, int x, int y) {
queue[*rear] = (Point*)malloc(sizeof(Point));
queue[*rear]->x = x;
queue[*rear]->y = y;
(*rear)++;
}
Point dequeue(Point** queue, int* front) {
Point result = *queue[(*front)++];
free(queue[*front-1]);
return result;
}
bool bfs(int** grid, int rows, int cols, int x, int y) {
int directions[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
bool isClosed = true;
Point* queue[10000];
int front = 0, rear = 0;
enqueue(queue, &rear, x, y);
grid[x][y] = -1;
while (front < rear) {
Point pt = dequeue(queue, &front);
for (int d = 0; d < 4; d++) {
int nx = pt.x + directions[d][0];
int ny = pt.y + directions[d][1];
if (nx < 0 || ny < 0 || nx >= rows || ny >= cols) {
isClosed = false;
continue;
}
if (grid[nx][ny] == 0) {
grid[nx][ny] = -1;
enqueue(queue, &rear, nx, ny);
}
}
}
return isClosed;
}
int closedIsland(int** grid, int rows, int* colsPtr) {
int cols = *colsPtr;
int count = 0;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (grid[i][j] == 0) {
if (bfs(grid, rows, cols, i, j)) {
count++;
}
}
}
}
return count;
}using System.Collections.Generic;
public class Solution {
public int ClosedIsland(int[][] grid) {
int count = 0;
for (int i = 0; i < grid.Length; i++) {
for (int j = 0; j < grid[0].Length; j++) {
if (grid[i][j] == 0) {
if (BFS(grid, i, j)) {
count++;
}
}
}
}
return count;
}
private bool BFS(int[][] grid, int startX, int startY) {
Queue<int[]> queue = new Queue<int[]>();
queue.Enqueue(new int[] {startX, startY});
int[][] directions = new int[][] {
new int[] {1, 0},
new int[] {-1, 0},
new int[] {0, 1},
new int[] {0, -1}
};
grid[startX][startY] = -1;
bool isClosed = true;
while (queue.Count > 0) {
int[] cell = queue.Dequeue();
foreach (var dir in directions) {
int nx = cell[0] + dir[0], ny = cell[1] + dir[1];
if (nx < 0 || ny < 0 || nx >= grid.Length || ny >= grid[0].Length) {
isClosed = false;
} else if (grid[nx][ny] == 0) {
grid[nx][ny] = -1;
queue.Enqueue(new int[] {nx, ny});
}
}
}
return isClosed;
}
}Using Python's collections.deque for the BFS queue, this solution follows similar logic to Java, marking visited nodes, and iterating via queue processing to identify closed islands.
Time Complexity: O(m * n), where m is the number of rows, and n is the number of columns.
Space Complexity: O(min(m, n)) due to the queue management.
Approach 3: DFS
We traverse the matrix, and for each piece of land, we perform a depth-first search to find all the land connected to it. Then we check if there is any land on the boundary. If there is, it is not a closed island; otherwise, it is a closed island, and we increment the answer by one.
Finally, we return the answer.
The time complexity is O(m times n), and the space complexity is O(m times n). Where m and n are the number of rows and columns in the matrix, respectively.
function closedIsland(grid: number[][]): number {
const m = grid.length;
const n = grid[0].length;
const dirs = [-1, 0, 1, 0, -1];
const dfs = (i: number, j: number): number => {
let res = i > 0 && j > 0 && i < m - 1 && j < n - 1 ? 1 : 0;
grid[i][j] = 1;
for (let k = 0; k < 4; ++k) {
const [x, y] = [i + dirs[k], j + dirs[k + 1]];
if (x >= 0 && y >= 0 && x < m && y < n && grid[x][y] === 0) {
res &= dfs(x, y);
}
}
return res;
};
let ans = 0;
for (let i = 0; i < m; ++i) {
for (let j = 0; j < n; j++) {
if (grid[i][j] === 0) {
ans += dfs(i, j);
}
}
}
return ans;
}func closedIsland(grid [][]int) (ans int) {
m, n := len(grid), len(grid[0])
dirs := [5]int{-1, 0, 1, 0, -1}
var dfs func(i, j int) int
dfs = func(i, j int) int {
res := 1
if i == 0 || i == m-1 || j == 0 || j == n-1 {
res = 0
}
grid[i][j] = 1
for k := 0; k < 4; k++ {
x, y := i+dirs[k], j+dirs[k+1]
if x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 0 {
res &= dfs(x, y)
}
}
return res
}
for i, row := range grid {
for j, v := range row {
if v == 0 {
ans += dfs(i, j)
}
}
}
return
}Approach 4: Union-Find
We can use a union-find set to maintain each piece of connected land.
We traverse the matrix, if the current position is on the boundary, we connect it with the virtual node m times n. If the current position is land, we connect it with the land below and to the right.
Then, we traverse the matrix again, for each piece of land, if its root node is itself, we increment the answer by one.
Finally, we return the answer.
The time complexity is O(m times n times \alpha(m times n)), and the space complexity is O(m times n). Where m and n are the number of rows and columns in the matrix, respectively.
function closedIsland(grid: number[][]): number {
const m = grid.length;
const n = grid[0].length;
const uf = new UnionFind(m * n + 1);
for (let i = 0; i < m; ++i) {
for (let j = 0; j < n; ++j) {
if (i === 0 || i === m - 1 || j === 0 || j === n - 1) {
uf.union(i * n + j, m * n);
}
if (grid[i][j] === 0) {
if (i + 1 < m && grid[i + 1][j] === 0) {
uf.union(i * n + j, (i + 1) * n + j);
}
if (j + 1 < n && grid[i][j + 1] === 0) {
uf.union(i * n + j, i * n + j + 1);
}
}
}
}
let ans = 0;
for (let i = 0; i < m; ++i) {
for (let j = 0; j < n; j++) {
if (grid[i][j] === 0 && uf.find(i * n + j) === i * n + j) {
++ans;
}
}
}
return ans;
}
class UnionFind {
private p: number[];
private size: number[];
constructor(n: number) {
this.p = Array(n)
.fill(0)
.map((_, i) => i);
this.size = Array(n).fill(1);
}
find(x: number): number {
if (this.p[x] !== x) {
this.p[x] = this.find(this.p[x]);
}
return this.p[x];
}
union(a: number, b: number): void {
const [pa, pb] = [this.find(a), this.find(b)];
if (pa === pb) {
return;
}
if (this.size[pa] > this.size[pb]) {
this.p[pb] = pa;
this.size[pa] += this.size[pb];
} else {
this.p[pa] = pb;
this.size[pb] += this.size[pa];
}
}
}type unionFind struct {
p, size []int
}
func newUnionFind(n int) *unionFind {
p := make([]int, n)
size := make([]int, n)
for i := range p {
p[i] = i
size[i] = 1
}
return &unionFind{p, size}
}
func (uf *unionFind) find(x int) int {
if uf.p[x] != x {
uf.p[x] = uf.find(uf.p[x])
}
return uf.p[x]
}
func (uf *unionFind) union(a, b int) {
pa, pb := uf.find(a), uf.find(b)
if pa != pb {
if uf.size[pa] > uf.size[pb] {
uf.p[pb] = pa
uf.size[pa] += uf.size[pb]
} else {
uf.p[pa] = pb
uf.size[pb] += uf.size[pa]
}
}
}
func closedIsland(grid [][]int) (ans int) {
m, n := len(grid), len(grid[0])
uf := newUnionFind(m*n + 1)
for i, row := range grid {
for j, v := range row {
if i == 0 || i == m-1 || j == 0 || j == n-1 {
uf.union(i*n+j, m*n)
}
if v == 0 {
if i+1 < m && grid[i+1][j] == 0 {
uf.union(i*n+j, (i+1)*n+j)
}
if j+1 < n && grid[i][j+1] == 0 {
uf.union(i*n+j, i*n+j+1)
}
}
}
}
for i, row := range grid {
for j, v := range row {
if v == 0 && uf.find(i*n+j) == i*n+j {
ans++
}
}
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Depth-First Search (DFS) with Edge Checking | Time Complexity: O(m * n), where |
| Breadth-First Search (BFS) with Queue | Time Complexity: O(m * n), where |
| DFS | – |
| Union-Find | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Depth-First Search (DFS) with Edge Checking | O(m*n) | O(m*n) | Best general solution. Simple recursion for exploring connected land cells. |
| Breadth-First Search (BFS) with Queue | O(m*n) | O(m*n) | Useful when avoiding recursion or handling very deep grids. |
Frequently asked questions
Is Number of Closed Islands easy or hard?
Number of Closed Islands is typically rated Medium difficulty. The challenge lies in recognizing that islands touching the grid boundary must be excluded and implementing a correct DFS or BFS traversal to track that condition.
Number of Closed Islands Python/Java solution
In Python or Java, implement DFS or BFS to explore four directions from each land cell. Mark visited cells by modifying the grid or using a separate visited array. If any explored cell lies on the boundary, the island is not closed. The final count includes only islands fully surrounded by water.
How to solve Number of Closed Islands in O(n)?
Treat the grid as a graph and perform DFS or BFS from every unvisited land cell. While exploring neighbors, check whether any part of the island touches the grid boundary. If the traversal never reaches the edge, increment the closed island count. Every cell is processed once, resulting in O(m*n) time complexity.
What is the best approach for Number of Closed Islands?
The most common approach is Depth-First Search (DFS) to explore each connected land component. During traversal, track whether any cell touches the grid boundary. If it does, the island is not closed. This DFS flood fill runs in O(m*n) time and O(m*n) space and is typically expected in coding interviews.
Is Number of Closed Islands asked at Google/Amazon/Meta?
Grid traversal and island-counting problems are common at companies like Amazon, Google, and Meta. Variants such as Number of Islands, Closed Islands, and Surrounded Regions frequently appear in interviews because they test DFS/BFS graph traversal on matrices.
What data structure is used in Number of Closed Islands?
The main data structures are the grid itself and either a recursion stack (for DFS) or a queue (for BFS). These structures help traverse connected components of land cells while marking visited positions to avoid repeated work.
What is the time complexity of Number of Closed Islands?
The optimal DFS or BFS solution runs in O(m*n) time where m and n are the grid dimensions. Each cell is visited at most once during traversal. The space complexity is O(m*n) in the worst case due to recursion stack or queue storage for large land regions.