C++ Program to Find Number of Islands

A C++ program to find the number of islands uses a grid traversal with DFS to mark connected land cells; the key code is a DFS function that visits all connected '1's and a loop that counts islands by calling DFS on unvisited land cells.

Examples

Input[[1,1,0,0,0],[1,1,0,0,0],[0,0,1,0,0],[0,0,0,1,1]]

Output3

Input[[1,1,1],[0,1,0],[1,0,1]]

Output1

Input[[0,0,0],[0,0,0],[0,0,0]]

Output0

How to Think About It

Think of the grid as a map where '1' means land and '0' means water. To find islands, scan each cell; when you find land that is not visited, start a search to mark all connected land cells as visited. Each such search counts as one island.

Algorithm

1

Initialize count of islands to zero.

2

Loop through each cell in the grid.

3

If the cell is land and not visited, perform DFS to mark all connected land cells.

4

Increment the island count after each DFS call.

5

Return the total island count.

Code

cpp

#include <iostream>
#include <vector>
using namespace std;

void dfs(int i, int j, vector<vector<int>>& grid, vector<vector<bool>>& visited) {
    int rows = grid.size();
    int cols = grid[0].size();
    if (i < 0 || j < 0 || i >= rows || j >= cols) return;
    if (grid[i][j] == 0 || visited[i][j]) return;
    visited[i][j] = true;
    dfs(i + 1, j, grid, visited);
    dfs(i - 1, j, grid, visited);
    dfs(i, j + 1, grid, visited);
    dfs(i, j - 1, grid, visited);
}

int numIslands(vector<vector<int>>& grid) {
    int rows = grid.size();
    if (rows == 0) return 0;
    int cols = grid[0].size();
    vector<vector<bool>> visited(rows, vector<bool>(cols, false));
    int count = 0;
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (grid[i][j] == 1 && !visited[i][j]) {
                dfs(i, j, grid, visited);
                count++;
            }
        }
    }
    return count;
}

int main() {
    vector<vector<int>> grid = {
        {1,1,0,0,0},
        {1,1,0,0,0},
        {0,0,1,0,0},
        {0,0,0,1,1}
    };
    cout << numIslands(grid) << endl;
    return 0;
}

Output

3

Dry Run

Let's trace the example grid [[1,1,0,0,0],[1,1,0,0,0],[0,0,1,0,0],[0,0,0,1,1]] through the code.

1

Start scanning grid

At (0,0), cell is 1 and not visited, call dfs.

2

DFS marks connected land

Mark (0,0), then recursively mark (0,1), (1,0), (1,1).

3

Increment island count

After DFS finishes, count = 1.

4

Continue scanning

Skip visited land cells, find next unvisited land at (2,2), call dfs.

5

Mark second island

Mark (2,2), count = 2.

6

Find third island

At (3,3), unvisited land found, call dfs to mark (3,3) and (3,4), count = 3.

Step	Action	Island Count
1	Found land at (0,0), DFS marks connected cells	1
2	Found land at (2,2), DFS marks cell	2
3	Found land at (3,3), DFS marks connected cells	3

Why This Works

Step 1: Why DFS?

DFS helps explore all connected land cells from a starting point, ensuring one island is counted once.

Step 2: Marking visited cells

Marking cells as visited prevents counting the same land multiple times.

Step 3: Counting islands

Each DFS call from an unvisited land cell means a new island is found, so increment count.

Alternative Approaches

Breadth-First Search (BFS)

cpp

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

void bfs(int i, int j, vector<vector<int>>& grid, vector<vector<bool>>& visited) {
    int rows = grid.size();
    int cols = grid[0].size();
    queue<pair<int,int>> q;
    q.push({i,j});
    visited[i][j] = true;
    int directions[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
    while (!q.empty()) {
        auto [x,y] = q.front(); q.pop();
        for (auto& d : directions) {
            int nx = x + d[0], ny = y + d[1];
            if (nx >= 0 && ny >= 0 && nx < rows && ny < cols && grid[nx][ny] == 1 && !visited[nx][ny]) {
                visited[nx][ny] = true;
                q.push({nx, ny});
            }
        }
    }
}

int numIslands(vector<vector<int>>& grid) {
    int rows = grid.size();
    if (rows == 0) return 0;
    int cols = grid[0].size();
    vector<vector<bool>> visited(rows, vector<bool>(cols, false));
    int count = 0;
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (grid[i][j] == 1 && !visited[i][j]) {
                bfs(i, j, grid, visited);
                count++;
            }
        }
    }
    return count;
}

int main() {
    vector<vector<int>> grid = {
        {1,1,0,0,0},
        {1,1,0,0,0},
        {0,0,1,0,0},
        {0,0,0,1,1}
    };
    cout << numIslands(grid) << endl;
    return 0;
}

BFS uses a queue and explores neighbors level by level; it is equally effective but may use more memory than DFS.

Union-Find (Disjoint Set)

cpp

#include <iostream>
#include <vector>
using namespace std;

class UnionFind {
    vector<int> parent, rank;
public:
    UnionFind(int n) : parent(n), rank(n, 0) {
        for (int i = 0; i < n; i++) parent[i] = i;
    }
    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }
    void unite(int x, int y) {
        int rx = find(x), ry = find(y);
        if (rx != ry) {
            if (rank[rx] < rank[ry]) parent[rx] = ry;
            else if (rank[ry] < rank[rx]) parent[ry] = rx;
            else {
                parent[ry] = rx;
                rank[rx]++;
            }
        }
    }
};

int numIslands(vector<vector<int>>& grid) {
    int rows = grid.size();
    if (rows == 0) return 0;
    int cols = grid[0].size();
    UnionFind uf(rows * cols);
    int count = 0;
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (grid[i][j] == 1) {
                count++;
                int index = i * cols + j;
                if (i > 0 && grid[i-1][j] == 1) uf.unite(index, (i-1)*cols + j);
                if (j > 0 && grid[i][j-1] == 1) uf.unite(index, i*cols + j - 1);
            }
        }
    }
    vector<bool> rootFound(rows * cols, false);
    int islands = 0;
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (grid[i][j] == 1) {
                int root = uf.find(i * cols + j);
                if (!rootFound[root]) {
                    rootFound[root] = true;
                    islands++;
                }
            }
        }
    }
    return islands;
}

int main() {
    vector<vector<int>> grid = {
        {1,1,0,0,0},
        {1,1,0,0,0},
        {0,0,1,0,0},
        {0,0,0,1,1}
    };
    cout << numIslands(grid) << endl;
    return 0;
}

Union-Find groups connected land cells efficiently; it is good for dynamic connectivity but more complex to implement.

Complexity: O(rows * cols) time, O(rows * cols) space

Time Complexity

Each cell is visited once during DFS/BFS, so the time is proportional to the total number of cells.

Space Complexity

Extra space is used for the visited array and recursion/queue stack, both proportional to grid size.

Which Approach is Fastest?

DFS and BFS have similar performance; Union-Find can be faster for multiple queries but is more complex.

Approach	Time	Space	Best For
DFS	O(rows*cols)	O(rows*cols)	Simple implementation, recursive exploration
BFS	O(rows*cols)	O(rows*cols)	Level-wise exploration, iterative
Union-Find	O(rows*cols * α(n))	O(rows*cols)	Dynamic connectivity, multiple queries