leetcode

commit 645b8954b236b5417fb0d1e51425b3dfcf11bc2e
parent 9fce40e7e010e496dce11e684915d7d648135538
Author: Andrew Laack <andrew@laack.co>
Date:   Wed, 16 Jul 2025 14:56:08 -0500

Completed number of islands

Diffstat:
A
number-of-islands/number-of-islandsV1.py
 | 
44
++++++++++++++++++++++++++++++++++++++++++++

1 file changed, 44 insertions(+), 0 deletions(-)
diff --git a/number-of-islands/number-of-islandsV1.py b/number-of-islands/number-of-islandsV1.py
@@ -0,0 +1,44 @@
+# loop over the entire grid
+# if current_val == 1:
+# bfs to find connected component
+# when performing bfs, set each position to -1
+# increment connected component counter
+# return # of connected components
+
+
+class Solution:
+    def numIslands(self, grid: List[List[str]]) -> int:
+
+        count = 0
+
+        for y in range(len(grid)):
+            for x in range(len(grid[y])):
+                if grid[y][x] == "1":
+                    mark_cc(y, x, grid)
+                    count += 1
+        return count
+
+
+def mark_cc(y_pos, x_pos, board):
+
+    # visited already or water
+    if board[y_pos][x_pos] != "1":
+        return
+
+    board[y_pos][x_pos] = "-1"
+
+    # left
+    if x_pos > 0:
+        mark_cc(y_pos, x_pos - 1, board)
+
+    # right
+    if x_pos < len(board[0]) - 1:
+        mark_cc(y_pos, x_pos + 1, board)
+
+    # up
+    if y_pos > 0:
+        mark_cc(y_pos - 1, x_pos, board)
+
+    # down
+    if y_pos < len(board) - 1:
+        mark_cc(y_pos + 1, x_pos, board)