Count Sub Islands — Solution in Python, Java & C++
Count Sub Islands solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Count Sub Islands is a medium coding problem on arrays, depth-first search and matrix, asked in Amazon, Google and Twitter interviews.
- Difficulty: Medium
- Topics: Arrays, Depth-First Search, Matrix, Breadth-First Search, Union Find
- Asked at: Amazon, Google, Twitter
- 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 two binary matrices grid1 and grid2 of the same size, where 1 is land and 0 is water. An island is a maximal group of land cells connected up, down, left or right.
An island in grid2 is a sub-island if every one of its cells is also land in grid1. Return the number of sub-islands.
Example 1
Input: grid1 = [[1,1],[0,1]], grid2 = [[1,1],[0,0]]
Output: 1
Example 2
Input: grid1 = [[1,0],[0,1]], grid2 = [[1,0],[0,1]]
Output: 2
Example 3
Input: grid1 = [[0]], grid2 = [[1]]
Output: 0
Constraints
1 <= grid1.length, grid1[i].length <= 12grid2 has the same dimensions as grid1.Cells are 0 or 1.
Hints for Count Sub Islands
Hint 1
Walk each island of
grid2once with a DFS or BFS.Hint 2
While walking, check every cell against
grid1and remember whether any cell failed.Hint 3
Do not stop the traversal early on a failure — you still need to mark the whole island as visited.
How to solve Count Sub Islands
Traverse each island of grid2, checking every cell against grid1 and remembering whether any failed; count islands where none did.
Approach
- For each unvisited land cell of
grid2, DFS/BFS its island. - Set
contained = falseif a visited cell is water ingrid1. - Count the island if
contained.
Why it works
An island is a sub-island iff all its cells are land in grid1, and the traversal examines every cell of the island exactly once.
Complexity
- Time —
O(m · n) - Space —
O(m · n)
Pitfalls
- Do not stop the traversal on a failure — the rest of the island must still be marked visited.
Reference solution
Python
def countSubIslands(grid1, grid2) -> int:
rows, cols = len(grid2), len(grid2[0])
seen = [[False] * cols for _ in range(rows)]
count = 0
for r in range(rows):
for c in range(cols):
if grid2[r][c] != 1 or seen[r][c]:
continue
seen[r][c] = True
stack = [(r, c)]
contained = True
while stack:
cr, cc = stack.pop()
if grid1[cr][cc] != 1:
contained = False
for nr, nc in ((cr + 1, cc), (cr - 1, cc), (cr, cc + 1), (cr, cc - 1)):
if 0 <= nr < rows and 0 <= nc < cols and grid2[nr][nc] == 1 and not seen[nr][nc]:
seen[nr][nc] = True
stack.append((nr, nc))
if contained:
count += 1
return countJava
public static int countSubIslands(int[][] grid1, int[][] grid2) {
int rows = grid2.length, cols = grid2[0].length;
boolean[][] seen = new boolean[rows][cols];
int[] dr = {1, -1, 0, 0};
int[] dc = {0, 0, 1, -1};
int count = 0;
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (grid2[r][c] != 1 || seen[r][c]) continue;
seen[r][c] = true;
Deque<int[]> stack = new ArrayDeque<>();
stack.push(new int[]{r, c});
boolean contained = true;
while (!stack.isEmpty()) {
int[] cell = stack.pop();
if (grid1[cell[0]][cell[1]] != 1) contained = false;
for (int d = 0; d < 4; d++) {
int nr = cell[0] + dr[d], nc = cell[1] + dc[d];
if (nr < 0 || nc < 0 || nr >= rows || nc >= cols) continue;
if (grid2[nr][nc] != 1 || seen[nr][nc]) continue;
seen[nr][nc] = true;
stack.push(new int[]{nr, nc});
}
}
if (contained) count++;
}
}
return count;
}C++
int countSubIslands(vector<vector<int>>& grid1, vector<vector<int>>& grid2) {
int rows = (int) grid2.size(), cols = (int) grid2[0].size();
vector<vector<bool>> seen(rows, vector<bool>(cols, false));
int dr[4] = {1, -1, 0, 0};
int dc[4] = {0, 0, 1, -1};
int count = 0;
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (grid2[r][c] != 1 || seen[r][c]) continue;
seen[r][c] = true;
vector<pair<int,int>> stack;
stack.push_back(make_pair(r, c));
bool contained = true;
while (!stack.empty()) {
pair<int,int> cell = stack.back();
stack.pop_back();
if (grid1[cell.first][cell.second] != 1) contained = false;
for (int d = 0; d < 4; d++) {
int nr = cell.first + dr[d], nc = cell.second + dc[d];
if (nr < 0 || nc < 0 || nr >= rows || nc >= cols) continue;
if (grid2[nr][nc] != 1 || seen[nr][nc]) continue;
seen[nr][nc] = true;
stack.push_back(make_pair(nr, nc));
}
}
if (contained) count++;
}
}
return count;
}JavaScript
var countSubIslands = function(grid1, grid2) {
const rows = grid2.length, cols = grid2[0].length;
const seen = [];
for (let r = 0; r < rows; r++) {
const row = [];
for (let c = 0; c < cols; c++) row.push(false);
seen.push(row);
}
const dr = [1, -1, 0, 0], dc = [0, 0, 1, -1];
let count = 0;
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
if (grid2[r][c] !== 1 || seen[r][c]) continue;
seen[r][c] = true;
const stack = [[r, c]];
let contained = true;
while (stack.length > 0) {
const cell = stack.pop();
if (grid1[cell[0]][cell[1]] !== 1) contained = false;
for (let d = 0; d < 4; d++) {
const nr = cell[0] + dr[d], nc = cell[1] + dc[d];
if (nr < 0 || nc < 0 || nr >= rows || nc >= cols) continue;
if (grid2[nr][nc] !== 1 || seen[nr][nc]) continue;
seen[nr][nc] = true;
stack.push([nr, nc]);
}
}
if (contained) 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)