Number of Islands

Difficulty: Medium

Problem

You are given a grid where every cell is either '1' (land) or '0' (water). Count the number of islands. An island is a group of land cells connected 4-directionally — up, down, left, right. Diagonal touching does NOT connect land, and you may assume water surrounds all four edges of the grid.

Example

Input: grid = [["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]]
Output: 3
Explanation: Three separate pieces of land: the 2×2 block in the top-left, the lone cell at (2,2) in the middle, and the pair (3,3)–(3,4) in the bottom-right.

Brute-force approach

There is no separate brute force worth writing — scan-and-flood IS the natural solution. (The true 'brute force', exploring from every land cell without marking anything, just recounts the same island over and over.)

Optimal approach

Key insight: The scan finds each island exactly once; the flood erases it so it can never be found again. Count the finds.

Walk every cell of the grid in reading order. Each time you step on land that hasn't been sunk yet, that's a brand-new island: count it, then flood-sink every cell of it so the scan can never count it again.

Steps

1. Scan the grid row by row, left to right
2. On unsunk land ('1'): a never-before-seen island — count += 1
3. Immediately sink(r, c): DFS in all 4 directions, flipping every cell of the island to '0'
4. Sunk cells fail the '1' check later, so the scan glides right past them
5. When the scan finishes, count is the answer

Time complexity: O(rows × cols) · Space complexity: O(rows × cols) worst-case recursion