SimuVedaAlgorithms Lab Open in the lab

Graphs / Intermediate

Number of Islands (Flood Fill) Visualizer

Scan every cell. Each time you land on unvisited land, that is a new island: count it, then sink the whole island with DFS so it is never counted again.

Start the Number of Islands (Flood Fill) simulation → Step forward and back, change the input, follow the code line by line in Java, Python, C++, C or JavaScript. Free, no sign-up.

Time and space complexity

Best timeO(R·C)
Average timeO(R·C)
Worst timeO(R·C)
Extra spaceO(R·C)

Worked example, step by step

The same steps the simulator shows, on a small input.

  1. Scan the map row by row. ■ is unvisited land; numbers mark which island a cell belongs to.
  2. (0, 0) is new land. That makes island 1. Sink all of it.
  3. Mark (0, 0) as part of island 1, then try its 4 neighbours.
  4. Mark (1, 0) as part of island 1, then try its 4 neighbours.
  5. Mark (1, 1) as part of island 1, then try its 4 neighbours.
  6. Mark (0, 1) as part of island 1, then try its 4 neighbours.
  7. (1, 3) is new land. That makes island 2. Sink all of it.
  8. Mark (1, 3) as part of island 2, then try its 4 neighbours.
  9. (2, 2) is new land. That makes island 3. Sink all of it.
  10. Mark (2, 2) as part of island 3, then try its 4 neighbours.
  11. (3, 3) is new land. That makes island 4. Sink all of it.
  12. Mark (3, 3) as part of island 4, then try its 4 neighbours.
  13. Mark (3, 4) as part of island 4, then try its 4 neighbours.
  14. Done. The map has 4 islands.

Try it with your own input →

Number of islands (flood fill) in Java, Python, C++, C and JavaScript

int numIslands(char[][] g) {
  int count = 0;
  for (int r = 0; r < g.length; r++)
    for (int c = 0; c < g[0].length; c++)
      if (g[r][c] == '1') {
        count++;
        sink(g, r, c);
      }
  return count;
}
void sink(char[][] g, int r, int c) {
  if (r < 0 || c < 0 || r >= g.length || c >= g[0].length || g[r][c] != '1') return;
  g[r][c] = '0';
  sink(g, r + 1, c); sink(g, r - 1, c);
  sink(g, r, c + 1); sink(g, r, c - 1);
}
def num_islands(g):
    count = 0
    for r in range(len(g)):
        for c in range(len(g[0])):
            if g[r][c] == '1':
                count += 1
                sink(g, r, c)
    return count

def sink(g, r, c):
    if r < 0 or c < 0 or r >= len(g) or c >= len(g[0]) or g[r][c] != '1':
        return
    g[r][c] = '0'
    sink(g, r + 1, c); sink(g, r - 1, c)
    sink(g, r, c + 1); sink(g, r, c - 1)
void sink(vector<vector<char>>& g, int r, int c);

int numIslands(vector<vector<char>>& g) {
  int count = 0;
  for (int r = 0; r < (int)g.size(); r++)
    for (int c = 0; c < (int)g[0].size(); c++)
      if (g[r][c] == '1') {
        count++;
        sink(g, r, c);
      }
  return count;
}
void sink(vector<vector<char>>& g, int r, int c) {
  if (r < 0 || c < 0 || r >= (int)g.size() || c >= (int)g[0].size() || g[r][c] != '1') return;
  g[r][c] = '0';
  sink(g, r + 1, c); sink(g, r - 1, c);
  sink(g, r, c + 1); sink(g, r, c - 1);
}
#define MAXR 100
int R, C;

void sink(char g[][MAXR], int r, int c);

int numIslands(char g[][MAXR]) {
  int count = 0;
  for (int r = 0; r < R; r++)
    for (int c = 0; c < C; c++)
      if (g[r][c] == '1') {
        count++;
        sink(g, r, c);
      }
  return count;
}
void sink(char g[][MAXR], int r, int c) {
  if (r < 0 || c < 0 || r >= R || c >= C || g[r][c] != '1') return;
  g[r][c] = '0';
  sink(g, r + 1, c); sink(g, r - 1, c);
  sink(g, r, c + 1); sink(g, r, c - 1);
}
function numIslands(g) {
  let count = 0;
  for (let r = 0; r < g.length; r++)
    for (let c = 0; c < g[0].length; c++)
      if (g[r][c] === '1') {
        count++;
        sink(g, r, c);
      }
  return count;
}
function sink(g, r, c) {
  if (r < 0 || c < 0 || r >= g.length || c >= g[0].length || g[r][c] !== '1') return;
  g[r][c] = '0';
  sink(g, r + 1, c); sink(g, r - 1, c);
  sink(g, r, c + 1); sink(g, r, c - 1);
}

In an interview

LeetCode 200, Number of Islands. Same flood fill: 695 Max Area of Island, 733 Flood Fill, 130 Surrounded Regions.

Mention both DFS and BFS. On a huge grid, recursive DFS can overflow the stack, so BFS with a queue is the safer answer.

More graphs