Number of Closed Islands
Number of Closed Islands is a medium graphs problem solved with the matrix graphs pattern.
The best approach, optimal (sink border land, then count), runs in O(m · n) time and O(m · n) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from dfs per island with a border flag up.
Problem
You are given an m x n grid where 0 means land and 1 means water. An island is a group of land cells connected horizontally or vertically.
An island is closed if it does not touch the outer border of the grid, i.e. it is completely surrounded by water on its left, right, top and bottom. Return the number of closed islands.
Examples
Example 1
- Input
grid = [[1,1,1,1,1],[1,0,0,1,1],[1,0,1,0,1],[1,1,1,1,1]]- Output
2- Why
- Land {(1,1), (1,2), (2,1)} and the single cell (2,3) are both surrounded by water on every side.
Example 2
- Input
grid = [[1,1,1,1],[1,0,1,0],[1,1,1,1]]- Output
1- Why
- Cell (1,1) is closed, but cell (1,3) lies on the right border, so it is not.
Example 3
- Input
grid = [[0,0],[0,0]]- Output
0- Why
- The only island touches the border.
Constraints
1 <= grid.length, grid[0].length <= 100grid[i][j]is0(land) or1(water)
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 13 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| DFS per island with a border flag | O(m · n) | O(m · n) |
| Optimal (sink border land, then count) | O(m · n) | O(m · n) |
1DFS per island with a border flag
O(m · n)Every cell is visited once.O(m · n)The recursion can be as deep as the largest island, up to m · n cells.Visit every unvisited land cell with a recursive DFS that marks the whole island. The DFS reports whether any of the island's cells is on the border. Count the islands for which it never touched the border. The DFS must explore the entire island even after it finds a border cell, so that no part of it is counted later.
- For every land cell not yet visited, run dfs(r, c).
- dfs marks the cell, returns false if the cell is on the border, and combines the results of all four neighbours with a non-short-circuiting AND.
- If dfs returns true, increment the count.
- Return the count.
class Solution {
public int closedIsland(int[][] grid) {
int m = grid.length, n = grid[0].length, count = 0;
boolean[][] seen = new boolean[m][n];
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
if (grid[r][c] == 0 && !seen[r][c] && dfs(grid, seen, r, c)) count++;
}
}
return count;
}
private boolean dfs(int[][] grid, boolean[][] seen, int r, int c) {
int m = grid.length, n = grid[0].length;
if (r < 0 || c < 0 || r >= m || c >= n) return false;
if (grid[r][c] == 1 || seen[r][c]) return true;
seen[r][c] = true;
boolean closed = r > 0 && c > 0 && r < m - 1 && c < n - 1;
closed &= dfs(grid, seen, r + 1, c);
closed &= dfs(grid, seen, r - 1, c);
closed &= dfs(grid, seen, r, c + 1);
closed &= dfs(grid, seen, r, c - 1);
return closed;
}
}class Solution:
def closedIsland(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
seen = [[False] * n for _ in range(m)]
def dfs(r: int, c: int) -> bool:
if r < 0 or c < 0 or r >= m or c >= n:
return False
if grid[r][c] == 1 or seen[r][c]:
return True
seen[r][c] = True
closed = 0 < r < m - 1 and 0 < c < n - 1
# evaluate every neighbour (no short-circuit) so the whole island is marked
results = [dfs(r + 1, c), dfs(r - 1, c), dfs(r, c + 1), dfs(r, c - 1)]
return closed and all(results)
count = 0
for r in range(m):
for c in range(n):
if grid[r][c] == 0 and not seen[r][c] and dfs(r, c):
count += 1
return countclass Solution {
public:
int closedIsland(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size(), count = 0;
vector<vector<bool>> seen(m, vector<bool>(n, false));
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
if (grid[r][c] == 0 && !seen[r][c] && dfs(grid, seen, r, c)) count++;
}
}
return count;
}
private:
bool dfs(vector<vector<int>>& grid, vector<vector<bool>>& seen, int r, int c) {
int m = grid.size(), n = grid[0].size();
if (r < 0 || c < 0 || r >= m || c >= n) return false;
if (grid[r][c] == 1 || seen[r][c]) return true;
seen[r][c] = true;
bool closed = r > 0 && c > 0 && r < m - 1 && c < n - 1;
closed &= dfs(grid, seen, r + 1, c);
closed &= dfs(grid, seen, r - 1, c);
closed &= dfs(grid, seen, r, c + 1);
closed &= dfs(grid, seen, r, c - 1);
return closed;
}
};function closedIsland(grid) {
const m = grid.length, n = grid[0].length;
const seen = Array.from({ length: m }, () => new Array(n).fill(false));
const dfs = (r, c) => {
if (r < 0 || c < 0 || r >= m || c >= n) return false;
if (grid[r][c] === 1 || seen[r][c]) return true;
seen[r][c] = true;
let closed = r > 0 && c > 0 && r < m - 1 && c < n - 1;
const a = dfs(r + 1, c), b = dfs(r - 1, c), d = dfs(r, c + 1), e = dfs(r, c - 1);
return closed && a && b && d && e;
};
let count = 0;
for (let r = 0; r < m; r++) {
for (let c = 0; c < n; c++) {
if (grid[r][c] === 0 && !seen[r][c] && dfs(r, c)) count++;
}
}
return count;
}2Optimal (sink border land, then count)
O(m · n)Each cell is turned into water at most once.O(m · n)The BFS queue can hold O(m · n) cells in the worst case; the grid itself is reused as the visited marker.First flood every island that touches the border, turning its cells into water, since none of them can be closed. After that, every remaining island is closed, so simply count the islands with one more flood fill each. Using an explicit BFS queue keeps the memory bounded even for a huge snake-shaped island.
- For every land cell on the border, flood its island into water with BFS.
- Scan the inner cells; for each remaining land cell, increment the count and flood its island.
- Return the count.
class Solution {
private static final int[][] DIRS = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
public int closedIsland(int[][] grid) {
int m = grid.length, n = grid[0].length;
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
boolean border = r == 0 || c == 0 || r == m - 1 || c == n - 1;
if (border && grid[r][c] == 0) sink(grid, r, c);
}
}
int count = 0;
for (int r = 1; r < m - 1; r++) {
for (int c = 1; c < n - 1; c++) {
if (grid[r][c] == 0) {
count++;
sink(grid, r, c);
}
}
}
return count;
}
private void sink(int[][] grid, int sr, int sc) {
int m = grid.length, n = grid[0].length;
Deque<int[]> queue = new ArrayDeque<>();
grid[sr][sc] = 1;
queue.add(new int[] { sr, sc });
while (!queue.isEmpty()) {
int[] cell = queue.poll();
for (int[] d : DIRS) {
int r = cell[0] + d[0], c = cell[1] + d[1];
if (r >= 0 && c >= 0 && r < m && c < n && grid[r][c] == 0) {
grid[r][c] = 1;
queue.add(new int[] { r, c });
}
}
}
}
}class Solution:
def closedIsland(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
def sink(sr: int, sc: int) -> None:
grid[sr][sc] = 1
queue = deque([(sr, sc)])
while queue:
r, c = queue.popleft()
for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] == 0:
grid[nr][nc] = 1
queue.append((nr, nc))
for r in range(m):
for c in range(n):
border = r == 0 or c == 0 or r == m - 1 or c == n - 1
if border and grid[r][c] == 0:
sink(r, c)
count = 0
for r in range(1, m - 1):
for c in range(1, n - 1):
if grid[r][c] == 0:
count += 1
sink(r, c)
return countclass Solution {
public:
int closedIsland(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
bool border = r == 0 || c == 0 || r == m - 1 || c == n - 1;
if (border && grid[r][c] == 0) sink(grid, r, c);
}
}
int count = 0;
for (int r = 1; r < m - 1; r++) {
for (int c = 1; c < n - 1; c++) {
if (grid[r][c] == 0) {
count++;
sink(grid, r, c);
}
}
}
return count;
}
private:
void sink(vector<vector<int>>& grid, int sr, int sc) {
int m = grid.size(), n = grid[0].size();
int dr[4] = {1, -1, 0, 0}, dc[4] = {0, 0, 1, -1};
queue<pair<int, int>> q;
grid[sr][sc] = 1;
q.push({sr, sc});
while (!q.empty()) {
auto [r0, c0] = q.front();
q.pop();
for (int k = 0; k < 4; k++) {
int r = r0 + dr[k], c = c0 + dc[k];
if (r >= 0 && c >= 0 && r < m && c < n && grid[r][c] == 0) {
grid[r][c] = 1;
q.push({r, c});
}
}
}
}
};function closedIsland(grid) {
const m = grid.length, n = grid[0].length;
const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
const sink = (sr, sc) => {
grid[sr][sc] = 1;
const queue = [[sr, sc]];
let head = 0;
while (head < queue.length) {
const [r0, c0] = queue[head++];
for (const [dr, dc] of dirs) {
const r = r0 + dr, c = c0 + dc;
if (r >= 0 && c >= 0 && r < m && c < n && grid[r][c] === 0) {
grid[r][c] = 1;
queue.push([r, c]);
}
}
}
};
for (let r = 0; r < m; r++) {
for (let c = 0; c < n; c++) {
const border = r === 0 || c === 0 || r === m - 1 || c === n - 1;
if (border && grid[r][c] === 0) sink(r, c);
}
}
let count = 0;
for (let r = 1; r < m - 1; r++) {
for (let c = 1; c < n - 1; c++) {
if (grid[r][c] === 0) {
count++;
sink(r, c);
}
}
}
return count;
}Edge cases to test
- A grid with only one row or one column (nothing can be closed)
- All water or all land
- An island that reaches the border through a long thin path
- Islands nested inside a ring of water that sits inside a bigger island
Hints
Hint 1
Note the encoding: here 0 is land and 1 is water.
Hint 2
An island is closed exactly when none of its cells is on the outer border of the grid.
Hint 3
Remove (flood) every island that touches the border first; every island that is left is closed.
FAQ
What is the best time complexity for Number of Closed Islands?
Optimal (sink border land, then count) runs in O(m · n) time and O(m · n) extra space. Each cell is turned into water at most once.
Which pattern does Number of Closed Islands use?
It is a graphs problem that uses the matrix graphs pattern. Other problems with the same pattern: Flood Fill, Maximum Number of Points From Grid Queries, Contain Virus.
Is there a brute force solution for Number of Closed Islands?
Yes. DFS per island with a border flag takes O(m · n) time and O(m · n) space. Visit every unvisited land cell with a recursive DFS that marks the whole island.
Which edge cases should I test for Number of Closed Islands?
A grid with only one row or one column (nothing can be closed); All water or all land; An island that reaches the border through a long thin path; Islands nested inside a ring of water that sits inside a bigger island.