Number of Islands solution and explanation
9 more videos on this problem
LeetCode Number of Islands Solution Explained - JavaNick White · 8:39 · 553K views
NUMBER OF ISLANDS - Leetcode 200 - PythonNeetCode · 11:41 · 511K views
Number of Islands - Leetcode 200 - Graphs (Python)Greg Hogg · 11:01 · 45K views
Number of Islands (LeetCode 200) | Full solution with a DFS and a BFS approachNikhil Lohia · 20:04 · 25K views
Leetcode 200: Number of Islands - Coding Question WalkthroughHello Interview · 24:23 · 18K views
Number of Islands - LeetCode 200 - JavaScriptAlgoJS · 10:18 · 9K views
Number Of Islands | LeetCode 200 (Medium)Destination FAANG · 18:12 · 1K views
Leetcode 200. Number of Islands - Python DFSHelmyCodeCamp · 6:17 · 1K views
LeetCode 200. Number of Islands | Island Matrix Part 2 | C#Base Case · 3:17 · 486 views
Leetcode 200 Number of Islands | Islands Problem (Java)HackerHeap · 13:23 · 439 views
The problem
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.lengthn == grid[i].length1 <= m, n <= 300grid[i][j]is'0'or'1'.
Approach overview
Problem Overview: You are given an m x n grid of characters where '1' represents land and '0' represents water. Islands are formed by connecting adjacent land cells horizontally or vertically. The task is to count how many distinct islands exist in the grid.
Approach 1: Depth-First Search (DFS) Traversal (Time: O(m*n), Space: O(m*n))
This problem reduces to counting connected components in a grid. Iterate through every cell of the matrix. When you encounter a land cell '1', you've discovered a new island. Run a DFS from that cell and recursively visit all connected land cells (up, down, left, right), marking them as visited by turning them into '0'. This prevents counting the same island again. Each cell is visited at most once, so the traversal takes linear time relative to the number of cells. DFS is simple to implement and works naturally with recursion when exploring neighbors in a depth-first search pattern.
Approach 2: Breadth-First Search (BFS) Traversal (Time: O(m*n), Space: O(m*n))
BFS solves the same connected-component problem but explores the grid level by level using a queue. When a '1' is found, push it into a queue and repeatedly pop cells while adding all valid neighboring land cells. Mark each visited cell as water to avoid revisiting. BFS avoids recursion depth limits and is often preferred in languages where recursion stacks are shallow. The algorithm still scans every cell once, giving O(m*n) time complexity. This method directly uses breadth-first search on a matrix grid to flood-fill each island.
Approach 3: Union Find (Disjoint Set) (Time: O(m*n * α(n)), Space: O(m*n))
Union Find models each land cell as a node in a disjoint set. Iterate through the grid and union adjacent land cells so they belong to the same set. Initially, every land cell is its own component. When two neighboring land cells are discovered, perform a union operation to merge their sets. After processing the grid, the number of unique parents represents the number of islands. Path compression and union-by-rank keep operations nearly constant time. This method is useful when connectivity queries appear frequently and highlights how Union Find can track components efficiently.
Recommended for interviews: DFS or BFS traversal. Both clearly demonstrate understanding of grid traversal and connected components. DFS is typically the fastest to implement during interviews. BFS is equally valid and avoids recursion depth concerns. Union Find shows deeper algorithm knowledge but usually adds unnecessary complexity for this specific problem.
Approach 1: DFS Approach
This approach uses Depth-First Search (DFS) to explore the grid. We iterate over each cell in the grid, and every time we find an unvisited '1', it indicates the discovery of a new island. We then perform DFS from that cell to mark all the connected '1's as visited, effectively marking the entire island.
class Solution:
def dfs(self, grid, r, c):
if r < 0 or c < 0 or r >= len(grid) or c >= len(grid[0]) or grid[r][c] == '0':
return
grid[r][c] = '0'
self.dfs(grid, r-1, c)
self.dfs(grid, r+1, c)
self.dfs(grid, r, c-1)
self.dfs(grid, r, c+1)
def numIslands(self, grid):
if not grid:
return 0
num_islands = 0
for r in range(len(grid)):
for c in range(len(grid[0])):
if grid[r][c] == '1':
num_islands += 1
self.dfs(grid, r, c)
return num_islandspublic class Solution {
private void dfs(char[][] grid, int r, int c) {
if (r < 0 || c < 0 || r >= grid.length || c >= grid[0].length || grid[r][c] == '0') {
return;
}
grid[r][c] = '0';
dfs(grid, r - 1, c);
dfs(grid, r + 1, c);
dfs(grid, r, c - 1);
dfs(grid, r, c + 1);
}
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) {
return 0;
}
int numIslands = 0;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[i].length; j++) {
if (grid[i][j] == '1') {
numIslands++;
dfs(grid, i, j);
}
}
}
return numIslands;
}
}#include <vector>
using namespace std;
void dfs(vector<vector<char>>& grid, int r, int c) {
if (r < 0 || c < 0 || r >= grid.size() || c >= grid[0].size() || grid[r][c] == '0') {
return;
}
grid[r][c] = '0';
dfs(grid, r-1, c);
dfs(grid, r+1, c);
dfs(grid, r, c-1);
dfs(grid, r, c+1);
}
int numIslands(vector<vector<char>>& grid) {
int numIslands = 0;
for (int i = 0; i < grid.size(); i++) {
for (int j = 0; j < grid[0].size(); j++) {
if (grid[i][j] == '1') {
numIslands++;
dfs(grid, i, j);
}
}
}
return numIslands;
}var numIslands = function(grid) {
function dfs(grid, r, c) {
if (r < 0 || c < 0 || r >= grid.length || c >= grid[0].length || grid[r][c] === '0') {
return;
}
grid[r][c] = '0';
dfs(grid, r-1, c);
dfs(grid, r+1, c);
dfs(grid, r, c-1);
dfs(grid, r, c+1);
}
let numIslands = 0;
for (let r = 0; r < grid.length; r++) {
for (let c = 0; c < grid[0].length; c++) {
if (grid[r][c] === '1') {
numIslands++;
dfs(grid, r, c);
}
}
}
return numIslands;
};#include <stdbool.h>
void dfs(char** grid, int r, int c, int gridSize, int* gridColSize) {
if (r < 0 || c < 0 || r >= gridSize || c >= gridColSize[r] || grid[r][c] == '0') {
return;
}
grid[r][c] = '0';
dfs(grid, r-1, c, gridSize, gridColSize);
dfs(grid, r+1, c, gridSize, gridColSize);
dfs(grid, r, c-1, gridSize, gridColSize);
dfs(grid, r, c+1, gridSize, gridColSize);
}
int numIslands(char** grid, int gridSize, int* gridColSize) {
int numIslands = 0;
for (int i = 0; i < gridSize; i++) {
for (int j = 0; j < gridColSize[i]; j++) {
if (grid[i][j] == '1') {
numIslands++;
dfs(grid, i, j, gridSize, gridColSize);
}
}
}
return numIslands;
}public class Solution {
private void Dfs(char[][] grid, int r, int c) {
if (r < 0 || c < 0 || r >= grid.Length || c >= grid[0].Length || grid[r][c] == '0') {
return;
}
grid[r][c] = '0';
Dfs(grid, r - 1, c);
Dfs(grid, r + 1, c);
Dfs(grid, r, c - 1);
Dfs(grid, r, c + 1);
}
public int NumIslands(char[][] grid) {
if (grid == null || grid.Length == 0) {
return 0;
}
int numIslands = 0;
for (int i = 0; i < grid.Length; i++) {
for (int j = 0; j < grid[i].Length; j++) {
if (grid[i][j] == '1') {
numIslands++;
Dfs(grid, i, j);
}
}
}
return numIslands;
}
}Python's solution uses a method dfs to explore and mark connected lands. We iterate over the entire grid, and for every '1' encountered, initiate a DFS from that position, effectively exploring the whole island.
Time Complexity: O(m*n), where m is the number of rows and n is the number of columns.
Space Complexity: O(m*n) for the recursion call stack in the DFS.
Approach 2: BFS Approach
This approach uses Breadth-First Search (BFS) to traverse the grid. Similar to DFS, we treat each '1' as a node in a graph. On encountering a '1', we initiate a BFS to explore all connected '1's (island nodes) by utilizing a queue for the frontier, marking them in-place as visited.
from collections import deque
class Solution:
def numIslands(self, grid):
if not grid:
return 0
num_islands = 0
rows, cols = len(grid), len(grid[0])
def bfs(r, c):
queue = deque([(r, c)])
grid[r][c] = '0'
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
while queue:
cr, cc = queue.popleft()
for dr, dc in directions:
nr, nc = cr + dr, cc + dc
if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == '1':
grid[nr][nc] = '0'
queue.append((nr, nc))
for r in range(rows):
for c in range(cols):
if grid[r][c] == '1':
num_islands += 1
bfs(r, c)
return num_islandsimport java.util.LinkedList;
import java.util.Queue;
public class Solution {
private static final int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) {
return 0;
}
int numIslands = 0;
for (int r = 0; r < grid.length; r++) {
for (int c = 0; c < grid[0].length; c++) {
if (grid[r][c] == '1') {
numIslands++;
grid[r][c] = '0';
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[]{r, c});
while (!queue.isEmpty()) {
int[] cell = queue.poll();
for (int[] d : directions) {
int nr = cell[0] + d[0], nc = cell[1] + d[1];
if (nr >= 0 && nr < grid.length && nc >= 0 && nc < grid[0].length && grid[nr][nc] == '1') {
queue.add(new int[]{nr, nc});
grid[nr][nc] = '0';
}
}
}
}
}
}
return numIslands;
}
}#include <vector>
#include <queue>
using namespace std;
void bfs(vector<vector<char>>& grid, int r, int c) {
queue<pair<int, int>> q;
q.push({r, c});
grid[r][c] = '0';
vector<vector<int>> directions {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
while (!q.empty()) {
int cr = q.front().first;
int cc = q.front().second;
q.pop();
for (vector<int>& dir : directions) {
int nr = cr + dir[0], nc = cc + dir[1];
if (nr >= 0 && nr < grid.size() && nc >= 0 && nc < grid[0].size() && grid[nr][nc] == '1') {
grid[nr][nc] = '0';
q.push({nr, nc});
}
}
}
}
int numIslands(vector<vector<char>>& grid) {
int numIslands = 0;
for (int i = 0; i < grid.size(); i++) {
for (int j = 0; j < grid[i].size(); j++) {
if (grid[i][j] == '1') {
bfs(grid, i, j);
numIslands++;
}
}
}
return numIslands;
}var numIslands = function(grid) {
if (!grid.length) return 0;
let numIslands = 0;
const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];
const bfs = function(r, c) {
const queue = [];
queue.push([r, c]);
grid[r][c] = '0';
while (queue.length) {
const [cr, cc] = queue.shift();
for (const [dr, dc] of directions) {
const nr = cr + dr;
const nc = cc + dc;
if (nr >= 0 && nr < grid.length && nc >= 0 && nc < grid[0].length && grid[nr][nc] === '1') {
queue.push([nr, nc]);
grid[nr][nc] = '0';
}
}
}
};
for (let r = 0; r < grid.length; r++) {
for (let c = 0; c < grid[0].length; c++) {
if (grid[r][c] === '1') {
numIslands++;
bfs(r, c);
}
}
}
return numIslands;
};#include <stdbool.h>
#include <stdlib.h>
#include <assert.h>
typedef struct {
int r, c;
} QueueNode;
void bfs(char** grid, int gridSize, int* gridColSize, int sr, int sc) {
QueueNode* queue = malloc(gridSize * gridSize * sizeof(QueueNode)); // Worst case memory
int front = 0, rear = 0;
queue[rear++] = (QueueNode){sr, sc};
while (front < rear) {
QueueNode node = queue[front++];
int dr[4] = {-1, 1, 0 , 0};
int dc[4] = {0, 0, -1, 1};
for (int i = 0; i < 4; i++) {
int r = node.r + dr[i], c = node.c + dc[i];
if (r < 0 || c < 0 || r >= gridSize || c >= gridColSize[r] || grid[r][c] == '0') {
continue;
}
grid[r][c] = '0';
queue[rear++] = (QueueNode){r, c};
}
}
free(queue);
}
int numIslands(char** grid, int gridSize, int* gridColSize) {
int numIslands = 0;
for (int i = 0; i < gridSize; i++) {
for (int j = 0; j < gridColSize[i]; j++) {
if (grid[i][j] == '1') {
numIslands++;
bfs(grid, gridSize, gridColSize, i, j);
}
}
}
return numIslands;
}using System.Collections.Generic;
public class Solution {
private static readonly int[][] directions = new int[][] {
new int[] {-1, 0}, new int[] {1, 0},
new int[] {0, -1}, new int[] {0, 1},
};
public int NumIslands(char[][] grid) {
if (grid == null || grid.Length == 0) {
return 0;
}
int numIslands = 0;
for (int r = 0; r < grid.Length; r++) {
for (int c = 0; c < grid[0].Length; c++) {
if (grid[r][c] == '1') {
numIslands++;
grid[r][c] = '0';
Queue<int[]> queue = new Queue<int[]>();
queue.Enqueue(new int[] {r, c});
while (queue.Count > 0) {
int[] cell = queue.Dequeue();
foreach (int[] d in directions) {
int nr = cell[0] + d[0], nc = cell[1] + d[1];
if (nr >= 0 && nr < grid.Length && nc >= 0 && nc < grid[0].Length && grid[nr][nc] == '1') {
queue.Enqueue(new int[] {nr, nc});
grid[nr][nc] = '0';
}
}
}
}
}
}
return numIslands;
}
}The Python implementation employs the collections.deque to perform BFS. Upon encountering a '1', the coordinates are queued and BFS enqueues its adjacent lands, effectively exploring the entire island and marking progress.
Time Complexity: O(m*n), with m rows, n columns.
Space Complexity: O(min(m, n)) for the BFS queue size.
Approach 3: DFS
We can use depth-first search (DFS) to traverse each island. We iterate through each cell (i, j) in the grid. If the cell's value is '1', it means we have found a new island. We can start a DFS from this cell, marking all connected land cells as '0' to avoid duplicate counting. Each time we find a new island, we increment the island count by 1.
The time complexity is O(m times n), and the space complexity is O(m times n). Where m and n are the number of rows and columns in the grid, respectively.
function numIslands(grid: string[][]): number {
const m = grid.length;
const n = grid[0].length;
let ans = 0;
const dirs = [-1, 0, 1, 0, -1];
const dfs = (i: number, j: number) => {
grid[i][j] = '0';
for (let k = 0; k < 4; ++k) {
const x = i + dirs[k];
const y = j + dirs[k + 1];
if (grid[x]?.[y] === '1') {
dfs(x, y);
}
}
};
for (let i = 0; i < m; ++i) {
for (let j = 0; j < n; ++j) {
if (grid[i][j] === '1') {
dfs(i, j);
ans++;
}
}
}
return ans;
}func numIslands(grid [][]byte) int {
m, n := len(grid), len(grid[0])
var dfs func(i, j int)
dfs = func(i, j int) {
grid[i][j] = '0'
dirs := []int{-1, 0, 1, 0, -1}
for k := 0; k < 4; k++ {
x, y := i+dirs[k], j+dirs[k+1]
if x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '1' {
dfs(x, y)
}
}
}
ans := 0
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if grid[i][j] == '1' {
dfs(i, j)
ans++
}
}
}
return ans
}const DIRS: [i32; 5] = [-1, 0, 1, 0, -1];
impl Solution {
pub fn num_islands(grid: Vec<Vec<char>>) -> i32 {
fn dfs(grid: &mut Vec<Vec<char>>, i: usize, j: usize) {
grid[i][j] = '0';
for k in 0..4 {
let x = (i as i32) + DIRS[k];
let y = (j as i32) + DIRS[k + 1];
if x >= 0
&& (x as usize) < grid.len()
&& y >= 0
&& (y as usize) < grid[0].len()
&& grid[x as usize][y as usize] == '1'
{
dfs(grid, x as usize, y as usize);
}
}
}
let mut grid = grid;
let mut ans = 0;
for i in 0..grid.len() {
for j in 0..grid[0].len() {
if grid[i][j] == '1' {
dfs(&mut grid, i, j);
ans += 1;
}
}
}
ans
}
}Approach 4: BFS
We can also use breadth-first search (BFS) to traverse each island. We iterate through each cell (i, j) in the grid. If the cell's value is '1', it means we have found a new island. We can start a BFS from this cell, marking all connected land cells as '0' to avoid duplicate counting. Each time we find a new island, we increment the island count by 1.
The specific BFS process is as follows:
- Enqueue the starting cell
(i, j)and mark its value as '0'. - While the queue is not empty, perform the following operations:
- Dequeue a cell
p. - Iterate through the four adjacent cells
(x, y)ofp. If(x, y)is within the grid bounds and its value is '1', enqueue it and mark its value as '0'.
- Dequeue a cell
The time complexity is O(m times n), and the space complexity is O(m times n). Where m and n are the number of rows and columns in the grid, respectively.
function numIslands(grid: string[][]): number {
const m = grid.length;
const n = grid[0].length;
let ans = 0;
const bfs = (i: number, j: number) => {
grid[i][j] = '0';
const q = [[i, j]];
const dirs = [-1, 0, 1, 0, -1];
for (const [i, j] of q) {
for (let k = 0; k < 4; ++k) {
const x = i + dirs[k];
const y = j + dirs[k + 1];
if (grid[x]?.[y] == '1') {
q.push([x, y]);
grid[x][y] = '0';
}
}
}
};
for (let i = 0; i < m; ++i) {
for (let j = 0; j < n; ++j) {
if (grid[i][j] == '1') {
bfs(i, j);
++ans;
}
}
}
return ans;
}func numIslands(grid [][]byte) int {
m, n := len(grid), len(grid[0])
bfs := func(i, j int) {
grid[i][j] = '0'
q := [][]int{[]int{i, j}}
dirs := []int{-1, 0, 1, 0, -1}
for len(q) > 0 {
p := q[0]
q = q[1:]
for k := 0; k < 4; k++ {
x, y := p[0]+dirs[k], p[1]+dirs[k+1]
if x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '1' {
q = append(q, []int{x, y})
grid[x][y] = '0'
}
}
}
}
ans := 0
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if grid[i][j] == '1' {
bfs(i, j)
ans++
}
}
}
return ans
}use std::collections::VecDeque;
const DIRS: [i32; 5] = [-1, 0, 1, 0, -1];
impl Solution {
pub fn num_islands(grid: Vec<Vec<char>>) -> i32 {
fn bfs(grid: &mut Vec<Vec<char>>, i: usize, j: usize) {
grid[i][j] = '0';
let mut queue = VecDeque::from([(i, j)]);
while !queue.is_empty() {
let (i, j) = queue.pop_front().unwrap();
for k in 0..4 {
let x = (i as i32) + DIRS[k];
let y = (j as i32) + DIRS[k + 1];
if x >= 0
&& (x as usize) < grid.len()
&& y >= 0
&& (y as usize) < grid[0].len()
&& grid[x as usize][y as usize] == '1'
{
grid[x as usize][y as usize] = '0';
queue.push_back((x as usize, y as usize));
}
}
}
}
let mut grid = grid;
let mut ans = 0;
for i in 0..grid.len() {
for j in 0..grid[0].len() {
if grid[i][j] == '1' {
bfs(&mut grid, i, j);
ans += 1;
}
}
}
ans
}
}Approach 5: Union-Find
We can use the Union-Find data structure to solve this problem. We traverse each cell (i, j) in the grid, and if the cell's value is '1', we merge it with adjacent land cells. Finally, we count the number of distinct root nodes in the Union-Find structure, which represents the number of islands.
The time complexity is O(m times n times log (m times n)), and the space complexity is O(m times n). Where m and n are the number of rows and columns in the grid, respectively.
function numIslands(grid: string[][]): number {
const m = grid.length;
const n = grid[0].length;
const p: number[] = Array.from({ length: m * n }, (_, i) => i);
function find(x: number): number {
if (p[x] != x) {
p[x] = find(p[x]);
}
return p[x];
}
const dirs = [1, 0, 1];
for (let i = 0; i < m; ++i) {
for (let j = 0; j < n; ++j) {
if (grid[i][j] == '1') {
for (let k = 0; k < 2; ++k) {
const x = i + dirs[k];
const y = j + dirs[k + 1];
if (grid[x]?.[y] == '1') {
p[find(i * n + j)] = find(x * n + y);
}
}
}
}
}
let ans = 0;
for (let i = 0; i < m; ++i) {
for (let j = 0; j < n; ++j) {
if (grid[i][j] == '1' && i * n + j == find(i * n + j)) {
++ans;
}
}
}
return ans;
}func numIslands(grid [][]byte) int {
m, n := len(grid), len(grid[0])
p := make([]int, m*n)
for i := range p {
p[i] = i
}
var find func(x int) int
find = func(x int) int {
if p[x] != x {
p[x] = find(p[x])
}
return p[x]
}
dirs := []int{1, 0, 1}
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if grid[i][j] == '1' {
for k := 0; k < 2; k++ {
x, y := i+dirs[k], j+dirs[k+1]
if x < m && y < n && grid[x][y] == '1' {
p[find(x*n+y)] = find(i*n + j)
}
}
}
}
}
ans := 0
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if grid[i][j] == '1' && i*n+j == find(i*n+j) {
ans++
}
}
}
return ans
}const DIRS: [usize; 3] = [1, 0, 1];
impl Solution {
pub fn num_islands(grid: Vec<Vec<char>>) -> i32 {
let m = grid.len();
let n = grid[0].len();
let mut p: Vec<i32> = (0..(m * n) as i32).collect();
fn find(p: &mut Vec<i32>, x: usize) -> i32 {
if p[x] != (x as i32) {
p[x] = find(p, p[x] as usize);
}
p[x]
}
for i in 0..m {
for j in 0..n {
if grid[i][j] == '1' {
for k in 0..2 {
let x = i + DIRS[k];
let y = j + DIRS[k + 1];
if x < m && y < n && grid[x][y] == '1' {
let f1 = find(&mut p, x * n + y);
let f2 = find(&mut p, i * n + j);
p[f1 as usize] = f2;
}
}
}
}
}
let mut ans = 0;
for i in 0..m {
for j in 0..n {
if grid[i][j] == '1' && p[i * n + j] == ((i * n + j) as i32) {
ans += 1;
}
}
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| DFS Approach | Time Complexity: O(m*n), where m is the number of rows and n is the number of columns. |
| BFS Approach | Time Complexity: O(m*n), with m rows, n columns. |
| DFS | – |
| BFS | – |
| Union-Find | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Depth-First Search (DFS) | O(m*n) | O(m*n) | Most common interview solution. Simple recursive traversal of connected land cells. |
| Breadth-First Search (BFS) | O(m*n) | O(m*n) | Preferred when avoiding recursion depth limits or when using iterative queue traversal. |
| Union Find (Disjoint Set) | O(m*n * α(n)) | O(m*n) | Useful when multiple connectivity queries are required or when demonstrating disjoint-set techniques. |
Frequently asked questions
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.