# 827. Making A Large Island       • Time: $O(n^2)$
• Space: $O(|\text{connected islands}|)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 class Solution { public: int largestIsland(vector>& grid) { const int m = grid.size(); const int n = grid.size(); int maxSize = 0; // sizes[i] := size of i-th connected component (start from 2) vector sizes{0, 0}; // For each 1 in the grid, paint all connected 1 with the next available // Color (2, 3, and so on). Also, remember the size of the island we just // Painted with that color. for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) if (grid[i][j] == 1) sizes.push_back(paint(grid, i, j, sizes.size())); // Paint 2, 3, ... for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) if (grid[i][j] == 0) { const unordered_set neighborIds{ getId(grid, i + 1, j), getId(grid, i - 1, j), getId(grid, i, j + 1), getId(grid, i, j - 1)}; maxSize = max(maxSize, 1 + getSize(neighborIds, sizes)); } return maxSize == 0 ? m * n : maxSize; } private: int paint(vector>& grid, int i, int j, int id) { if (i < 0 || i == grid.size() || j < 0 || j == grid.size()) return 0; if (grid[i][j] != 1) return 0; grid[i][j] = id; // grid[i][j] is part of id-th connected component return 1 + paint(grid, i + 1, j, id) + paint(grid, i - 1, j, id) + paint(grid, i, j + 1, id) + paint(grid, i, j - 1, id); } // Get the id of grid[i][j], return 0 if out of bound int getId(const vector>& grid, int i, int j) { if (i < 0 || i == grid.size() || j < 0 || j == grid.size()) return 0; // Invalid return grid[i][j]; } int getSize(const unordered_set& neighborIds, const vector& sizes) { int size = 0; for (const int neighborId : neighborIds) size += sizes[neighborId]; return size; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 class Solution { public int largestIsland(int[][] grid) { final int m = grid.length; final int n = grid.length; int maxSize = 0; // sizes[i] := size of i-th connected component (start from 2) List sizes = new ArrayList<>(Arrays.asList(0, 0)); // For each 1 in the grid, paint all connected 1 with the next available // Color (2, 3, and so on). Also, remember the size of the island we just // Painted with that color. for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) if (grid[i][j] == 1) { sizes.add(paint(grid, i, j, sizes.size())); // Paint 2, 3, ... } for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) if (grid[i][j] == 0) { Set neighborIds = new HashSet<>(Arrays.asList(getId(grid, i - 1, j), getId(grid, i + 1, j), getId(grid, i, j + 1), getId(grid, i, j - 1))); maxSize = Math.max(maxSize, 1 + getSize(grid, neighborIds, sizes)); } return maxSize == 0 ? m * n : maxSize; } private int paint(int[][] grid, int i, int j, int id) { if (i < 0 || i == grid.length || j < 0 || j == grid.length) return 0; if (grid[i][j] != 1) return 0; grid[i][j] = id; // grid[i][j] is part of id-th connected component return 1 + paint(grid, i + 1, j, id) + paint(grid, i - 1, j, id) + paint(grid, i, j + 1, id) + paint(grid, i, j - 1, id); } // Get the id of grid[i][j], return 0 if out of bound private int getId(int[][] grid, int i, int j) { if (i < 0 || i == grid.length || j < 0 || j == grid.length) return 0; // Invalid return grid[i][j]; } private int getSize(int[][] grid, Set neighborIds, List sizes) { int size = 0; for (final int neighborId : neighborIds) size += sizes.get(neighborId); return size; } }