Making A Large Island

Hard Graphs Connected Components Original on LeetCode

Making A Large Island is a hard graphs problem solved with the connected components pattern. The best approach, optimal (label islands, then try each water cell), runs in O(n²) time and O(n²) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (flip each water cell and flood fill) up.

Problem

You are given an n x n binary grid where 1 is land and 0 is water. An island is a group of land cells connected up, down, left or right.

You may turn at most one water cell into land. Return the size (number of cells) of the largest island the grid can have after that change.

Examples

Example 1

Input
grid = [[1,1,0],[0,0,1],[1,0,1]]
Output
5
Why
Turning the cell at [1,1] into land joins the island of size 2 at the top with the island of size 2 on the right: 2 + 2 + 1 = 5.

Example 2

Input
grid = [[1,1],[1,1]]
Output
4
Why
There is no water to flip, so the answer is the whole grid.

Example 3

Input
grid = [[0,0],[0,0]]
Output
1
Why
Flipping any one cell creates an island of size 1.

Constraints

  • n == grid.length == grid[i].length
  • 1 <= n <= 500
  • grid[i][j] is 0 (water) or 1 (land).
  • You may change at most one 0 to 1; changing none is also allowed.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (flip each water cell and flood fill)O(n⁴)O(n²)
Optimal (label islands, then try each water cell)O(n²)O(n²)

1Brute force (flip each water cell and flood fill)

TimeO(n⁴)Up to n² water cells, each followed by a BFS over up to n² cells.
SpaceO(n²)The visited array and queue of one BFS.

For every water cell, pretend it is land and run a BFS from it to measure the island it now belongs to. The best of these is the answer; if there is no water, the whole grid is already one island.

  1. For each cell with grid[i][j] == 0: set it to 1, BFS from it counting cells, set it back to 0.
  2. Track the largest count.
  3. If no water cell was found, return n · n.
class Solution {
    public int largestIsland(int[][] grid) {
        int n = grid.length, best = 0;
        boolean hasWater = false;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++) {
                if (grid[i][j] != 0) continue;
                hasWater = true;
                grid[i][j] = 1;
                best = Math.max(best, measure(grid, i, j));
                grid[i][j] = 0;
            }
        return hasWater ? best : n * n;
    }

    private int measure(int[][] grid, int sr, int sc) {
        int n = grid.length, size = 0;
        int[][] dirs = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
        boolean[][] seen = new boolean[n][n];
        ArrayDeque<int[]> q = new ArrayDeque<>();
        q.add(new int[] { sr, sc });
        seen[sr][sc] = true;
        while (!q.isEmpty()) {
            int[] c = q.poll();
            size++;
            for (int[] d : dirs) {
                int x = c[0] + d[0], y = c[1] + d[1];
                if (x >= 0 && y >= 0 && x < n && y < n && !seen[x][y] && grid[x][y] == 1) {
                    seen[x][y] = true;
                    q.add(new int[] { x, y });
                }
            }
        }
        return size;
    }
}

2Optimal (label islands, then try each water cell)

TimeO(n²)Each cell is labelled once and each water cell looks at 4 neighbours.
SpaceO(n²)The id-to-size map and the flood-fill stack. The grid itself is reused for the ids.

First pass: flood fill every island once, writing an id (2, 3, 4, …) into its cells and storing the island's size under that id. Second pass: for each water cell, collect the distinct ids among its four neighbours and add up their sizes plus 1 for the cell itself. The largest such total (or the largest island when there is no water) is the answer.

  1. id = 2; for each land cell still marked 1, flood fill it with id, store size[id], id++.
  2. best = largest size (n · n if there is no water, since then one island fills the grid).
  3. For each 0 cell: seen = distinct neighbour ids; total = 1 + sum of size[id] for id in seen; best = max(best, total).
  4. Return best.
class Solution {
    public int largestIsland(int[][] grid) {
        int n = grid.length;
        int[][] dirs = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
        List<Integer> size = new ArrayList<>(List.of(0, 0));
        int best = 0;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++) {
                if (grid[i][j] != 1) continue;
                int id = size.size(), count = 0;
                ArrayDeque<int[]> st = new ArrayDeque<>();
                st.push(new int[] { i, j });
                grid[i][j] = id;
                while (!st.isEmpty()) {
                    int[] c = st.pop();
                    count++;
                    for (int[] d : dirs) {
                        int x = c[0] + d[0], y = c[1] + d[1];
                        if (x >= 0 && y >= 0 && x < n && y < n && grid[x][y] == 1) {
                            grid[x][y] = id;
                            st.push(new int[] { x, y });
                        }
                    }
                }
                size.add(count);
                best = Math.max(best, count);
            }
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++) {
                if (grid[i][j] != 0) continue;
                Set<Integer> seen = new HashSet<>();
                int total = 1;
                for (int[] d : dirs) {
                    int x = i + d[0], y = j + d[1];
                    if (x >= 0 && y >= 0 && x < n && y < n && grid[x][y] > 1 && seen.add(grid[x][y]))
                        total += size.get(grid[x][y]);
                }
                best = Math.max(best, total);
            }
        return best;
    }
}

Edge cases to test

  • No water at all (answer n²)
  • No land at all (answer 1)
  • A water cell touching the same island from two or more sides (count that island once)
  • A 1 x 1 grid

Hints

Hint 1

Trying every water cell and re-measuring the island from scratch works, but repeats a lot of the same flood fills.

Hint 2

Measure each existing island once. Give every island an id and remember its size.

Hint 3

For a water cell, the new island is 1 plus the sizes of the distinct island ids among its four neighbours. Use a small set so an island touching two sides is not counted twice.

FAQ

What is the best time complexity for Making A Large Island?

Optimal (label islands, then try each water cell) runs in O(n²) time and O(n²) extra space. Each cell is labelled once and each water cell looks at 4 neighbours.

Which pattern does Making A Large Island use?

It is a graphs problem that uses the connected components pattern. Other problems with the same pattern: Number of Provinces, Number of Islands, Evaluate Division.

Is there a brute force solution for Making A Large Island?

Yes. Brute force (flip each water cell and flood fill) takes O(n⁴) time and O(n²) space. For every water cell, pretend it is land and run a BFS from it to measure the island it now belongs to.

Which edge cases should I test for Making A Large Island?

No water at all (answer n²); No land at all (answer 1); A water cell touching the same island from two or more sides (count that island once); A 1 x 1 grid.