An Interest In:
Web News this Week
- April 25, 2024
- April 24, 2024
- April 23, 2024
- April 22, 2024
- April 21, 2024
- April 20, 2024
- April 19, 2024
Leetcode Number Of Islands
In this post we'll have a look at LeetCode problem #200 called Number Of Islands.
The problem statement is quite straightforward. Given a grid of 1s and 0s, we need to find the total number of islands in a given grid.
They mention:
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.
For example:
Input: grid = [ ["1","1","1","1","0"], ["1","1","0","1","0"], ["1","1","0","0","0"], ["0","0","0","0","0"]]Output: 1
And another example:
Input: grid = [ ["1","1","0","0","0"], ["1","1","0","0","0"], ["0","0","1","0","0"], ["0","0","0","1","1"]]Output: 3
How do we solve it?
My approach is to look at each (unvisited) cell in the grid, if it contains 1 then (recursively) expand outward from there as long as its neighbour also has a 1. This is called BFS (breadth first search).
When we visit a cell, we'll mark that cell as visited, such that we'll not visit it again later.
Here's the solution:
class Solution: def numIslands(self, grid): ROWS, COLS = len(grid), len(grid[0]) res = 0 visited = set() def dfs(r,c): if r<0 or c<0 or r>=ROWS or c>=COLS or (r,c) in visited or grid[r][c] != "1": return visited.add((r,c)) dfs(r+1,c) dfs(r-1,c) dfs(r,c+1) dfs(r,c-1) for r in range(ROWS): for c in range(COLS): if grid[r][c] == "1" and (r,c) not in visited: res += 1 dfs(r,c) return res
The code itself is also very straightforward to understand. I hope you find it helpful.
Note that we can avoid using a visited set by simply marking 1s with some symbol, like a # sign.
--
Cover Photo by Sacha Gregoire on Unsplash
Original Link: https://dev.to/omkarscode/leetcode-number-of-islands-51dk
Dev To
An online community for sharing and discovering great ideas, having debates, and making friendsMore About this Source Visit Dev To