About usWhy usInstructorsReviewsCostFAQContactBlogRegister for Webinar
Our June 2021 cohorts are filling up quickly. Join our free webinar to Uplevel your career

Count Islands Problem

Counting the number of islands is a commonly asked graph interview question at tech interviews. Here, we show you how to solve it using DFS and BFS.

Count Islands Problem Statement

Given a two-dimensional matrix of 0s and 1s, find the number of islands.

An island is a group of connected 1s or a standalone 1. A cell in the matrix can be connected to up to 8 neighbors: 2 vertical, 2 horizontal and 4 diagonal.

Example

{
"matrix": [
[1, 1, 0, 0, 0],
[0, 1, 0, 0, 1],
[1, 0, 0, 1, 1],
[0, 0, 0, 0, 0],
[1, 0, 1, 0, 1]
]
}

Output:

5

Notes

  • Use as little extra memory as possible.
  • Solve the problem without allocating a visited matrix.

Constraints:

  • 1 <= number of rows <= 450
  • 1 <= number of columns <= 450

The problem is easy but there is one very important thing to learn. We recommend reading through the whole editorial even if your solution passed all tests.

Count Islands Solution 1: Depth First Search

Treat the matrix like a graph and do a simple DFS or BFS.

We are not allowed to use a visited matrix, but we can modify the input matrix itself! When a node is visited, change its value from 1 to 0.

Time Complexity

O(n * m).

Time complexity of BFS or DFS is O(V + E), in our case it will be O(n * m + 8 * n * m) that is O(n * m).

Auxiliary Space Used

O(n * m) for the DFS solution. The space is used by the call stack because the solution is recursive. If we had used an iterative DFS implementation, we would use a stack and same O(n * m) auxiliary space for that.

Consider the worst case for DFS:

1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1

Code For Count Islands Solution 1: Depth First Search


/*
Asymptotic complexity in terms of \`n\` and \`m\` dimensions of the input matrix:
* Time: O(n * m).
* Auxiliary space: O(n * m).
* Total space: O(n * m).
*/

// All 8 directions. Consider as pair: {add_r[i], add_r[i]}.
const int add_r[8] = {0, -1, -1, -1, 0, 1, 1, 1};
const int add_c[8] = {-1, -1, 0, 1, 1, 1, 0, -1};

// Note that we are passing matrix by reference. Passing by value will not work because we are doing
// modifications in matrix. So either pass by reference or use global variable.
void dfs(int row, int column, vector<vector<int>> &matrix) {
    matrix[row][column] = 0;
    for (int i = 0; i < 8; i++) {
        // Try to visit all 8 neighbours.
        int new_row = row + add_r[i];
        int new_column = column + add_c[i];

        // Out of the matrix.
        if (new_row < 0 || new_row >= matrix.size() || new_column < 0 || new_column >= matrix[0].size()) {
            continue;
        }

        if (matrix[new_row][new_column]) {
            dfs(new_row, new_column, matrix);
        }
    }
}

int count_islands(vector<vector<int>> &matrix) {
    int islands = 0;
    int n = matrix.size();
    int m = matrix[0].size();

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            // When we find unvisited node, visit it and visit all the reachable nodes.
            if (matrix[i][j]) {
                islands++;
                dfs(i, j, matrix);
            }
        }
    }
    return islands;
}

Count Islands Solution 2: Breadth First Search

DFS would make almost n * m nested recursive calls; that takes O(n * m) space.

BFS solution, on the other hand, uses just O(max(n, m)) of auxiliary space.

The worst-case for BFS is similar to that of DFS, where all entries of matrix are 1. Consider the worst-case scenario, at some point of time all the nodes of the last row and last column will be in the queue. The queue will then take O(n + m) = O(max(n, m)) space.

This difference in used space between the two algorithms can affect performance in some real life cases.

Space Complexity

O(n * m), due to input size and auxiliary space used.

Code For Count Islands Solution 2: Breadth First Search


/*
Asymptotic complexity in terms of \`n\` and \`m\` dimensions of the input matrix:
* Time: O(n * m).
* Auxiliary space: O(max(n, m)).
* Total space: O(n * m).
*/

// All 8 directions. Consider as pair: {add_r[i], add_r[i]}.
const int add_r[8] = {0, -1, -1, -1, 0, 1, 1, 1};
const int add_c[8] = {-1, -1, 0, 1, 1, 1, 0, -1};

void bfs(int row, int column, vector<vector<int>> &matrix) {
    queue<pair<int, int>> q;
    q.push({row, column});
    matrix[row][column] = 0;

    while (q.empty() == false) {
        pair<int, int> head = q.front();
        q.pop();
        int current_row = head.first;
        int current_column = head.second;

        for (int i = 0; i < 8; i++) {
            // Try to visit all 8 neighbours.
            int new_row = current_row + add_r[i];
            int new_column = current_column + add_c[i];

            // Out of the matrix.
            if (new_row < 0 || new_row >= matrix.size() || new_column < 0 || new_column >= matrix[0].size()) {
                continue;
            }

            if (matrix[new_row][new_column]) {
                /*
                We could have marked as 0 when we pop-up the element from the queue and not here.
                This will also give correct answer, but that is not the correct way! If we do
                that, same element will be pushed multiple times in the queue (that will increase
                running time and queue size unnecessarily)! Take some examples and try to figure
                it out.
                */
                matrix[new_row][new_column] = 0;
                q.push({new_row, new_column});
            }
        }
    }
}

int count_islands(vector<vector<int>> &matrix) {
    int islands = 0;
    int n = matrix.size();
    int m = matrix[0].size();

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            // When we find unvisited node, visit it and visit all the reachable nodes.
            if (matrix[i][j]) {
                islands++;
                bfs(i, j, matrix);
            }
        }
    }
    return islands;
}

We hope that these solutions to counting islands have helped you level up your coding skills. You can expect graph problems like counting islands at top tech companies like Amazon and Google.

If you are preparing for a tech interview at FAANG or any other Tier-1 tech company, register for Interview Kickstart’s FREE webinar to understand the best way to prepare.

Interview Kickstart offers interview preparation courses taught by FAANG+ tech leads and seasoned hiring managers. Our programs include a comprehensive curriculum, unmatched teaching methods, and career coaching to help you nail your next tech interview.

We offer 17 interview preparation courses, each tailored to a specific engineering domain or role, including the most in-demand and highest-paying domains and roles, such as:

‍To learn more, register for the FREE webinar.

Try yourself in the Editor

Note: Input and Output will already be taken care of.

Recommended Posts

All Posts