Crack the Backend

Problem Statement

Given a 2D grid grid of '1' (land) and '0' (water), return the number of islands. An island is formed by connecting adjacent lands horizontally or vertically (4 directions). You may assume all four edges of the grid are surrounded by water.

Connected means up/down/left/right; diagonal does not count.
We need to count connected components of '1's. Modifying the grid in place (e.g. setting visited '1' to '0') avoids extra visited structure.

Key Observations

The grid can be seen as a graph: each '1' is a node; edges connect adjacent '1's (4-neighborhood). The number of islands is the number of connected components in this graph.
From each unvisited '1', run DFS or BFS to visit all '1's in the same island. Mark them as visited (e.g. flip to '0') so we do not count the same island again. Increment a counter for each new island we start.
DFS/BFS from (i,j) explores all cells reachable by 4-directional steps; that is exactly one island.

Approach

High-level: Scan the grid. Whenever we find a '1', we have found a new island; run DFS or BFS from that cell to mark the entire island as visited (e.g. set to '0'), then increment the island count. Return the count.

Steps:

count = 0. For each (r, c): if grid[r][c] == '1', increment count and run DFS/BFS from (r, c) that sets all connected '1's to '0' (or mark visited).
DFS/BFS: from (r,c), check 4 neighbors; if a neighbor is in bounds and is '1', recurse or enqueue it and mark it.
Return count.

Implementation

Java

public int numIslands(char[][] grid) {
    int count = 0;

    for (int r = 0; r < grid.length; r++)
    for (int c = 0; c < grid[0].length; c++)
    if (grid[r][c] == '1') { dfs(grid, r, c); count++; }
    return count;
}

void dfs(char[][] g, int r, int c) {

    if (r<0||r>=g.length||c<0||c>=g[0].length||g[r][c]!='1') {
        return;
    }

    g[r][c] = '0';
    dfs(g,r+1,c); dfs(g,r-1,c); dfs(g,r,c+1); dfs(g,r,c-1);
}

Test Cases

Example 1

Input

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

Expected

1

Explanation

One island.

Complexity Analysis

Time: O(m*n).
Space: O(m*n) recursion or O(min(m,n)) with iterative.

Follow-ups

Number of Islands II: add land one by one; count after each add (Union-Find).