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'.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.
The function dfs is responsible for marking connected '1's as visited by changing them to '0'. The numIslands function traverses each cell in the grid, and upon finding a '1', it increments the count and triggers a DFS from that cell to mark the entire island.
C++
Java
Python
C#
JavaScript
Time Complexity: O(m*n) where m is the number of rows and n is the number of columns since each cell is visited once.
Space Complexity: O(m*n) in the worst case due to the recursion stack used by DFS.
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.
This C implementation utilizes a queue for BFS to explore and mark connected components of each found '1'. An auxiliary structure QueueNode is used to keep track of cell indices being explored. BFS propagates through the nodes layer by layer until the entire island is marked.
C++
Java
Python
C#
JavaScript
Time Complexity: O(m*n), where m and n are rows and columns.#
Space Complexity: O(min(m, n)) due to the queue storage in BFS.
| Approach | Complexity |
|---|---|
| DFS Approach | Time Complexity: O(m*n) where m is the number of rows and n is the number of columns since each cell is visited once. |
| BFS Approach | Time Complexity: O(m*n), where m and n are rows and columns.# |
LeetCode Number of Islands Solution Explained - Java • Nick White • 531,028 views views
Watch 9 more video solutions →Practice Number of Islands with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor