Is Number of Islands easy or hard?

Number of Islands is generally classified as a medium difficulty problem. The logic is straightforward once you recognize it as a connected-components problem in a grid, but beginners may struggle with grid traversal and marking visited cells correctly.

How to solve Number of Islands in O(n)?

Treat the grid as a graph and run DFS or BFS whenever an unvisited land cell appears. The traversal marks all connected land cells as visited so they aren't counted again. Because each cell is processed once, the algorithm runs in O(m*n) time, which is linear relative to the grid size.

What is the best approach for Number of Islands?

Depth-First Search (DFS) or Breadth-First Search (BFS) is the most common approach. Both treat the grid as a graph and count connected components of land cells. Each time a '1' is found, a traversal marks all connected cells as visited. The overall time complexity is O(m*n) because each cell is processed once.

What data structure is used in Number of Islands?

The problem primarily uses graph traversal data structures. DFS uses the recursion stack, while BFS uses a queue to explore neighbors. Some implementations also use the Union Find (Disjoint Set) structure to group connected land cells into components.

What is the time complexity of Number of Islands?

The optimal time complexity is O(m*n), where m and n are the grid dimensions. Every cell is visited at most once during DFS or BFS traversal. Space complexity is O(m*n) in the worst case due to recursion stack or queue storage.

Number of Islands Python or Java solution approach?

Python and Java implementations typically use DFS or BFS. The grid is scanned cell by cell, and whenever a '1' appears, a traversal marks all adjacent land cells as visited. Both languages achieve O(m*n) time complexity with either recursion (DFS) or a queue-based BFS.

Is Number of Islands asked at Google, Amazon, or Meta?

Number of Islands frequently appears in interviews at companies like Amazon, Google, Meta, and Microsoft. It tests understanding of graph traversal, grid exploration, and connected components. Variants such as Number of Islands II or dynamic island counting are also common follow-ups.

Description Solution Video 8:39

200. Number of Islands

Medium65.2% acceptance86 companies

Given an m x n 2D binary grid 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 all surrounded by water.

Example 1:

Input: grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
Output: 1

Example 2:

Input: grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
Output: 3

Constraints:

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

Asked at top 20 of 86 companies

Tiktok LinkedIn Walmart Labs Snapchat Bytedance Samsung Qualcomm Anduril Wix Autodesk Waymo Siemens

+8 more

Zenefits Tinkoff AMD Huawei Moloco CrowdStrike Rivian Hive

Topics

8:39

Still stuck?Read 5 approaches, or watch a walkthrough.

Open solution

200. Number of Islands

Asked at top 20 of 86 companies

Topics

Similar problems