DSA-VerseLearn by watching code run
DashboardData StructuresAlgorithmsVisualizerCORECoding PlaygroundInterview QuestionsComplexity AnalyzerLearning NotesBookmarksLearning ProgressSettings
All interview questions

Interview preparation

Number of Islands

MediumGraphsArraysStacks and Queues
AmazonGoogleMetaMicrosoftUber Community-reported practice tags — not verified company questions.

1Problem statement

Given an m × n grid of '1' (land) and '0' (water), return the number of islands. An island is a group of land cells connected horizontally or vertically, surrounded by water.

2Examples

Input: grid = ["11110", "11010", "11000", "00000"]
Output: 1
Input: grid = ["11000", "11000", "00100", "00011"]
Output: 3

3Constraints

  • 1 ≤ m, n ≤ 300
  • grid[i][j] is '0' or '1'.

4Approaches

Approach 1

Brute Force

For every land cell, run a full search to collect its island and compare sets to avoid double counting.

Time O((m·n)²)Space O(m·n)

Approach 2

Better: Union-Find

Union adjacent land cells; count distinct roots.

Time ≈ O(m·n·α)Space O(m·n)

Approach 3

Optimal: BFS / DFS flood fill

Scan the grid; each unvisited land cell starts a new island and a BFS that sinks (marks) every connected land cell.

Time O(m·n)Space O(min(m, n)) queue for BFS

5Code (optimal approach)

Complete programs that print the example outputs — verified in JavaScript, Python, Java and Go.

function numIslands(rows) {
  const grid = rows.map((r) => r.split(""));
  const R = grid.length;
  const C = grid[0].length;
  const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
  let islands = 0;
  for (let r = 0; r < R; r++) {
    for (let c = 0; c < C; c++) {
      if (grid[r][c] !== "1") continue;
      islands++;
      grid[r][c] = "0";
      const queue = [[r, c]];
      for (let head = 0; head < queue.length; head++) {
        const [cr, cc] = queue[head];
        for (const [dr, dc] of dirs) {
          const nr = cr + dr;
          const nc = cc + dc;
          if (nr >= 0 && nr < R && nc >= 0 && nc < C && grid[nr][nc] === "1") {
            grid[nr][nc] = "0";
            queue.push([nr, nc]);
          }
        }
      }
    }
  }
  return islands;
}

console.log(numIslands(["11110", "11010", "11000", "00000"]));
console.log(numIslands(["11000", "11000", "00100", "00011"]));

6Complexity

Time

O(m·n)

Space

O(m·n) worst case

7Visual walkthrough

  1. 1.Treat each land cell as a vertex and each up/down/left/right land neighbour as an edge.
  2. 2.Each BFS from a new land cell explores exactly one connected component.
  3. 3.The number of BFS starts is the number of islands.

Related visualization (Graph BFS (Breadth-First Search)) — shows the core data-structure operations this solution relies on:

Graph BFS (Breadth-First Search)interactive Open full visualizer
ABCDEFG

Queue (front → rear)

empty

Traversal order

—
Current vertexIn queueDiscoveredProcessedUnvisited

Explores the graph level by level using a queue. Because vertices are discovered in order of distance, BFS also finds the shortest path (fewest edges) from the start in an unweighted graph.

1 / 78

8Related questions

Implement Queue using Stacks

On this page

  1. 01Problem statement
  2. 02Examples
  3. 03Constraints
  4. 04Approaches
  5. 05Code (4 languages)
  6. 06Complexity
  7. 07Visual walkthrough
  8. 08Related questions