827. Making A Large Island
https://leetcode.com/problems/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.
---
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution { | |
| public int largestIsland(int[][] grid) { | |
| // Start at 1, since it is being used a visited, we cannot start at 0 | |
| int island = 1; | |
| Map<Integer, Integer> map = new HashMap<Integer, Integer>(); | |
| int zeros = 0; | |
| for (int r = 0; r < grid.length; r++) { | |
| for (int c = 0; c < grid[0].length; c++) { | |
| if (grid[r][c] == 1) { | |
| grid[r][c] = ++island; | |
| int size = dfs(grid, r, c, island); | |
| map.put(island, size); | |
| } else if (grid[r][c] == 0) { | |
| // Explicit check for zero, since island will be set to 2, 3, 4 ... | |
| zeros++; | |
| } | |
| } | |
| } | |
| // If no zeros are detected, then return size of grid | |
| if (zeros == 0) { | |
| return grid.length * grid[0].length; | |
| } | |
| int[][] dirs = new int[][] {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; | |
| int ans = 1; | |
| for (int r = 0; r < grid.length; r++) { | |
| for (int c = 0; c < grid[0].length; c++) { | |
| if (grid[r][c] == 0) { | |
| Set<Integer> seen = new HashSet<Integer>(); | |
| int total = 0; | |
| for (int[] d : dirs) { | |
| int nr = r + d[0]; | |
| int nc = c + d[1]; | |
| if (isIsland(nr, nc, grid) && !seen.contains(grid[nr][nc])) { | |
| seen.add(grid[nr][nc]); | |
| total += map.get(grid[nr][nc]); | |
| } | |
| } | |
| ans = Math.max(ans, total + 1); | |
| } | |
| } | |
| } | |
| return ans; | |
| } | |
| private int dfs(int[][] grid, int r, int c, int island) { | |
| int[][] dirs = new int[][] {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; | |
| int ans = 1; | |
| for (int[] d : dirs) { | |
| int nr = r + d[0]; | |
| int nc = c + d[1]; | |
| if (isValid(nr, nc, grid)) { | |
| grid[nr][nc] = island; | |
| ans += dfs(grid, nr, nc, island); | |
| } | |
| } | |
| return ans; | |
| } | |
| private boolean isValid(int nr, int nc, int[][] grid) { | |
| return nr >= 0 && nc >= 0 && nr < grid.length && nc < grid[0].length && grid[nr][nc] == 1; | |
| } | |
| private boolean isIsland(int nr, int nc, int[][] grid) { | |
| return nr >= 0 && nc >= 0 && nr < grid.length && nc < grid[0].length && grid[nr][nc] > 0; | |
| } | |
| } |
