827: Making-A-Large-Island
Hard

table of contents

For a hard question, you can solve this question in quite an intuitive manner.

The question asks us to find the largest island after changing at most one 0 to be 1.

First off, we know we must pre-compute the areas of each island in the n x n binary grid, as otherwise we might just end up recalcalculating areas we have seen before. We can do this by simply iterating through grid and running breadth-first search on any island tiles that we have not seen before to calculate its area.

However, when trying to find the largest island after changing at most one 0 to be 1, we need some method to easily retrieve the area of a respective island neighbouring the changed hex. To do this, we can modify our BFS algorithm so that each island tile in grid gets changed into an index pointer in an array, areas, that stores the areas of each respective island.

Therefore, we can simply just run a second iteration of grid, and if the current tile, grid[i][j] == 0, then we check the tile above, below, left and right to see if there is an island present. If there is/are island/s present, then we simply just sum all their respective areas together, and keep track of the largest in ans.

code

class Solution {
private:
    int bfs (int index, int x, int y, vector<vector<int>> &grid) {
        int ans = 1;
        grid[x][y] = index;
        if (x > 0 && grid[x-1][y] == 1) {
            ans += bfs(index, x-1, y, grid);
        }
        if (x < grid.size()-1 && grid[x+1][y] == 1) {
            ans += bfs(index, x+1, y, grid);
        }
        if (y > 0 && grid[x][y-1] == 1) {
            ans += bfs(index, x, y-1, grid);
        }
        if (y < grid.size()-1 && grid[x][y+1] == 1) {
            ans += bfs(index, x, y+1, grid);
        }
        return ans;
    }
public:
    int largestIsland(vector<vector<int>>& grid) {
        vector<int> areas;
        int index = 2;
        int ans = 0;
        int n = grid.size();
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 1) {
                    areas.push_back(bfs(index, i, j, grid));
                    ans = max(ans, areas[areas.size()-1]);
                    ++index;
                }
            }
        }
        int temp_ans;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                temp_ans = 1;
                int prev_square[3] = {0, 0, 0};
                if (grid[i][j] == 0) {
                    if(i > 0 && grid[i - 1][j] > 0) {
                        prev_square[0] = grid[i - 1][j];
                        temp_ans += areas[prev_square[0] - 2];
                    }

                    if(i < n-1 && grid[i + 1][j] > 0) {
                        if(grid[i + 1][j] != prev_square[0]) {
                            prev_square[1] = grid[i + 1][j];
                            temp_ans += areas[prev_square[1] - 2];
                        }
                    }

                    if(j > 0 && grid[i][j - 1] > 0) {
                        if(grid[i][j - 1] != prev_square[0] && grid[i][j - 1] != prev_square[1]) {
                            prev_square[2] = grid[i][j - 1];
                            temp_ans += areas[prev_square[2] - 2];
                        }
                    }

                    if(j < n-1 && grid[i][j + 1] > 0) {
                        if(grid[i][j + 1] != prev_square[0] && grid[i][j + 1] != prev_square[1] && grid[i][j + 1] != prev_square[2]) {
                            temp_ans += areas[grid[i][j + 1] - 2];
                        }
                    }

                    ans = max(temp_ans, ans);
                }
            }
        }

        return ans == 0 ? 1 : ans;
    }
};

complexity