Log inSign up
mediumLeetCodeNot Started

Number of Closed Islands

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Arrays
Solve on LeetCode
Lesson

Problem Statement

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 top, left, bottom, right) surrounded by 1s.

Return the number of closed islands.

Example 1 · Standard Grid with Closed Islands:

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 surrounded on all sides by 1s that do not touch the outer boundary.

Example 2 · No Closed Islands:

Input: grid = [ [0,0,1,0,0], [0,1,0,1,0], [0,1,1,1,0] ]
Output: 1
Explanation: Only the center cell (1,2) is completely enclosed by 1s.

Constraints:

  • 1 <= grid.length, grid[0].length <= 100
  • 0 <= grid[i][j] <= 1

Prerequisites

Before attempting this problem, you should be comfortable with:

  • Grid traversal and boundary condition checking
  • Depth-First Search (DFS) / Flood Fill pattern
  • Connected component graph concepts

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the 2-Phase Boundary Flood Fill pruning pattern.
  • Understand the inversion of land (0) vs water (1) representation.
  • Eliminate boundary edge cases by pre-clearing connected border components.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Input structure involves an array or contiguous sequence with constraints on element relationships.
  • Optimal solution requires avoiding O(N2) exhaustive searches through state tracking or pointers.
  • Subproblem exhibits optimal substructure or monotonicity enabling linear or logarithmic processing.

Algorithmic Decision Tree:

  • If the array is sorted or can be sorted without violating problem requirements, evaluate Two Pointers or Binary Search.
  • If tracking contiguous subsegments with monotone expansion/shrinkage, apply Sliding Window.
  • If frequency or complement lookups are required in O(1) time, use a Hash Map or Frequency Array.

Connected Patterns:

Surrounded RegionsNumber of EnclavesPacific Atlantic Water Flow

1. Perimeter Reachability Check per Land Cell (Brute Force)

Intuition

0 represents land, 1 represents water. An island is closed if none of its land cells are on the grid boundary (r == 0, r == m-1, c == 0, c == n-1). For each unvisited 0, run BFS: if any cell touches the boundary, the entire component is NOT closed. Otherwise, increment closed island count.

When to apply: Use to verify the definition of closed islands.

Perimeter Reachability BFS Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1]
Current operationSTEP 1 OF 6
Grid: 4x4
Visual state
Values and pointers at this exact step
matrix
c0
c1
c2
c3
r0
1
1
1
1
r1
1
0
↑ 0-land
0
1
r2
1
0
0
1
r3
1
1
1
1
Variables at this step
closedCount
0
Check / comparison
Perimeter is water.
Decision / next transition
Candidate interior land.
Why this step matters

Grid: 4x4. Boundary cells (rows 0, 3, cols 0, 3) are all water (1). Land cells (0) are at (1,1), (1,2), (2,1), (2,2).

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1import java.util.*;
2
3public class Main {
4 public static class Solution {
5 public int closedIsland(int[][] grid) {
6 int m = grid.length, n = grid[0].length;
7 boolean[][] visited = new boolean[m][n];
8 int closed = 0;
9 int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
10
11 for (int r = 0; r < m; r++) {
12 for (int c = 0; c < n; c++) {
13 if (grid[r][c] == 0 && !visited[r][c]) {
14 Queue<int[]> q = new LinkedList<>();
15 q.add(new int[]{r, c});
16 visited[r][c] = true;
17 boolean isClosed = true;
18
19 while (!q.isEmpty()) {
20 int[] curr = q.poll();
21 int cr = curr[0], cc = curr[1];
22 if (cr == 0 || cr == m - 1 || cc == 0 || cc == n - 1) {
23 isClosed = false;
24 }
25 for (int[] d : dirs) {
26 int nr = cr + d[0], nc = cc + d[1];
27 if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] == 0 && !visited[nr][nc]) {
28 visited[nr][nc] = true;
29 q.add(new int[]{nr, nc});
30 }
31 }
32 }
33 if (isClosed) closed++;
34 }
35 }
36 }
37 return closed;
38 }
39 }
40
41 public static void main(String[] args) {
42 Solution sol = new Solution();
43 int[][] grid = {
44 {1, 1, 1, 1},
45 {1, 0, 0, 1},
46 {1, 0, 0, 1},
47 {1, 1, 1, 1}
48 };
49 System.out.println("Closed Islands: " + sol.closedIsland(grid));
50 }
51}

