200. Number of Islands

Q: DFS or BFS at Atlassian?

Either is accepted on correctness, but BFS scores higher on the 'discuss tradeoffs' rubric because you can explicitly cite the stack-overflow risk of DFS on a 300x300 all-ones grid. If you go DFS, name the risk out loud.

Q: Why is union-find ever the right answer here?

Only when the input is streaming — cells flip on or off over time. The static one-shot problem is best solved with DFS/BFS in linear time. Atlassian's follow-up frequently makes the input streaming, so know both.

mediumAsked at Atlassian

Number of Islands is Atlassian's canonical grid-graph problem. Given an m x n grid of '1' (land) and '0' (water), return the number of distinct land islands. Atlassian asks it because grid traversal under-pressure is a clean signal for whether you can navigate Jira's board layouts or Confluence's page trees.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-19

Source citations

Public interview reports confirming this problem appears in Atlassian loops.

Glassdoor (2026-Q1)— Atlassian SWE-II onsite reports list Number of Islands as a recurring graph problem in round 2 or 3.
Reddit r/cscareerquestions (2025-11)— Multiple Atlassian onsite threads cite Number of Islands as the BFS/DFS warm-up before Word Ladder or Course Schedule.

Problem

Given an m x n 2D binary grid which represents a map of '1's (land) and '0's (water), return the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are surrounded by water.

Constraints

m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j] is '0' or '1'.

Examples

Example 1

Input

grid = [["1","1","0"],["1","1","0"],["0","0","1"]]

Output

Example 2

Input

grid = [["1","1","0","0"],["1","1","0","0"],["0","0","1","0"],["0","0","0","1"]]

Output

Approaches

1. DFS flood-fill, mark in-place

Scan the grid; on each unvisited '1', increment the counter and DFS to mark the entire island as visited (rewrite to '0' or use a visited set).

Time: O(m * n)
Space: O(m * n) worst case for recursion

function numIslands(grid) {
  if (!grid.length) return 0;
  const m = grid.length;
  const n = grid[0].length;
  let count = 0;
  const dfs = (r, c) => {
    if (r < 0 || r >= m || c < 0 || c >= n || grid[r][c] !== '1') return;
    grid[r][c] = '0';
    dfs(r + 1, c);
    dfs(r - 1, c);
    dfs(r, c + 1);
    dfs(r, c - 1);
  };
  for (let r = 0; r < m; r++) {
    for (let c = 0; c < n; c++) {
      if (grid[r][c] === '1') {
        count++;
        dfs(r, c);
      }
    }
  }
  return count;
}

Tradeoff: Cleanest code; each cell visited once. Mutates the input — flag this out loud so the interviewer can ask the 'don't mutate' follow-up. Recursion can blow the stack on a 300x300 all-land grid; for safety mention switching to iterative BFS.

2. Iterative BFS with a visited set

Same scan, but use a queue instead of recursion and a separate Set for visited cells. Avoids the stack-blow risk on pathological inputs.

Time: O(m * n)
Space: O(min(m, n)) for the queue + O(m * n) for the visited set

function numIslandsBFS(grid) {
  if (!grid.length) return 0;
  const m = grid.length;
  const n = grid[0].length;
  const visited = new Set();
  const key = (r, c) => r * n + c;
  let count = 0;
  for (let r = 0; r < m; r++) {
    for (let c = 0; c < n; c++) {
      if (grid[r][c] !== '1' || visited.has(key(r, c))) continue;
      count++;
      const queue = [[r, c]];
      visited.add(key(r, c));
      while (queue.length) {
        const [cr, cc] = queue.shift();
        for (const [dr, dc] of [[1, 0], [-1, 0], [0, 1], [0, -1]]) {
          const nr = cr + dr;
          const nc = cc + dc;
          if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
          if (grid[nr][nc] !== '1' || visited.has(key(nr, nc))) continue;
          visited.add(key(nr, nc));
          queue.push([nr, nc]);
        }
      }
    }
  }
  return count;
}

Tradeoff: Doesn't mutate the input. Slightly more code. queue.shift() is O(n) in JS so for huge grids use a manual head pointer or import a deque. Mention this; Atlassian interviewers reward awareness of JS-specific quirks.

3. Union-find (when the grid is streamed)

Initialize each land cell as its own set; union with its land neighbors. Count distinct roots at the end. Required if the grid is dynamic (cells turn from water → land over time).

Time: O(m * n * α(m*n))
Space: O(m * n)

class DSU {
  constructor(n) {
    this.parent = new Array(n);
    for (let i = 0; i < n; i++) this.parent[i] = i;
    this.count = 0;
  }
  find(x) {
    while (this.parent[x] !== x) {
      this.parent[x] = this.parent[this.parent[x]];
      x = this.parent[x];
    }
    return x;
  }
  union(a, b) {
    const ra = this.find(a);
    const rb = this.find(b);
    if (ra === rb) return false;
    this.parent[ra] = rb;
    this.count--;
    return true;
  }
}
function numIslandsDSU(grid) {
  const m = grid.length;
  const n = grid[0].length;
  const dsu = new DSU(m * n);
  for (let r = 0; r < m; r++) {
    for (let c = 0; c < n; c++) {
      if (grid[r][c] === '1') dsu.count++;
    }
  }
  for (let r = 0; r < m; r++) {
    for (let c = 0; c < n; c++) {
      if (grid[r][c] !== '1') continue;
      const id = r * n + c;
      if (r + 1 < m && grid[r + 1][c] === '1') dsu.union(id, (r + 1) * n + c);
      if (c + 1 < n && grid[r][c + 1] === '1') dsu.union(id, r * n + c + 1);
    }
  }
  return dsu.count;
}

Tradeoff: Overkill for the static problem; correct answer to the streaming variant (LeetCode 305 — Number of Islands II). Atlassian interviewers love asking the streaming version to candidates who finish DFS quickly, so be ready to pivot here.

Atlassian-specific tips

Atlassian interviewers explicitly grade 'four-direction direction array' as a reusable pattern. Define the dirs = [[1,0],[-1,0],[0,1],[0,-1]] array once and iterate; copy-pasting four DFS calls is a code-smell flag. If asked 'what about diagonals?' just expand to eight directions — the algorithm doesn't change. Be ready to discuss the streaming variant; about 40% of Atlassian onsite reports include it as a follow-up.

Common mistakes

Forgetting the bounds check before the visited check — the recursion goes out of bounds and you get a TypeError on grid[-1].
Using a visited set keyed on `${r},${c}` strings — the GC pressure on a 300x300 grid is real; key on r * n + c instead.
Mutating the input grid without telling the interviewer — this is a tradeoff to surface, not an excuse to skip.

Follow-up questions

An interviewer at Atlassian may pivot to one of these next:

Number of Islands II (LeetCode 305) — cells turn from water to land one-by-one; return the island count after each addition. Forces union-find.
Largest island after flipping one water cell — for each '0', compute the merged size; tag islands by id first, then sum.
What if the grid is too big to fit in memory? Stream rows and keep only the previous row's island IDs; merge as you go.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

DFS or BFS at Atlassian?

Either is accepted on correctness, but BFS scores higher on the 'discuss tradeoffs' rubric because you can explicitly cite the stack-overflow risk of DFS on a 300x300 all-ones grid. If you go DFS, name the risk out loud.

Why is union-find ever the right answer here?

Only when the input is streaming — cells flip on or off over time. The static one-shot problem is best solved with DFS/BFS in linear time. Atlassian's follow-up frequently makes the input streaming, so know both.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

Drill Number of Islands and other Atlassian interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →