Formatted question description: https://leetcode.ca/all/827.html

827. Making A Large Island (Hard)

In a 2D grid of 0s and 1s, we change at most one 0 to a 1.

After, what is the size of the largest island? (An island is a 4-directionally connected group of 1s).

Example 1:

Input: [[1, 0], [0, 1]]
Output: 3
Explanation: Change one 0 to 1 and connect two 1s, then we get an island with area = 3.

Example 2:

Input: [[1, 1], [1, 0]]
Output: 4
Explanation: Change the 0 to 1 and make the island bigger, only one island with area = 4.

Example 3:

Input: [[1, 1], [1, 1]]
Output: 4
Explanation: Can't change any 0 to 1, only one island with area = 4.

 

Notes:

  • 1 <= grid.length = grid[0].length <= 50.
  • 0 <= grid[i][j] <= 1.

 

Related Topics: Depth-first Search

Solution 1. Union Find

// OJ: https://leetcode.com/problems/making-a-large-island/

// Time: O(MN)
// Space: O(MN)
class UnionFind {
    vector<int> id, size;
public:
    UnionFind(int N) : id(N), size(N, 1) {
        iota(begin(id), end(id), 0);
    }
    int find(int x) {
        return id[x] == x ? x : (id[x] = find(id[x]));
    }
    void connect(int x, int y) {
        int p = find(x), q = find(y);
        if (p == q) return;
        id[p] = q;
        size[q] += size[p];
    }
    int getSize(int x) { return size[find(x)]; }
};
class Solution {
public:
    int largestIsland(vector<vector<int>>& G) {
        int M = G.size(), N = G[0].size(), dirs[4][2] = { {0,1},{0,-1},{1,0},{-1,0} }, ans = 0;
        UnionFind uf(M * N);
        for (int i = 0; i < M; ++i) {
            for (int j = 0; j < N; ++j) {
                if (G[i][j] == 0) continue;
                for (auto &[dx, dy] : dirs) {
                    int x = i + dx, y = j + dy;
                    if (x < 0 || y < 0 || x >= M || y >= N || G[x][y] == 0) continue;
                    uf.connect(i * N + j, x * N + y);
                }
                ans = max(ans, uf.getSize(i * N + j));
            }
        }
        for (int i = 0; i < M; ++i) {
            for (int j = 0; j < N; ++j) {
                if (G[i][j] == 1) continue;
                unordered_map<int, int> m;
                for (auto &[dx, dy] : dirs) {
                    int x = i + dx, y = j + dy;
                    if (x < 0 || y < 0 || x >= M || y >= N || G[x][y] == 0) continue;
                    m[uf.find(x * N + y)] = uf.getSize(x * N + y);
                }
                int size = 1;
                for (auto &p : m) size += p.second;
                ans = max(ans, size);
            }
        }
        return ans;
    }
};

Java

class Solution {
    int[][] directions = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };

    public int largestIsland(int[][] grid) {
        int side = grid.length;
        int[][] islandNumbers = new int[side][side];
        int islandCount = 0;
        int maxSize = 0;
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        List<int[]> zeros = new ArrayList<int[]>();
        for (int i = 0; i < side; i++) {
            for (int j = 0; j < side; j++) {
                if (grid[i][j] == 0)
                    zeros.add(new int[]{i, j});
                else if (islandNumbers[i][j] == 0) {
                    islandCount++;
                    int size = breadthFirstSearch(grid, islandNumbers, islandCount, i, j);
                    maxSize = Math.max(maxSize, size);
                    map.put(islandCount, size);
                }
            }
        }
        for (int[] zero : zeros) {
            int size = 1;
            Set<Integer> islandsSet = new HashSet<Integer>();
            int row = zero[0], column = zero[1];
            for (int[] direction : directions) {
                int newRow = row + direction[0], newColumn = column + direction[1];
                if (newRow >= 0 && newRow < side && newColumn >= 0 && newColumn < side) {
                    int islandNumber = islandNumbers[newRow][newColumn];
                    if (islandNumber > 0)
                        islandsSet.add(islandNumber);
                }
            }
            for (int island : islandsSet)
                size += map.get(island);
            maxSize = Math.max(maxSize, size);
        }
        return maxSize;
    }

    public int breadthFirstSearch(int[][] grid, int[][] islandNumbers, int islandCount, int row, int column) {
        int size = 0;
        islandNumbers[row][column] = islandCount;
        int side = grid.length;
        Queue<int[]> queue = new LinkedList<int[]>();
        queue.offer(new int[]{row, column});
        while (!queue.isEmpty()) {
            int[] cell = queue.poll();
            size++;
            int curRow = cell[0], curColumn = cell[1];
            for (int[] direction : directions) {
                int newRow = curRow + direction[0], newColumn = curColumn + direction[1];
                if (newRow >= 0 && newRow < side && newColumn >= 0 && newColumn < side && grid[newRow][newColumn] == 1 && islandNumbers[newRow][newColumn] == 0) {
                    islandNumbers[newRow][newColumn] = islandCount;
                    queue.offer(new int[]{newRow, newColumn});
                }
            }
        }
        return size;
    }
}

All Problems

All Solutions