Number of Closed Islands — Solution in Python, Java & C++
Number of Closed Islands solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Number of Closed Islands is a medium coding problem on arrays, depth-first search and matrix, asked in Amazon, Google and Uber interviews.
- Difficulty: Medium
- Topics: Arrays, Depth-First Search, Matrix, Breadth-First Search, Union Find
- Asked at: Amazon, Google, Uber
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given a 2-D grid where 0 is land and 1 is water. An island is a maximal group of 0s connected horizontally or vertically.
An island is closed if it is completely surrounded by water — that is, none of its cells lies on the border of the grid. Return the number of closed islands.
Example 1
Input: grid = [[1,1,1,1,1],[1,0,0,0,1],[1,0,1,0,1],[1,0,0,0,1],[1,1,1,1,1]]
Output: 1
Example 2
Input: grid = [[0,0,1],[1,1,1],[1,1,1]]
Output: 0
Explanation: The only island touches the border.
Example 3
Input: grid = [[1,1,1],[1,0,1],[1,1,1]]
Output: 1
Constraints
1 <= grid.length, grid[i].length <= 8grid[i][j] is 0 or 1.
Hints for Number of Closed Islands
Hint 1
Flood-fill each unvisited land cell to collect its whole island.
Hint 2
While filling, note whether any cell of the island sits on row 0, row m-1, column 0 or column n-1.
Hint 3
Count the island only if no such cell was found.
How to solve Number of Closed Islands
Flood-fill each unvisited land cell to collect its island, noting whether any cell lies on the border; count the island only if none does.
Approach
- For each unvisited
0, start a DFS/BFS marking cells seen. - During the fill, set
closed = falseif a cell is on row 0, row m-1, column 0 or column n-1. - After the fill, count the island if
closedis still true.
Why it works
An island is closed exactly when it has no border cell, and the fill visits every cell of the island, so the flag is decided correctly.
Complexity
- Time —
O(m · n) - Space —
O(m · n)
Pitfalls
- Do not abort the fill on a border cell — the rest of that island must still be marked seen, or it will be recounted.
- Here
0is land and1is water, the reverse of the usual convention.
Reference solution
Python
def closedIsland(grid) -> int:
m, n = len(grid), len(grid[0])
seen = [[False] * n for _ in range(m)]
count = 0
for sr in range(m):
for sc in range(n):
if grid[sr][sc] != 0 or seen[sr][sc]:
continue
stack = [(sr, sc)]
seen[sr][sc] = True
closed = True
while stack:
r, c = stack.pop()
if r == 0 or r == m - 1 or c == 0 or c == n - 1:
closed = False
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 and not seen[nr][nc]:
seen[nr][nc] = True
stack.append((nr, nc))
if closed:
count += 1
return countJava
public static int closedIsland(int[][] grid) {
int m = grid.length, n = grid[0].length;
boolean[][] seen = new boolean[m][n];
int[][] steps = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
int count = 0;
for (int sr = 0; sr < m; sr++) {
for (int sc = 0; sc < n; sc++) {
if (grid[sr][sc] != 0 || seen[sr][sc]) continue;
Deque<int[]> stack = new ArrayDeque<>();
stack.push(new int[]{sr, sc});
seen[sr][sc] = true;
boolean closed = true;
while (!stack.isEmpty()) {
int[] cell = stack.pop();
int r = cell[0], c = cell[1];
if (r == 0 || r == m - 1 || c == 0 || c == n - 1) closed = false;
for (int[] d : steps) {
int nr = r + d[0], nc = c + d[1];
if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] == 0 && !seen[nr][nc]) {
seen[nr][nc] = true;
stack.push(new int[]{nr, nc});
}
}
}
if (closed) count++;
}
}
return count;
}C++
int closedIsland(vector<vector<int>>& grid) {
int m = (int) grid.size(), n = (int) grid[0].size();
vector<vector<bool>> seen(m, vector<bool>(n, false));
int dr[4] = {-1, 1, 0, 0};
int dc[4] = {0, 0, -1, 1};
int count = 0;
for (int sr = 0; sr < m; sr++) {
for (int sc = 0; sc < n; sc++) {
if (grid[sr][sc] != 0 || seen[sr][sc]) continue;
vector<pair<int, int>> stack;
stack.push_back(make_pair(sr, sc));
seen[sr][sc] = true;
bool closed = true;
while (!stack.empty()) {
pair<int, int> cell = stack.back();
stack.pop_back();
int r = cell.first, c = cell.second;
if (r == 0 || r == m - 1 || c == 0 || c == n - 1) closed = false;
for (int k = 0; k < 4; k++) {
int nr = r + dr[k], nc = c + dc[k];
if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] == 0 && !seen[nr][nc]) {
seen[nr][nc] = true;
stack.push_back(make_pair(nr, nc));
}
}
}
if (closed) count++;
}
}
return count;
}JavaScript
var closedIsland = function(grid) {
const m = grid.length, n = grid[0].length;
const seen = [];
for (let r = 0; r < m; r++) seen.push(new Array(n).fill(false));
let count = 0;
for (let sr = 0; sr < m; sr++) {
for (let sc = 0; sc < n; sc++) {
if (grid[sr][sc] !== 0 || seen[sr][sc]) continue;
const stack = [[sr, sc]];
seen[sr][sc] = true;
let closed = true;
while (stack.length > 0) {
const cell = stack.pop();
const r = cell[0], c = cell[1];
if (r === 0 || r === m - 1 || c === 0 || c === n - 1) closed = false;
const steps = [[r - 1, c], [r + 1, c], [r, c - 1], [r, c + 1]];
for (let s = 0; s < 4; s++) {
const nr = steps[s][0], nc = steps[s][1];
if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] === 0 && !seen[nr][nc]) {
seen[nr][nc] = true;
stack.push([nr, nc]);
}
}
}
if (closed) count++;
}
}
return count;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Depth-First Search (DFS)