Time & Space Complexity

  • Time complexity: O(m * n) — Every cell is explored once.
  • Space complexity: O(m * n) — Visited matrix and queue.

Why Brute Force Doesn't Scale:

Branching booleans require visiting every node regardless of early failure.

2-phase DFS simplifies code into standard flood fill with 0 auxiliary tracking memory.

2. Boundary Flood Fill Elimination

Intuition

1. Scan boundary cells: for any land cell on row 0, row m-1, col 0, col n-1, run DFS/BFS to turn all connected land into water (1). 2. Scan remaining interior cells: every remaining component of 0s is guaranteed to be completely closed! Count them with regular DFS.

When to apply: Use to eliminate edge cases first, converting the problem to standard number of islands.

Boundary Flood Fill Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1]
Current operationSTEP 1 OF 6
Step 1: Check perimeter rows (0, 3) and cols (0, 3)
Visual state
Values and pointers at this exact step
matrix
c0
c1
c2
c3
r0
1
↑ Perimeter
1
1
1
r1
1
0
0
1
r2
1
0
0
1
r3
1
1
1
1
Variables at this step
boundaryLandSunken
0
Check / comparison
No boundary 0s.
Decision / next transition
Boundary flood fill finishes with 0 changes.
Why this step matters

Step 1: Check perimeter rows (0, 3) and cols (0, 3). All are 1 (water). No boundary land to eliminate.

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1public class Main {
2 public static class Solution {
3 public int closedIsland(int[][] grid) {
4 int m = grid.length, n = grid[0].length;
5
6 // Step 1: Flood fill boundary land
7 for (int r = 0; r < m; r++) {
8 if (grid[r][0] == 0) dfs(grid, r, 0);
9 if (grid[r][n - 1] == 0) dfs(grid, r, n - 1);
10 }
11 for (int c = 0; c < n; c++) {
12 if (grid[0][c] == 0) dfs(grid, 0, c);
13 if (grid[m - 1][c] == 0) dfs(grid, m - 1, c);
14 }
15
16 // Step 2: Count remaining interior closed islands
17 int count = 0;
18 for (int r = 0; r < m; r++) {
19 for (int c = 0; c < n; c++) {
20 if (grid[r][c] == 0) {
21 count++;
22 dfs(grid, r, c);
23 }
24 }
25 }
26 return count;
27 }
28
29 private void dfs(int[][] grid, int r, int c) {
30 if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length || grid[r][c] == 1) return;
31 grid[r][c] = 1; // turn land to water
32 dfs(grid, r + 1, c);
33 dfs(grid, r - 1, c);
34 dfs(grid, r, c + 1);
35 dfs(grid, r, c - 1);
36 }
37 }
38
39 public static void main(String[] args) {
40 Solution sol = new Solution();
41 int[][] grid = {
42 {1, 1, 1, 1},
43 {1, 0, 0, 1},
44 {1, 0, 0, 1},
45 {1, 1, 1, 1}
46 };
47 System.out.println("Closed Islands: " + sol.closedIsland(grid));
48 }
49}

Time & Space Complexity

  • Time complexity: O(m * n) — Two passes visiting each cell at most twice.
  • Space complexity: O(m * n) — Recursive call stack O(m * n).

3. Single-Pass Boolean DFS (Optimal & Standard)

Intuition

1. Iterate cells: if grid[r][c] == 0 and not visited, call dfs(r, c). 2. Base case: If out of bounds, return false (indicates leak to boundary). If water (1), return true (closed on this side). 3. Sink cell: grid[r][c] = 1. 4. Recursively call in all 4 directions. Use bitwise & (or separate variables) so ALL branches execute (preventing short-circuiting that leaves unvisited land). 5. If all directions return true, increment closed islands count.

When to apply: Use as the cleanest single-pass algorithm without modifying the perimeter in a separate pass.

