187. Number of Islands in a 2D Grid

Given a grid of 0s (water) and 1s (land), count the number of islands - maximal groups of land cells connected horizontally or vertically (not diagonally).

Input: The first line contains two integers rows and cols. Each of the next rows lines contains cols space-separated values (0 or 1), the grid. Output: Print a single integer - the number of islands.

1 <= rows, cols <= 1000

This is one of the most iconic 'flood fill' style problems - the same technique (scan for an unvisited start, flood-fill to claim its whole region) applies directly to 'Flood Fill Algorithm' and many other grid-connectivity problems in this category.

Count the number of connected land regions in a grid of water and land cells. Brute force: For every land cell, check if it's connected to every OTHER land cell directly - this is far more work than necessary compared to a single flood-fill pass per unvisited land cell found. Optimised: A single scan combined with flood-filling (BFS/DFS) from each newly-found unvisited land cell visits every cell exactly once overall - each flood-fill 'claims' an entire island's cells as visited in one go, so the outer scan never re-processes them.

Use the same scan-and-flood-fill idea, but replace the recursive DFS with an iterative BFS using an explicit queue: when an unvisited land cell is found, push it onto a queue, mark it visited, and repeatedly pop cells, pushing their unvisited land neighbors, until the queue empties, then move to the next island. This produces the identical island count as the recursive version but removes any dependency on the call stack, eliminating the stack-overflow risk on large or oddly-shaped islands while keeping the same overall complexity. Time: O(rows * cols) Space: O(rows * cols)

Scan every cell of the grid; whenever an unvisited land cell ('1') is found, increment the island count and recursively flood-fill in all four directions (marking visited cells, e.g. by flipping them to '0' or a separate visited marker) to sink the entire connected island before continuing the scan. This is the most direct implementation of 'connected component counting', but the recursion depth can reach the size of the largest island, which for a grid up to 1000x1000 (up to 10^6 cells) risks a stack overflow on a long snaking island. Time: O(rows * cols) Space: O(rows * cols)

Process the grid once in row-major order; for every land cell, union it with its land neighbor directly above and directly to the left (if they are also land), using a disjoint-set-union structure with path compression and union by rank/size, while tracking a running island count that decreases by one every time a successful union merges two previously-separate components. This finds the answer in a single pass over the grid with no explicit traversal stack or queue needed at all, running in nearly linear time (technically O(rows*cols * alpha(rows*cols)), where alpha is the inverse Ackermann function and is effectively a small constant), and generalizes naturally if the grid were to be updated incrementally over time. Time: O(rows * cols * alpha(rows * cols)) Space: O(rows * cols)

1. Scan every cell of the grid. 2. Whenever an UNVISITED land cell (value 1) is found, that's the start of a NEW island - increment the island count. 3. Flood-fill outward from it (BFS or DFS), marking every 4-directionally-connected land cell as visited, so it's never counted as a separate island later.

Time: O(rows * cols) - every cell is visited and marked exactly once across the whole process. Space: O(rows * cols) in the worst case, for the visited-tracking grid and the BFS queue or DFS recursion stack.

Test a grid of all water (answer 0), a grid of all land (answer 1), and rows/cols at the upper bound of 1000.

Be precise that only 4-directional (up/down/left/right) neighbors count as connected here, NOT diagonal ones - a common point of ambiguity worth confirming explicitly for any grid-connectivity problem.