Count Sub Islands

Medium
452.

Count Sub Islands

Count Sub Islands is a medium coding problem on arrays, depth-first search and matrix, asked in Amazon, Google and Twitter interviews.

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 <= 12
  • grid2 has the same dimensions as grid1.
  • Cells are 0 or 1.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} grid1
 * @param {number[][]} grid2
 * @return {number}
 */
var countSubIslands = function(grid1, grid2) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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 <= 12
  • grid2 has the same dimensions as grid1.
  • Cells are 0 or 1.

Hints for Count Sub Islands

  1. Hint 1

    Walk each island of grid2 once with a DFS or BFS.

  2. Hint 2

    While walking, check every cell against grid1 and remember whether any cell failed.

  3. 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

  1. For each unvisited land cell of grid2, DFS/BFS its island.
  2. Set contained = false if a visited cell is water in grid1.
  3. 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 count

Java

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)