Documentation Index
Fetch the complete documentation index at: /llms.txt
Use this file to discover all available pages before exploring further.
Tested Python solution for LeetCode 200 with 14 pytest cases. Generate a practice environment with lcpy.
lcpy gen -n 200 # by problem number
lcpy gen -s number_of_islands # by problem name
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.
Input: grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
Output: 1
Input: grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
Output: 3
m == grid.lengthn == grid[i].length1 <= m, n <= 300grid[i][j] is '0' or '1'.class Solution:
# Time: O(m * n) where m = rows, n = cols
# Space: O(m * n) for recursion stack in worst case
def num_islands(self, grid: list[list[str]]) -> int:
if not grid or not grid[0]:
return 0
VISITED = "0" # noqa: N806
UNVISITED_ISLAND = "1" # noqa: N806
rows, cols = len(grid), len(grid[0])
islands = 0
def dfs(r: int, c: int) -> None:
if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != UNVISITED_ISLAND:
return
grid[r][c] = VISITED
for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
dfs(r + dr, c + dc)
for r in range(rows):
for c in range(cols):
if grid[r][c] == UNVISITED_ISLAND:
islands += 1
dfs(r, c)
return islands
| Time | Space |
|---|---|
| O(m * n) where m = rows, n = cols | O(m * n) for recursion stack in worst case |