Count regions with DFS

Given an m x n grid of 0s and 1s, count the number of connected regions consisting of 1s using depth-first search (4-directional adjacency). Return the count. Discuss time and space complexity, show both recursive and iterative (stack-based) approaches, and explain how you would avoid revisiting cells. Consider edge cases like empty grids and very large inputs.

Count Connected Regions (Number of Islands)

Given an m x n grid of 0s and 1s, count the number of connected regions consisting of 1s. Two cells belong to the same region if they are both 1 and are 4-directionally adjacent (up, down, left, right). Diagonal adjacency does NOT connect cells.

Return the total number of distinct regions.

This is the classic "Number of Islands" problem solved with depth-first search. As you visit each cell, mark it as seen so you never revisit it — that keeps the traversal O(m·n). You can use either recursive DFS or an explicit stack (iterative DFS) to flood-fill each region; the stack-based form avoids deep recursion on very large or pathological inputs.

Example:

grid = [[1,1,0,0,0],
        [1,1,0,0,0],
        [0,0,1,0,0],
        [0,0,0,1,1]]

There are 3 regions: the 2x2 block of 1s in the top-left, the single 1 in the middle, and the pair of 1s in the bottom-right. So the answer is 3.

Constraints

• 1 <= m, n is the grid dimensions; the grid may also be empty ([] or [[]]), which has 0 regions.
• grid[i][j] is either 0 or 1.
• Adjacency is 4-directional only (up, down, left, right) — diagonals do not connect.
• Mark each cell as visited the moment you enqueue/push it to avoid revisiting and double-counting.

Hints

1. Scan every cell. When you find a 1 that hasn't been visited yet, you've found a new region — increment your counter, then flood-fill the entire region so its cells aren't counted again.
2. Flood-fill with DFS: from the starting cell, visit all 4-directionally adjacent 1s, then their neighbors, and so on. Mark a cell as seen before pushing it so it's never added to the stack twice.
3. For the iterative version, use an explicit stack of (row, col). Pop a cell, look at its 4 neighbors, and push any in-bounds, unvisited 1-cells. This avoids recursion-depth limits on huge grids.
4. Handle empty inputs first: [] and [[]] should return 0 before you index into rows.