LeetCode [827] Making A Large Island

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.

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

class Solution { int m, n; Map<Integer, Integer> map; int[][] dirs = new int[][]{{-1,0},{1,0},{0,-1},{0,1}}; int max = 0; public int largestIsland(int[][] grid) { m = grid.length; n = grid[0].length; map = new HashMap<>(); int index = 2; for(int i=0; i<m; ++i){ for(int j=0; j<n; ++j){ if(grid[i][j]!=1) continue; int[] area = new int[1]; helper(i, j, grid, index, area); map.put(index, area[0]); max = Math.max(area[0], max); index++; } } for(int i=0; i<m; ++i){ for(int j=0; j<n; ++j){ if(grid[i][j]!=0) continue; Set<Integer> merged = new HashSet<>(); for(int[] d : dirs){ int ni = i+d[0], nj =j+d[1]; if(ni>=0 && ni<m && nj>=0 && nj<n && grid[ni][nj]!=0){ merged.add(grid[ni][nj]); } } int area = 1; for(int ind : merged){ area += map.get(ind); } max = Math.max(max, area); } } return max; } void helper(int i, int j, int[][] grid, int index, int[] area){ grid[i][j] = index; area[0]++; for(int[] d : dirs){ int ni = i+d[0], nj = j+d[1]; if(ni>=0 && ni<m && nj>=0 && nj<n && grid[ni][nj]==1){ helper(ni, nj, grid, index, area); } } } }