Number of Islands
MedPrompt
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: 1Example 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'.
Approaches
4 approaches with complexity analysis and trade-offs.
The simplest approach is to use nested loops to iterate through each cell in the grid. When we find a land cell ('1'), we increment our island count and use a separate function to mark all connected land cells as visited to avoid counting them again.
Algorithm
- Initialize a counter for the number of islands to 0
- Iterate through each cell in the grid using nested loops
- When a land cell ('1') is found:
- Increment the island counter
- Use DFS to mark all connected land cells as visited by changing them to '0'
- Return the island counter
Walkthrough
In this approach, we iterate through each cell in the grid using nested loops. When we encounter a land cell ('1') that hasn't been visited yet, we increment our island count and perform a flood fill operation to mark all connected land cells as visited.
The flood fill can be implemented using either Depth-First Search (DFS) or Breadth-First Search (BFS). For simplicity, we'll use DFS in this implementation.
Here's the implementation:
public int numIslands(char[][] grid) { if (grid == null || grid.length == 0) { return 0; } int rows = grid.length; int cols = grid[0].length; int count = 0; for (int i = 0; i < rows; i++) { for (int j = 0; j < cols; j++) { if (grid[i][j] == '1') { count++; dfs(grid, i, j); } } } return count;} private void dfs(char[][] grid, int row, int col) { int rows = grid.length; int cols = grid[0].length; // Check if out of bounds or not land if (row < 0 || col < 0 || row >= rows || col >= cols || grid[row][col] != '1') { return; } // Mark as visited by changing '1' to '0' grid[row][col] = '0'; // Check all four directions dfs(grid, row + 1, col); dfs(grid, row - 1, col); dfs(grid, row, col + 1); dfs(grid, row, col - 1);}This approach modifies the input grid to mark visited cells. If we're not allowed to modify the input, we would need to use an additional visited matrix.
Complexity
Time
O(m × n) where m is the number of rows and n is the number of columns. Each cell is visited at most once.
Space
O(m × n) in the worst case for the recursion stack (when the grid is filled with land cells)
Trade-offs
Pros
Simple and intuitive approach
Easy to implement
No additional space required (if we're allowed to modify the input grid)
Cons
Modifies the input grid
Recursive DFS might cause stack overflow for very large grids
Not the most efficient for sparse grids with few land cells
Instead of using DFS, we can use Breadth-First Search (BFS) with a queue to find all connected land cells. This approach is particularly useful for large grids as it avoids the potential stack overflow issues of recursive DFS.
Algorithm
- Initialize a counter for the number of islands to 0
- Iterate through each cell in the grid using nested loops
- When a land cell ('1') is found:
- Increment the island counter
- Use BFS with a queue to mark all connected land cells as visited
- For BFS:
- Add the current cell to the queue and mark it as visited
- While the queue is not empty, dequeue a cell and check its four adjacent cells
- If an adjacent cell is land, add it to the queue and mark it as visited
- Return the island counter
Walkthrough
In this approach, we still iterate through each cell in the grid, but when we find a land cell, we use BFS instead of DFS to mark all connected land cells as visited.
We use a queue to keep track of cells to visit. When we find a land cell, we add it to the queue, mark it as visited, and then explore all its adjacent land cells by adding them to the queue.
public int numIslands(char[][] grid) { if (grid == null || grid.length == 0) { return 0; } int rows = grid.length; int cols = grid[0].length; int count = 0; for (int i = 0; i < rows; i++) { for (int j = 0; j < cols; j++) { if (grid[i][j] == '1') { count++; bfs(grid, i, j); } } } return count;} private void bfs(char[][] grid, int row, int col) { int rows = grid.length; int cols = grid[0].length; Queue<int[]> queue = new LinkedList<>(); queue.add(new int[]{row, col}); grid[row][col] = '0'; // Mark as visited int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; // Down, Up, Right, Left while (!queue.isEmpty()) { int[] current = queue.poll(); int r = current[0]; int c = current[1]; for (int[] dir : directions) { int newRow = r + dir[0]; int newCol = c + dir[1]; if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols && grid[newRow][newCol] == '1') { queue.add(new int[]{newRow, newCol}); grid[newRow][newCol] = '0'; // Mark as visited } } }}This BFS approach is less likely to cause stack overflow for large grids compared to the recursive DFS approach.
Complexity
Time
O(m × n) where m is the number of rows and n is the number of columns. Each cell is visited at most once.
Space
O(min(m, n)) for the queue in the worst case (when the grid has a snake-like island)
Trade-offs
Pros
Avoids stack overflow issues for large grids
Visits cells in a level-by-level manner
Good for finding the shortest path (though not needed for this problem)
Cons
Modifies the input grid
Slightly more complex implementation than DFS
Queue operations might have a small overhead
We can use the Union-Find data structure to solve this problem. This approach is particularly efficient for dynamic problems where we need to repeatedly check if two elements are in the same set or merge sets.
Algorithm
- Create a Union-Find data structure
- Initialize each land cell as a separate set and count the total number of land cells
- Iterate through the grid and for each land cell:
- Check its right and down neighbors
- If a neighbor is also land, union the current cell with the neighbor
- Decrease the count when two sets are merged
- Return the final count of distinct sets
Walkthrough
The Union-Find (Disjoint Set) approach works by grouping connected land cells into sets. Each set represents an island.
Here's how we implement it:
- Initialize a Union-Find data structure with each land cell as a separate set
- Iterate through the grid and for each land cell, union it with its adjacent land cells
- Count the number of distinct sets (islands)
public int numIslands(char[][] grid) { if (grid == null || grid.length == 0) { return 0; } int rows = grid.length; int cols = grid[0].length; // Create Union-Find data structure UnionFind uf = new UnionFind(grid); // Process all land cells for (int i = 0; i < rows; i++) { for (int j = 0; j < cols; j++) { if (grid[i][j] == '1') { // Check right and down neighbors only to avoid duplicate unions int[][] directions = {{1, 0}, {0, 1}}; for (int[] dir : directions) { int newRow = i + dir[0]; int newCol = j + dir[1]; if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols && grid[newRow][newCol] == '1') { uf.union(i * cols + j, newRow * cols + newCol); } } } } } return uf.getCount();} class UnionFind { private int count; // Number of distinct sets private int[] parent; private int[] rank; public UnionFind(char[][] grid) { int rows = grid.length; int cols = grid[0].length; parent = new int[rows * cols]; rank = new int[rows * cols]; // Initialize with each land cell as a separate set count = 0; for (int i = 0; i < rows; i++) { for (int j = 0; j < cols; j++) { if (grid[i][j] == '1') { parent[i * cols + j] = i * cols + j; // Self-parent count++; } } } } public int find(int x) { if (parent[x] != x) { parent[x] = find(parent[x]); // Path compression } return parent[x]; } public void union(int x, int y) { int rootX = find(x); int rootY = find(y); if (rootX != rootY) { // Union by rank if (rank[rootX] < rank[rootY]) { parent[rootX] = rootY; } else if (rank[rootX] > rank[rootY]) { parent[rootY] = rootX; } else { parent[rootY] = rootX; rank[rootX]++; } count--; // Decrease count when two sets are merged } } public int getCount() { return count; }}This approach doesn't modify the input grid and is particularly efficient for problems where we need to repeatedly check if two cells are connected or merge connected components.
Complexity
Time
O(m × n × α(m×n)) where α is the inverse Ackermann function, which is nearly constant for all practical purposes. So effectively O(m × n).
Space
O(m × n) for the Union-Find data structure
Trade-offs
Pros
Doesn't modify the input grid
Efficient for dynamic connectivity problems
Can be extended to handle online queries efficiently
With path compression and union by rank, operations are nearly constant time
Cons
More complex implementation compared to DFS/BFS
Requires additional space for the Union-Find data structure
Not as intuitive as the graph traversal approaches
The most efficient approach for this specific problem is to use DFS with in-place modification of the grid. This approach has the same time complexity as the other approaches but uses constant extra space (excluding the recursion stack).
Algorithm
- Initialize a counter for the number of islands to 0
- Iterate through each cell in the grid using nested loops
- When a land cell ('1') is found:
- Increment the island counter
- Use DFS to mark all connected land cells as visited by changing them to '2'
- Optionally, restore the grid to its original state if needed
- Return the island counter
Walkthrough
This approach is similar to the first DFS approach, but we optimize it by using the input grid itself to mark visited cells, thus avoiding the need for an additional visited matrix.
We iterate through each cell in the grid, and when we find a land cell ('1'), we increment our island count and use DFS to mark all connected land cells as visited by changing them to a different character (e.g., '0' or '2').
public int numIslands(char[][] grid) { if (grid == null || grid.length == 0) { return 0; } int rows = grid.length; int cols = grid[0].length; int count = 0; for (int i = 0; i < rows; i++) { for (int j = 0; j < cols; j++) { if (grid[i][j] == '1') { count++; dfs(grid, i, j); } } } // Optional: restore the grid if needed // for (int i = 0; i < rows; i++) { // for (int j = 0; j < cols; j++) { // if (grid[i][j] == '2') { // grid[i][j] = '1'; // } // } // } return count;} private void dfs(char[][] grid, int row, int col) { int rows = grid.length; int cols = grid[0].length; // Check if out of bounds or not land if (row < 0 || col < 0 || row >= rows || col >= cols || grid[row][col] != '1') { return; } // Mark as visited by changing '1' to '2' grid[row][col] = '2'; // Check all four directions dfs(grid, row + 1, col); dfs(grid, row - 1, col); dfs(grid, row, col + 1); dfs(grid, row, col - 1);}To avoid modifying the input permanently, we can mark visited cells with a different character (e.g., '2') and then restore them after counting if needed.
Alternatively, we can use an iterative DFS with a stack to avoid the recursion stack overhead:
public int numIslands(char[][] grid) { if (grid == null || grid.length == 0) { return 0; } int rows = grid.length; int cols = grid[0].length; int count = 0; for (int i = 0; i < rows; i++) { for (int j = 0; j < cols; j++) { if (grid[i][j] == '1') { count++; // Use stack for iterative DFS Stack<int[]> stack = new Stack<>(); stack.push(new int[]{i, j}); grid[i][j] = '2'; // Mark as visited while (!stack.isEmpty()) { int[] current = stack.pop(); int r = current[0]; int c = current[1]; // Check all four directions int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; for (int[] dir : directions) { int newRow = r + dir[0]; int newCol = c + dir[1]; if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols && grid[newRow][newCol] == '1') { stack.push(new int[]{newRow, newCol}); grid[newRow][newCol] = '2'; // Mark as visited } } } } } } // Optional: restore the grid if needed // for (int i = 0; i < rows; i++) { // for (int j = 0; j < cols; j++) { // if (grid[i][j] == '2') { // grid[i][j] = '1'; // } // } // } return count;}This iterative approach avoids the potential stack overflow issues of recursive DFS while maintaining the same time and space complexity.
Complexity
Time
O(m × n) where m is the number of rows and n is the number of columns. Each cell is visited at most once.
Space
O(m × n) in the worst case for the recursion stack (when the grid is filled with land cells), but O(1) extra space otherwise
Trade-offs
Pros
Optimal space complexity (constant extra space excluding recursion stack)
Simple and efficient implementation
Can be implemented iteratively to avoid recursion stack overhead
Faster than Union-Find for this specific problem
Cons
Modifies the input grid (though it can be restored)
Recursive implementation might cause stack overflow for very large grids
Not as versatile as Union-Find for dynamic connectivity problems
Solutions
Solution
using System ; using System.Collections.Generic ; using System.Linq ; public class Solution { public int NumIslands ( char [][] grid ) { var queue = new Queue < Tuple < int , int >>(); var lenI = grid . Length ; var lenJ = lenI == 0 ? 0 : grid [ 0 ]. Length ; var paths = new int [,] { { 0 , 1 }, { 1 , 0 }, { 0 , - 1 }, { - 1 , 0 } }; var result = 0 ; for ( var i = 0 ; i < lenI ; ++ i ) { for ( var j = 0 ; j < lenJ ; ++ j ) { if ( grid [ i ][ j ] == '1' ) { ++ result ; grid [ i ][ j ] = '0' ; queue . Enqueue ( Tuple . Create ( i , j )); while ( queue . Any ()) { var position = queue . Dequeue (); for ( var k = 0 ; k < 4 ; ++ k ) { var next = Tuple . Create ( position . Item1 + paths [ k , 0 ], position . Item2 + paths [ k , 1 ]); if ( next . Item1 >= 0 && next . Item1 < lenI && next . Item2 >= 0 && next . Item2 < lenJ && grid [ next . Item1 ][ next . Item2 ] == '1' ) { grid [ next . Item1 ][ next . Item2 ] = '0' ; queue . Enqueue ( next ); } } } } } } return result ; } }class Solution {private char[][] grid;private int m;private int n;public int numIslands(char[][] grid) { m = grid.length; n = grid[0].length; this.grid = grid; int ans = 0; for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { if (grid[i][j] == '1') { dfs(i, j); ++ans; } } } return ans; }private void dfs(int i, int j) { grid[i][j] = '0'; int[] dirs = {-1, 0, 1, 0, -1}; for (int k = 0; k < 4; ++k) { int x = i + dirs[k]; int y = j + dirs[k + 1]; if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '1') { dfs(x, y); } } }}class Solution {public: int numIslands(vector<vector<char>> &grid) { int m = grid.size(); int n = grid[0].size(); int ans = 0; int dirs[5] = {-1, 0, 1, 0, -1}; function<void(int, int)> dfs = [&](int i, int j) { grid[i][j] = '0'; for (int k = 0; k < 4; ++k) { int x = i + dirs[k], y = j + dirs[k + 1]; if (x >= 0 && x < grid.size() && y >= 0 && y < grid[0].size() && grid[x][y] == '1') { dfs(x, y); } } }; for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { if (grid[i][j] == '1') { dfs(i, j); ++ans; } } } return ans; }};# dfs class Solution : def numIslands ( self , grid : List [ List [ str ]]) -> int : def dfs ( i , j ): if not ( 0 <= i < m and 0 <= j < n and grid [ i ][ j ] == '1' ): return grid [ i ][ j ] = '0' for a , b in pairwise ( dirs ): x , y = i + a , j + b dfs ( x , y ) ans = 0 dirs = ( - 1 , 0 , 1 , 0 , - 1 ) m , n = len ( grid ), len ( grid [ 0 ]) for i in range ( m ): for j in range ( n ): if grid [ i ][ j ] == '1' : dfs ( i , j ) ans += 1 return ans ############### # bfs from collections import deque class Solution : def numIslands ( self , grid : List [ List [ str ]]) -> int : if not grid : return 0 m , n = len ( grid ), len ( grid [ 0 ]) directions = [( 0 , 1 ), ( 0 , - 1 ), ( 1 , 0 ), ( - 1 , 0 )] islands = 0 for i in range ( m ): for j in range ( n ): if grid [ i ][ j ] == "1" : islands += 1 q = deque ([( i , j )]) # no need to reset q, q already drained from previous bfs while q : x , y = q . popleft () for dx , dy in directions : nx , ny = x + dx , y + dy if 0 <= nx < m and 0 <= ny < n and grid [ nx ][ ny ] == "1" : q . append (( nx , ny )) grid [ nx ][ ny ] = "0" # mark as visited return islands ############### # union find # similar to UF in https://leetcode.ca/2016-09-30-305-Number-of-Islands-II/ class Solution : def numIslands ( self , grid : List [ List [ str ]]) -> int : def check ( i , j ): return 0 <= i < m and 0 <= j < n and grid [ i ][ j ] == "1" # Check for "1" instead of 1 def find ( x ): if p [ x ] != x : p [ x ] = find ( p [ x ]) return p [ x ] m , n = len ( grid ), len ( grid [ 0 ]) p = list ( range ( m * n )) cur = 0 # Initialize cur as 0 instead of n for i in range ( m ): for j in range ( n ): if grid [ i ][ j ] == "1" : cur += 1 # Increment cur when encountering "1" for x , y in [( - 1 , 0 ), ( 1 , 0 ), ( 0 , - 1 ), ( 0 , 1 )]: if check ( i + x , j + y ) and find ( i * n + j ) != find (( i + x ) * n + j + y ): p [ find ( i * n + j )] = find (( i + x ) * n + j + y ) cur -= 1 return cur ############ ''' >>> a = set() >>> >>> a |= {(1, 1)} >>> a {(1, 1)} >>> >>> a |= {(2, 2)} >>> a {(1, 1), (2, 2)} >>> >>> a.add((3, 3)) >>> a {(1, 1), (3, 3), (2, 2)} >>> >>> (1,1) in a True >>> (10,10) in a False ''' class Solution ( object ): def numIslands ( self , grid ): """ :type grid: List[List[str]] :rtype: int """ visited = set () ans = 0 def dfs ( grid , i , j , visited ): if i < 0 or i >= len ( grid ) or j < 0 or j >= len ( grid [ 0 ]) or grid [ i ][ j ] == "0" or ( i , j ) in visited : return False visited |= {( i , j )} for di , dj in [( - 1 , 0 ), ( 1 , 0 ), ( 0 , 1 ), ( 0 , - 1 )]: newi , newj = i + di , j + dj dfs ( grid , newi , newj , visited ) return True for i in range ( 0 , len ( grid )): for j in range ( 0 , len ( grid [ 0 ])): if dfs ( grid , i , j , visited ): ans += 1 return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.