Single-Pass Boolean DFS Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1]
Current operationSTEP 1 OF 6
grid[1][1]=0: Launch dfs(1, 1)
Visual state
Values and pointers at this exact step
matrix
c0
c1
c2
c3
r0
1
1
1
1
r1
1
1
↑ dfs(1,1)
0
1
r2
1
0
0
1
r3
1
1
1
1
Variables at this step
currCell
(1,1)
Check / comparison
Interior land cell.
Decision / next transition
Call dfs on neighbors.
Why this step matters

grid[1][1]=0: Launch dfs(1, 1). Sink grid[1][1] = 1. Evaluates 4 directions.

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1public class Main {
2 public static class Solution {
3 public int closedIsland(int[][] grid) {
4 int m = grid.length, n = grid[0].length;
5 int count = 0;
6
7 for (int r = 0; r < m; r++) {
8 for (int c = 0; c < n; c++) {
9 if (grid[r][c] == 0) {
10 if (dfs(grid, r, c)) {
11 count++;
12 }
13 }
14 }
15 }
16 return count;
17 }
18
19 private boolean dfs(int[][] grid, int r, int c) {
20 if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length) return false;
21 if (grid[r][c] == 1) return true;
22
23 grid[r][c] = 1; // sink
24
25 // Important: Evaluate all 4 directions without short-circuiting!
26 boolean down = dfs(grid, r + 1, c);
27 boolean up = dfs(grid, r - 1, c);
28 boolean right = dfs(grid, r, c + 1);
29 boolean left = dfs(grid, r, c - 1);
30
31 return down && up && right && left;
32 }
33 }
34
35 public static void main(String[] args) {
36 Solution sol = new Solution();
37 int[][] grid = {
38 {1, 1, 1, 1},
39 {1, 0, 0, 1},
40 {1, 0, 0, 1},
41 {1, 1, 1, 1}
42 };
43 System.out.println("Closed Islands: " + sol.closedIsland(grid));
44 }
45}

Time & Space Complexity

  • Time complexity: O(m * n) — Single linear pass exploring each cell once.
  • Space complexity: O(m * n) — O(m * n) recursion call stack.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Component DFS with Boolean Closed FlagO(M * N)O(M * N)For every 0, run DFS and maintain a boolean flag isClosed = true. If any node in the component reaches a border, set isClosed = false.Boolean flag aggregation across branches.
2.Better — BFS Boundary Flood FillO(M * N)O(M * N)Enqueue all boundary 0s into a BFS queue. Flip connected 0s to 1. Then BFS interior 0s to count closed islands.Queue operations.
3.Optimal — 2-Phase Boundary DFS PruningOptimalO(M * N)O(M * N) call stackPhase 1: Run DFS from all border cells (r == 0, r == m-1, c == 0, c == n-1), turning connected 0s to 1s. Phase 2: Traverse interior, each 0 found increments closed island count and triggers DFS.None; theoretical optimum.

Common Pitfalls & Crucial Edge Cases

Off-by-One Errors

Incorrect boundary indexing when adjusting pointers or array slices.

Integer Overflow

Using 32-bit signed integer types when accumulative operations exceed 231 - 1 in C++/Java.

Unnecessary Memory Allocation

Allocating large auxiliary arrays or objects inside inner loops causing GC overhead.

Failing to Reset Loop State

Not re-initializing state variables or counters between iterations or subproblems.

Crucial Edge Cases to Validate:

  • All 1s matrix — No land, returns 0.
  • All 0s matrix — All land touches boundaries, Phase 1 sinks everything, returns 0.
  • Small 1xN or Mx1 grid — All cells are border cells, always returns 0.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Highlight the problem's inversion (0 is land, 1 is water) to show attention to detail.
  2. Present the 2-phase approach: 1. Clean the boundary, 2. Count the interior.
  3. Explain why this pattern also solves 'Surrounded Regions' and 'Number of Enclaves'.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the optimal time and auxiliary space complexity for Number of Closed Islands?

2.Why is the brute force approach suboptimal for large inputs in Number of Closed Islands?

3.Which data structure or technique enables the optimal solution for Number of Closed Islands?

Back to DSA Sheet