Skip to main content

9. Number of Islands

mediumAsked at JetBrains

Count connected land components in a 2D grid — JetBrains uses this to gauge graph-traversal fluency before any code-graph clustering follow-up.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given an m x n 2D binary grid where '1' is land and '0' is water, return the number of islands. An island is land connected horizontally or vertically and surrounded by water.

Constraints

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

Examples

Example 1

Input
grid=[['1','1','0'],['1','0','0'],['0','0','1']]
Output
2

Example 2

Input
grid=[['1','1','1'],['1','1','1']]
Output
1

Approaches

1. Repeated full sweep

After painting each island, restart the outer scan from (0,0); does redundant rework.

Time
O(m*n * islands)
Space
O(m*n)
// for every '1' found, flood and restart entire grid scan — wasteful

Tradeoff:

2. DFS flood-fill in place

Linear sweep, DFS sinks each new island, marking visited. Same shape as JetBrains's code-graph component analysis over reference subgraphs.

Time
O(m*n)
Space
O(m*n)
function numIslands(grid) {
  let count = 0;
  const sink = (i, j) => {
    if (i<0||j<0||i>=grid.length||j>=grid[0].length||grid[i][j]!=='1') return;
    grid[i][j] = '0';
    sink(i+1,j); sink(i-1,j); sink(i,j+1); sink(i,j-1);
  };
  for (let i=0;i<grid.length;i++)
    for (let j=0;j<grid[0].length;j++)
      if (grid[i][j]==='1') { count++; sink(i,j); }
  return count;
}

Tradeoff:

JetBrains-specific tips

JetBrains expects you to draw the link to connected-component labeling of reference graphs — the same primitive their inspections use for unused-symbol analysis.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →