# Number of Islands **Difficulty:** MEDIUM [External](https://leetcode.com/problems/number-of-islands) Canonical: https://scaleengineer.com/dsa/problems/number-of-islands **Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search), [Union Find](https://scaleengineer.com/algorithms/union-find) **Data structures:** Array, Matrix **Companies:** [Barclays](https://scaleengineer.com/companies/barclays), [ByteDance](https://scaleengineer.com/companies/bytedance), [Cisco](https://scaleengineer.com/companies/cisco), [Comcast](https://scaleengineer.com/companies/comcast), [Docusign](https://scaleengineer.com/companies/docusign), [DoorDash](https://scaleengineer.com/companies/doordash), [Dropbox](https://scaleengineer.com/companies/dropbox), [EarnIn](https://scaleengineer.com/companies/earnin), [Expedia](https://scaleengineer.com/companies/expedia), [Flipkart](https://scaleengineer.com/companies/flipkart), [Goldman Sachs](https://scaleengineer.com/companies/goldman-sachs), [Huawei](https://scaleengineer.com/companies/huawei), [Infosys](https://scaleengineer.com/companies/infosys), [Intel](https://scaleengineer.com/companies/intel), [Intuit](https://scaleengineer.com/companies/intuit), [Karat](https://scaleengineer.com/companies/karat), [LinkedIn](https://scaleengineer.com/companies/linkedin), [Morgan Stanley](https://scaleengineer.com/companies/morgan-stanley), [Nutanix](https://scaleengineer.com/companies/nutanix), [Nvidia](https://scaleengineer.com/companies/nvidia), [Oracle](https://scaleengineer.com/companies/oracle), [PayPal](https://scaleengineer.com/companies/paypal), [Qualcomm](https://scaleengineer.com/companies/qualcomm), [SAP](https://scaleengineer.com/companies/sap), [Samsung](https://scaleengineer.com/companies/samsung), [ServiceNow](https://scaleengineer.com/companies/servicenow), [Siemens](https://scaleengineer.com/companies/siemens), [Snowflake](https://scaleengineer.com/companies/snowflake), [SoFi](https://scaleengineer.com/companies/sofi), [Tinkoff](https://scaleengineer.com/companies/tinkoff), [Visa](https://scaleengineer.com/companies/visa), [Walmart Labs](https://scaleengineer.com/companies/walmart-labs), [Wix](https://scaleengineer.com/companies/wix), [Yandex](https://scaleengineer.com/companies/yandex), [Zoho](https://scaleengineer.com/companies/zoho), [eBay](https://scaleengineer.com/companies/ebay), [Capital One](https://scaleengineer.com/companies/capital-one), [Coupang](https://scaleengineer.com/companies/coupang), [HPE](https://scaleengineer.com/companies/hpe), [Lucid Motors](https://scaleengineer.com/companies/lucid-motors), [Salesforce](https://scaleengineer.com/companies/salesforce), [Tesla](https://scaleengineer.com/companies/tesla), [Turing](https://scaleengineer.com/companies/turing), [Zeta](https://scaleengineer.com/companies/zeta), [Citadel](https://scaleengineer.com/companies/citadel), [Snap](https://scaleengineer.com/companies/snap), [Zenefits](https://scaleengineer.com/companies/zenefits), [BlackRock](https://scaleengineer.com/companies/blackrock), [Disney](https://scaleengineer.com/companies/disney), [PhonePe](https://scaleengineer.com/companies/phonepe), [UiPath](https://scaleengineer.com/companies/uipath), [Zepto](https://scaleengineer.com/companies/zepto), [BitGo](https://scaleengineer.com/companies/bitgo), [X](https://scaleengineer.com/companies/x), [HashedIn](https://scaleengineer.com/companies/hashedin), [Booking.com](https://scaleengineer.com/companies/booking.com), [Axon](https://scaleengineer.com/companies/axon), [Cloudflare](https://scaleengineer.com/companies/cloudflare), [Zomato](https://scaleengineer.com/companies/zomato), [Pinterest](https://scaleengineer.com/companies/pinterest), [Anduril](https://scaleengineer.com/companies/anduril), [Zillow](https://scaleengineer.com/companies/zillow), [Grammarly](https://scaleengineer.com/companies/grammarly), [Palantir Technologies](https://scaleengineer.com/companies/palantir-technologies), [Rivian](https://scaleengineer.com/companies/rivian), [Urban Company](https://scaleengineer.com/companies/urban-company), [Waymo](https://scaleengineer.com/companies/waymo), [Akuna Capital](https://scaleengineer.com/companies/akuna-capital), [CrowdStrike](https://scaleengineer.com/companies/crowdstrike), [Moloco](https://scaleengineer.com/companies/moloco), [Whatnot](https://scaleengineer.com/companies/whatnot), [thoughtspot](https://scaleengineer.com/companies/thoughtspot), [Hotstar](https://scaleengineer.com/companies/hotstar), [Reddit](https://scaleengineer.com/companies/reddit), [BILL Holdings](https://scaleengineer.com/companies/bill-holdings), [OKX](https://scaleengineer.com/companies/okx) --- ## 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.length` * `n == grid[i].length` * `1 <= m, n <= 300` * `grid[i][j]` is `'0'` or `'1'`. # Approaches ## Brute Force with Nested Loops 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. **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) **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 ### Explanation 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: ```java 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. ### Algorithm 1. Initialize a counter for the number of islands to 0 2. Iterate through each cell in the grid using nested loops 3. 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' 4. Return the island counter ## BFS with Queue 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. **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) **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 ### Explanation 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. ```java 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 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. ### Algorithm 1. Initialize a counter for the number of islands to 0 2. Iterate through each cell in the grid using nested loops 3. When a land cell ('1') is found: - Increment the island counter - Use BFS with a queue to mark all connected land cells as visited 4. 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 5. Return the island counter ## Union-Find (Disjoint Set) 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. **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 **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 ### Explanation 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: 1. Initialize a Union-Find data structure with each land cell as a separate set 2. Iterate through the grid and for each land cell, union it with its adjacent land cells 3. Count the number of distinct sets (islands) ```java 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. ### Algorithm 1. Create a Union-Find data structure 2. Initialize each land cell as a separate set and count the total number of land cells 3. 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 4. Return the final count of distinct sets ## DFS with Constant Space (Optimal) 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). **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 **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 ### Explanation 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'). ```java 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: ```java 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 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. ### Algorithm 1. Initialize a counter for the number of islands to 0 2. Iterate through each cell in the grid using nested loops 3. 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' 4. Optionally, restore the grid to its original state if needed 5. Return the island counter # Solutions ### CSharp ```csharp 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 ; } } ``` ### Java ```java 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); } } } } ``` ### CPP ```cpp class Solution { public: int numIslands(vector> &grid) { int m = grid.size(); int n = grid[0].size(); int ans = 0; int dirs[5] = {-1, 0, 1, 0, -1}; function 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; } }; ``` ### Python ```python # 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 ans ```