Count Islands in a Grid

# Count Islands in a Grid Implement `count_islands(grid: list[list[int]]) -> int`. The rectangular grid contains water cells `0` and land cells `1`. An island is a maximal group of land cells connected through shared horizontal or vertical edges. Return the number of islands. ### Input Domain - `0 <= len(grid) <= 2,000`. - If the grid is nonempty, all rows have the same length. - The grid contains at most `1,000,000` cells. - Every cell is exactly `0` or `1`. ### Output Rules - Diagonal contact does not connect two land cells. - Return `0` for an empty grid, empty rows, or a grid containing only water. - The input may be modified by the implementation. ### Constraints - Target time is `O(rows * columns)`. - Avoid recursion whose call depth can grow with the number of cells. ### Examples #### Example 1 Input: `grid = [[1,1,0,0],[1,0,0,1],[0,0,1,1]]` Output: `2` #### Example 2 Input: `grid = [[0,0],[0,0]]` Output: `0` ```hint Consume one connected component at a time When an unvisited land cell is found, traverse every land cell reachable from it before continuing the grid scan. ```