Advertisement
Guest User

Grokking Newsletter 203

a guest
Dec 29th, 2021
53
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution {
  2.  
  3. static final int NO_COLOR = 0;
  4.  
  5. int n;
  6. int[][] grid;
  7.  
  8. int[][] color;
  9. Map<Integer, Integer> islandSizes;
  10.  
  11. int[][] dirs = {
  12. { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 }
  13. };
  14.  
  15. public int largestIsland(int[][] grid) {
  16.  
  17. // setup
  18. this.n = grid.length;
  19. this.grid = grid;
  20.  
  21. color = new int[n][n];
  22. islandSizes = new HashMap<>();
  23.  
  24. int maxArea = 0;
  25.  
  26. // find area and coloring
  27. int colorId = 1;
  28.  
  29. for (int r = 0; r < n; r++) {
  30. for (int c = 0; c < n; c++) {
  31.  
  32. if (grid[r][c] == 1 && color[r][c] == NO_COLOR) {
  33.  
  34. int area = getMaxAreaAndColoring(r, c, colorId);
  35. islandSizes.put(colorId, area);
  36. colorId++;
  37.  
  38. // record max area
  39. maxArea = Math.max(maxArea, area);
  40. }
  41. }
  42. }
  43.  
  44. // find largest island can be created by changing one 0 cell to 1
  45. for (int r = 0; r < n; r++) {
  46. for (int c = 0; c < n; c++) {
  47.  
  48. if (grid[r][c] == 0) {
  49. int area = getMaxAreaOfIslandCanMake(r, c);
  50. maxArea = Math.max(maxArea, area);
  51. }
  52. }
  53. }
  54.  
  55. return maxArea;
  56. }
  57.  
  58. int getMaxAreaAndColoring(int row, int col, int colorId) {
  59.  
  60. Queue<int[]> queue = new LinkedList<>();
  61. queue.offer(new int[] { row, col });
  62.  
  63. color[row][col] = colorId;
  64.  
  65. int area = 0;
  66. while (!queue.isEmpty()) {
  67. int[] at = queue.poll();
  68. int r = at[0];
  69. int c = at[1];
  70.  
  71. area++;
  72.  
  73. for (int[] neighbor : getNeighbors(r, c)) {
  74. int rr = neighbor[0];
  75. int cc = neighbor[1];
  76.  
  77. if (grid[rr][cc] == 1 && color[rr][cc] == NO_COLOR) {
  78. color[rr][cc] = colorId;
  79.  
  80. queue.offer(new int[] { rr, cc });
  81. }
  82. }
  83. }
  84.  
  85. return area;
  86. }
  87.  
  88. int getMaxAreaOfIslandCanMake(int row, int col) {
  89.  
  90. int area = 1;
  91. Set<Integer> seenIds = new HashSet<>();
  92.  
  93. for (int[] neighbor : getNeighbors(row, col)) {
  94. int rr = neighbor[0];
  95. int cc = neighbor[1];
  96.  
  97. int colorId = color[rr][cc];
  98.  
  99. if (colorId != NO_COLOR) {
  100. if (!seenIds.contains(colorId)) {
  101. area += islandSizes.get(colorId);
  102. }
  103.  
  104. seenIds.add(colorId);
  105. }
  106. }
  107.  
  108. return area;
  109. }
  110.  
  111. List<int[]> getNeighbors(int row, int col) {
  112.  
  113. List<int[]> ans = new ArrayList<>();
  114.  
  115. for (int[] dir : dirs) {
  116. int rr = row + dir[0];
  117. int cc = col + dir[1];
  118.  
  119. if (0 <= rr && rr < n && 0 <= cc && cc < n) {
  120. ans.add(new int[] { rr, cc });
  121. }
  122. }
  123.  
  124. return ans;
  125. }
  126. }
Advertisement
RAW Paste Data Copied
Advertisement