Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Graphs

Number of Islands

Medium · Graphs · Asked at Amazon, Google, Microsoft, Meta, Uber

In a grid of 1 (land) and 0 (water), an island is a group of land cells connected horizontally or vertically. Count the islands.

Input

First line: r c. Next r lines: c values (0 or 1) separated by spaces.

Output

The number of islands.

Constraints

Example 1

Input

4 5
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1

Output

3

Example 2

Input

1 1
0

Output

0

Hints

  1. Each island is a connected component of land cells in a grid graph.
  2. Scan the grid; on an unvisited land cell, count one island and flood-fill (BFS) the whole island, marking it as water/visited.

Approach

Go through every cell. When you find a 1, count a new island and BFS from it in the four directions, turning every reached land cell into 0 so it isn't counted again. Every cell is enqueued at most once. With a 300 × 300 grid, a recursive DFS could go 90 000 calls deep, so an explicit queue is safer.

Complexity: O(r·c) time · O(r·c) space

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    int r, c;
    cin >> r >> c;
    vector<vector<int>> g(r, vector<int>(c));
    for (auto &row : g)
        for (auto &x : row) cin >> x;
    int dr[] = {1, -1, 0, 0}, dc[] = {0, 0, 1, -1};
    int islands = 0;
    for (int i = 0; i < r; i++)
        for (int j = 0; j < c; j++) {
            if (g[i][j] != 1) continue;
            islands++;
            queue<pair<int, int>> q;
            q.push({i, j});
            g[i][j] = 0;
            while (!q.empty()) {
                auto cell = q.front();
                q.pop();
                for (int d = 0; d < 4; d++) {
                    int x = cell.first + dr[d], y = cell.second + dc[d];
                    if (x >= 0 && x < r && y >= 0 && y < c && g[x][y] == 1) {
                        g[x][y] = 0;
                        q.push({x, y});
                    }
                }
            }
        }
    cout << islands << "\n";
    return 0;
}

Python solution

import sys
from collections import deque

data = list(map(int, sys.stdin.read().split()))
r, c = data[0], data[1]
g = [data[2 + i * c : 2 + (i + 1) * c] for i in range(r)]
islands = 0
for i in range(r):
    for j in range(c):
        if g[i][j] != 1:
            continue
        islands += 1
        g[i][j] = 0
        q = deque([(i, j)])
        while q:
            x, y = q.popleft()
            for nx, ny in ((x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)):
                if 0 <= nx < r and 0 <= ny < c and g[nx][ny] == 1:
                    g[nx][ny] = 0
                    q.append((nx, ny))
print(islands)

Java solution

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int r = sc.nextInt(), c = sc.nextInt();
        int[][] g = new int[r][c];
        for (int i = 0; i < r; i++)
            for (int j = 0; j < c; j++) g[i][j] = sc.nextInt();
        int[] dr = {1, -1, 0, 0}, dc = {0, 0, 1, -1};
        int islands = 0;
        ArrayDeque<int[]> q = new ArrayDeque<>();
        for (int i = 0; i < r; i++)
            for (int j = 0; j < c; j++) {
                if (g[i][j] != 1) continue;
                islands++;
                g[i][j] = 0;
                q.add(new int[] {i, j});
                while (!q.isEmpty()) {
                    int[] cell = q.poll();
                    for (int d = 0; d < 4; d++) {
                        int x = cell[0] + dr[d], y = cell[1] + dc[d];
                        if (x >= 0 && x < r && y >= 0 && y < c && g[x][y] == 1) {
                            g[x][y] = 0;
                            q.add(new int[] {x, y});
                        }
                    }
                }
            }
        System.out.println(islands);
    }
}

Solve Number of Islands online · All practice problems