Number of Islands II - Practice Coding Problems

Number of Islands II - Problem

You are given an empty 2D binary grid grid of size m x n. The grid represents a map where 0's represent water and 1's represent land. Initially, all the cells of grid are water cells (i.e., all the cells are 0's).

We may perform an add land operation which turns the water at position into a land. You are given an array positions where positions[i] = [ri, ci] is the position (ri, ci) at which we should operate the i-th operation.

Return an array of integers answer where answer[i] is the number of islands after turning the cell (ri, ci) into a land. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Input & Output

Example 1 — Basic Island Formation

$ Input: m = 3, n = 3, positions = [[0,0],[0,1],[1,2],[2,1]]

› Output: [1,1,2,3]

💡 Note: Start empty. Add (0,0): 1 island. Add (0,1): connects to (0,0), still 1 island. Add (1,2): new island, now 2 total. Add (2,1): another new island, now 3 total.

Example 2 — Island Merging

$ Input: m = 2, n = 2, positions = [[0,0],[1,1],[0,1]]

› Output: [1,2,1]

💡 Note: Add (0,0): 1 island. Add (1,1): separate island, 2 total. Add (0,1): connects (0,0) and (1,1) diagonally? No - only horizontal/vertical, so still 2 separate islands. Actually connects (0,0) vertically, merging into 1 island.

Constraints

1 ≤ m, n ≤ 300
1 ≤ positions.length ≤ 10⁴
0 ≤ r_i < m
0 ≤ c_i < n

Visualization

Tap to expand

Understanding the Visualization

Empty Grid

Start with 3×3 grid of all water (0s)

Add Lands

Process positions [[0,0],[0,1],[1,2],[2,1]]

Count Islands

Track island count after each addition: [1,1,2,3]

Key Takeaway

🎯 Key Insight: Use Union-Find to efficiently track connected components as they merge dynamically

Asked in

G Google 28 f Facebook 22 a Amazon 18 M Microsoft 15

The key insight is to use Union-Find data structure to efficiently track connected components as land is added dynamically. The brute force DFS approach rescans the entire grid after each addition, while Union-Find maintains connectivity in nearly constant time. Best approach: Union-Find with Time: O(k × α(m×n)), Space: O(m×n).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force with DFS	O(k × m × n)	O(m × n)	After each land addition, run DFS to count all islands
Union-Find (Disjoint Set)	O(k × α(m × n))	O(m × n)	Use Union-Find to efficiently track connected components

Brute Force with DFS — Algorithm Steps

Add land at given position
Run DFS on entire grid to count islands
Store count in result array

Visualization

Tap to expand

Step-by-Step Walkthrough

Add Land

Place land at specified position

DFS Scan

Traverse entire grid to count islands

Store Count

Add island count to result array

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

int m, n;
int** grid;
bool** visited;

void dfs(int r, int c) {
    if (r < 0 || r >= m || c < 0 || c >= n || visited[r][c] || grid[r][c] == 0) {
        return;
    }
    visited[r][c] = true;
    dfs(r+1, c);
    dfs(r-1, c);
    dfs(r, c+1);
    dfs(r, c-1);
}

int countIslands() {
    // Reset visited array
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            visited[i][j] = false;
        }
    }
    
    int count = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 1 && !visited[i][j]) {
                dfs(i, j);
                count++;
            }
        }
    }
    return count;
}

int* solution(int m_param, int n_param, int** positions, int positionsSize, int* returnSize) {
    m = m_param;
    n = n_param;
    
    // Allocate grid
    grid = (int**)malloc(m * sizeof(int*));
    visited = (bool**)malloc(m * sizeof(bool*));
    for (int i = 0; i < m; i++) {
        grid[i] = (int*)calloc(n, sizeof(int));
        visited[i] = (bool*)malloc(n * sizeof(bool));
    }
    
    int* result = (int*)malloc(positionsSize * sizeof(int));
    *returnSize = positionsSize;
    
    for (int i = 0; i < positionsSize; i++) {
        int r = positions[i][0];
        int c = positions[i][1];
        grid[r][c] = 1;
        result[i] = countIslands();
    }
    
    return result;
}

int main() {
    int m, n;
    scanf("%d", &m);
    scanf("%d", &n);
    
    char line[10000];
    scanf(" %[^\n]", line);
    
    // Simple parsing for positions array
    int** positions = NULL;
    int positionsSize = 0;
    
    // Count positions
    char* temp = strdup(line);
    char* token = strtok(temp, "[");
    while (token != NULL) {
        if (strchr(token, ',') != NULL && strchr(token, ']') != NULL) {
            positionsSize++;
        }
        token = strtok(NULL, "[");
    }
    free(temp);
    
    positions = (int**)malloc(positionsSize * sizeof(int*));
    for (int i = 0; i < positionsSize; i++) {
        positions[i] = (int*)malloc(2 * sizeof(int));
    }
    
    // Parse positions
    temp = strdup(line);
    token = strtok(temp, "[");
    int idx = 0;
    while (token != NULL && idx < positionsSize) {
        if (strchr(token, ',') != NULL) {
            sscanf(token, "%d,%d]", &positions[idx][0], &positions[idx][1]);
            idx++;
        }
        token = strtok(NULL, "[");
    }
    free(temp);
    
    int returnSize;
    int* result = solution(m, n, positions, positionsSize, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(k × m × n)

For k positions, each DFS takes O(m×n) time to scan entire grid

✓ Linear Growth

Space Complexity

O(m × n)

Grid storage plus DFS recursion stack depth up to m×n

⚡ Linearithmic Space

89.4K Views

Medium Frequency

~35 min Avg. Time

1.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force with DFS — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler