Making A Large Island - Practice Coding Problems

Making A Large Island - Problem

You are given an n x n binary matrix grid. You are allowed to change at most one 0 to be 1.

Return the size of the largest island in grid after applying this operation.

An island is a 4-directionally connected group of 1s.

Input & Output

Example 1 — Basic Island Connection

$ Input: grid = [[1,0],[0,1]]

› Output: 3

💡 Note: Change either 0 to 1: grid becomes [[1,1],[0,1]] or [[1,0],[1,1]]. Both create an island of size 3.

Example 2 — Multiple Disconnected Islands

$ Input: grid = [[1,1],[1,0]]

› Output: 4

💡 Note: Change the 0 at position (1,1) to 1. The entire grid becomes land, creating one island of size 4.

Example 3 — All Water

$ Input: grid = [[0,0],[0,0]]

› Output: 1

💡 Note: Change any 0 to 1. Since no islands exist to connect, the maximum size is 1.

Constraints

n == grid.length
n == grid[i].length
1 ≤ n ≤ 500
grid[i][j] is either 0 or 1

Visualization

Tap to expand

Understanding the Visualization

Input Grid

Binary matrix with 1s (land) and 0s (water)

Find Best Position

Test each water cell to see which creates largest connected island

Maximum Island Size

Return the size of largest island after changing one 0 to 1

Key Takeaway

🎯 Key Insight: Pre-label islands with unique IDs to avoid recalculating sizes when testing bridge positions

Asked in

G Google 15 f Facebook 12 a Amazon 8

The key insight is to avoid recalculating island sizes by pre-labeling each island with a unique ID and storing their sizes. The optimal island labeling approach uses two passes: first to label and measure all existing islands, then to test each water position by summing adjacent island sizes. Time: O(n²), Space: O(n²)

Common Approaches

Approach	Time	Space	Notes
✓ Island Labeling with DFS	O(n²)	O(n²)	Label each existing island with unique ID, then find best position to connect islands
Brute Force - Try Every Position	O(n⁴)	O(n²)	For each 0, temporarily change it to 1 and calculate the resulting island size

Island Labeling with DFS — Algorithm Steps

Step 1: Use DFS to label each island with unique ID (2, 3, 4, ...) and store sizes
Step 2: For each water cell (0), check adjacent cells to see which islands it connects
Step 3: Sum the sizes of connected islands plus 1 for the new cell

Visualization

Tap to expand

Step-by-Step Walkthrough

Label Islands

Assign unique ID to each connected island

Record Sizes

Store the size of each labeled island

Find Best Bridge

For each water cell, sum adjacent island sizes

Code -

solution.c — C

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

int dfs(int** grid, int** labeledGrid, int n, int i, int j, int label) {
    if (i < 0 || i >= n || j < 0 || j >= n || grid[i][j] == 0 || labeledGrid[i][j] != 0) {
        return 0;
    }
    labeledGrid[i][j] = label;
    return 1 + dfs(grid, labeledGrid, n, i+1, j, label) + dfs(grid, labeledGrid, n, i-1, j, label) + 
           dfs(grid, labeledGrid, n, i, j+1, label) + dfs(grid, labeledGrid, n, i, j-1, label);
}

int solution(int** grid, int n) {
    if (n == 0) return 0;
    
    // Label each island with unique ID and calculate sizes
    int* islandSizes = (int*)calloc(n*n + 10, sizeof(int));  // Max possible islands
    int** labeledGrid = (int**)malloc(n * sizeof(int*));
    for (int i = 0; i < n; i++) {
        labeledGrid[i] = (int*)calloc(n, sizeof(int));
    }
    int islandId = 2;  // Start from 2 (0=water, 1=original land)
    
    // First pass: label all islands
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 1 && labeledGrid[i][j] == 0) {
                int size = dfs(grid, labeledGrid, n, i, j, islandId);
                islandSizes[islandId] = size;
                islandId++;
            }
        }
    }
    
    // If no water cells exist, return total land area
    bool hasWater = false;
    for (int i = 0; i < n && !hasWater; i++) {
        for (int j = 0; j < n && !hasWater; j++) {
            if (grid[i][j] == 0) hasWater = true;
        }
    }
    if (!hasWater) {
        free(islandSizes);
        for (int i = 0; i < n; i++) {
            free(labeledGrid[i]);
        }
        free(labeledGrid);
        return n * n;
    }
    
    int maxSize = 0;
    int directions[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    
    // Second pass: try each water cell
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 0) {
                bool* seen = (bool*)calloc(n*n + 10, sizeof(bool));
                int size = 1;  // The water cell itself becomes land
                
                for (int d = 0; d < 4; d++) {
                    int ni = i + directions[d][0];
                    int nj = j + directions[d][1];
                    if (ni >= 0 && ni < n && nj >= 0 && nj < n && labeledGrid[ni][nj] > 0) {
                        int island = labeledGrid[ni][nj];
                        if (!seen[island]) {
                            seen[island] = true;
                            size += islandSizes[island];
                        }
                    }
                }
                
                if (size > maxSize) {
                    maxSize = size;
                }
                free(seen);
            }
        }
    }
    
    free(islandSizes);
    for (int i = 0; i < n; i++) {
        free(labeledGrid[i]);
    }
    free(labeledGrid);
    return maxSize;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Simple parsing for small grids - assumes format [[1,0],[0,1]]
    int n = 0;
    // Count rows by counting '],' patterns + 1
    for (int i = 0; line[i]; i++) {
        if (line[i] == ']' && line[i+1] == ',') n++;
    }
    n++; // Add 1 for the last row
    
    int** grid = (int**)malloc(n * sizeof(int*));
    for (int i = 0; i < n; i++) {
        grid[i] = (int*)malloc(n * sizeof(int));
    }
    
    // Parse the grid (simplified parser)
    int row = 0, col = 0;
    for (int i = 0; line[i]; i++) {
        if (line[i] >= '0' && line[i] <= '9') {
            grid[row][col++] = line[i] - '0';
        } else if (line[i] == ']' && line[i+1] == ',') {
            row++;
            col = 0;
        }
    }
    
    int result = solution(grid, n);
    printf("%d\n", result);
    
    for (int i = 0; i < n; i++) {
        free(grid[i]);
    }
    free(grid);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Two passes over the grid, each cell visited constant times

⚠ Quadratic Growth

Space Complexity

O(n²)

Additional grid to store island labels plus recursion stack

⚠ Quadratic Space

89.4K Views

Medium Frequency

~25 min Avg. Time

1.9K 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

Island Labeling with DFS — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler