Number of Islands

Count connected land components

Scan the grid. When a land cell has not been visited, increment the island count and run DFS or BFS from it through the permitted neighbors. Mark a cell visited when it is pushed or recursed into, not when removed, so it cannot be queued repeatedly. The traversal turns the entire connected component into visited water conceptually.

Every cell is examined a constant number of times, giving O(rows * cols) time. A separate visited matrix uses O(rows * cols) space; mutating the input from land to water reduces that to traversal stack/queue space, up to O(rows * cols) in the worst case. Explicitly ask whether diagonal neighbors connect islands: standard variants use four directions, but eight directions changes the direction list. Test an empty grid, all water, one large island, isolated cells, a single row, and ragged input only if permitted. Avoid calling DFS from every land cell without marking it, which repeats work.