Making A Large Island

LeetCode Q 827 - Making A Large Island

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.

Solution

Solution 1 : Union Find / Disjoint Set

We add one field to the UnionFindSet.
That is int[] area, which used to track the size of each component after the union operation.

Code:

class UnionFindSet {
	
	int[] parent;
	int[] area;

	public UnionFindSet (int size) {
		this.parent = new int[size]; this.area = new int[size];
		for (int i = 0; i < size; i++) 
			parent[i] = i;
	}
	
	public int find (int x) {
		if (parent[x] != x) parent[x] = find(parent[x]);
		return parent[x];
	}
	
	public void union (int x, int y) {
		int px = find(x), py = find(y);
		if (px != py) {
			parent[py] = px;
			area[px] += area[py];
			maxArea = Math.max(maxArea, area[px]); 
		}
	}
}

int maxArea = 1;

private static final int[][] DIRS = new int[][] { { -1, 0 }, { 0, -1 }, { 1, 0 }, { 0, 1 } };

public int largestIsland(int[][] grid) { 

	int R = grid.length, C = grid[0].length;

	UnionFindSet ufs = new UnionFindSet(R * C);

	for (int r = 0; r < R; r++) {
		for (int c = 0; c < C; c++) {
			if (grid[r][c] == 1) {
				// union node and its top and left nodes
				// the other two girds' area are all 0, cuz we haven't visited them.
				for (int i = 0; i < 2; i++) {
					int nr = r + DIRS[i][0];
					int nc = r + DIRS[i][1];
					
					if (nr >= 0 && nc >= 0 && nr < R && nc < C 
						&& grid[nr][nc] == 1) {
						ufs.union(r * C + c, nr * C + nc);
					}
				}
			}
		}
	}

	for (int r = 0; r < R; r++) {
		for (int c = 0; c < C; c++) {
			if (grid[r][c] == 0) {

				int curr = i * C + j;
				ufs.area[curr] = 1;
				// Use set to record neighbors' father to avoid adding area repeatedly
				Set<Integer> neighs = new HashSet<>();
				
				for (int i = 0; i < 4; i++) {
					int nr = r + DIRS[i][0];
					int nc = r + DIRS[i][1];
					
					if (nr < 0 || nc < 0 || nr == R || nc == C 
						|| grid[nr][nc] == 0) continue;
					
					int np = ufs.find(nr * C + nc);
					if (neighs.add(np)) 
						ufs.area[curr] += ufs.area[np];
				}

				maxArea = Math.max(maxArea, ufs.area[curr]);
			}
		}
	}
	
	return maxArea;
}

Solution 2 : DFS

Whe mark island.

• Give each island different name and calculate the area of each island.
• Try each point grid[i][j] == 0 to see which island this point connects to.

Code:

Set<String> set = new HashSet<>();
int res = 0;
 
public int largestIsland(int[][] grid) {
	
	Map<String,String> map = new HashMap<>();
	int m = grid.length, index = 0;
	boolean[][] visited = new boolean[m][m];
	
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < m; j++) {
			if (grid[i][j] == 1 && !visited[i][j]) {
				dfs(grid,visited,i,j);
				
				for (String s : set) map.put(s,res + "+" + index);
				
				res = 0; set.clear(); index++;
			} 
		}
	}
	
	int max = 0;
	int[][] neibor = new int[][] { { -1, 0 }, { 0, -1 }, { 1, 0 }, { 0, 1 } };
	
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < m; j++) {
			if (grid[i][j] == 0) {
				
				int tempvalue = 1;
				set.clear();
				
				for (int k = 0; k < 4; k++) {
					int row = i + neibor[k][0];
					int col = j + neibor[k][1];
					
					if (row >=0 && row < m && col >= 0 && col < m 
						&& grid[row][col] == 1) {
						String value = map.get(row + "+" + col);
						
						String[] strs = value.split("\\+");
						
						if (set.add(strs[1])) 
							tempvalue += Integer.parseInt(strs[0]); 
					}
				}
				max = Math.max(max,tempvalue);
			}
		}
	}
	
	return max == 0 ? m * m : max;
}

public void dfs(int[][] grid, boolean[][] visited, int r, int c) {
	
	visited[r][c] = true;
	int m = grid.length;
	
	set.add(r + "+" + c);
	res++;
	
	int[][] neibor = new int[][] { { -1, 0 }, { 0, -1 }, { 1, 0 }, { 0, 1 } };
	
	for (int i = 0; i < 4; i++) {
		int nr = r + neibor[i][0];
		int nc = c + neibor[i][1];
		if (nr >=0 && nr < m && nc >= 0 && nc < m 
			&& grid[nr][nc] == 1 && !visited[nr][nc]) 
			dfs(grid, visited, nr, nc);
	}
}