LeetCode 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


As in the previous solution, we check every 0. However, we also store the size of each group, so that we do not have to use depth-first search to repeatedly calculate the same size.
However, this idea fails when the 0 touches the same group. For example, consider grid = [[0,1],[1,1]]. The answer is 4, not 1 + 3 + 3, since the right neighbor and the bottom neighbor of the 0belong to the same group.
We can remedy this problem by keeping track of a group id (or index), that is unique for each group. Then, we'll only add areas of neighboring groups with different ids.
Algorithm
For each group, fill it with value index and remember it's size as area[index] = dfs(...).
Then for each 0, look at the neighboring group ids seen and add the area of those groups, plus 1 for the 0 we are toggling. This gives us a candidate answer, and we take the maximum.
To solve the issue of having potentially no 0, we take the maximum of the previously calculated areas.
  • Time Complexity: O(N^2), where N is the length and width of the grid.
  int[] dr = new int[] { -1, 0, 1, 0 };
  int[] dc = new int[] { 0, -1, 0, 1 };
  int[][] grid;
  int N;

  public int largestIsland(int[][] grid) {
    this.grid = grid;
    N = grid.length;

    int index = 2;
    int[] area = new int[N * N + 2];
    for (int r = 0; r < N; ++r)
      for (int c = 0; c < N; ++c)
        if (grid[r][c] == 1)
          area[index] = dfs(r, c, index++);

    int ans = 0;
    for (int x : area)
      ans = Math.max(ans, x);
    for (int r = 0; r < N; ++r)
      for (int c = 0; c < N; ++c)
        if (grid[r][c] == 0) {
          Set<Integer> seen = new HashSet();
          for (Integer move : neighbors(r, c))
            if (grid[move / N][move % N] > 1)
              seen.add(grid[move / N][move % N]);

          int bns = 1;
          for (int i : seen)
            bns += area[i];
          ans = Math.max(ans, bns);
        }

    return ans;
  }

  public int dfs(int r, int c, int index) {
    int ans = 1;
    grid[r][c] = index;
    for (Integer move : neighbors(r, c)) {
      if (grid[move / N][move % N] == 1) {
        grid[move / N][move % N] = index;
        ans += dfs(move / N, move % N, index);
      }
    }

    return ans;
  }

  public List<Integer> neighbors(int r, int c) {
    List<Integer> ans = new ArrayList();
    for (int k = 0; k < 4; ++k) {
      int nr = r + dr[k];
      int nc = c + dc[k];
      if (0 <= nr && nr < N && 0 <= nc && nc < N)
        ans.add(nr * N + nc);
    }

    return ans;

  }


X.
https://leetcode.com/problems/making-a-large-island/discuss/126960/Extremely-Simple-Concept-Using-Marker
Mark all the Connected Components in the grid using a distinct Integer marker.
Keep the count of the marker in the grid using a HashMap.
For each zero check the distinct islands that get connected.
ex:
101
000
011
using Marker
Grid :
203
000
044
Map :
2 : 1
3 : 1
4 : 2
Now for each zero, check the distinct marker it connects.
The zero in the 2nd row last column connects marker 3 and 4.


Hence the counts becomes maximum = 2 (count of 4) + 1 (count of 3) + 1(The zero that is converted to 1).
https://leetcode.com/problems/making-a-large-island/discuss/127015/C%2B%2B-O(n*m)-15-ms-colorful-islands
https://leetcode.com/problems/making-a-large-island/discuss/127032/C%2B%2BJavaPython-Straight-Forward-O(N2)-with-Explanations
For each 1 in the grid, we paint all connected 1 with the next available color (2, 3, and so on). We also remember the size of the island we just painted with that color.


Then, we analyze all 0 in the grid, and sum sizes of connected islands (based on the island color). Note that the same island can connect to 0 more than once. The example below demonstrates this idea (the answer is highlighted):
    public int largestIsland(int[][] grid) {
        Map<Integer, Integer> map = new HashMap<>(); //Key: color, Val: size of island painted of that color
        map.put(0, 0); //We won't paint island 0, hence make its size 0, we will use this value later   
        int n = grid.length; 
        int colorIndex = 2; //0 and 1 is already used in grid, hence we start colorIndex from 2 
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    int size = paint(grid, i, j, colorIndex);
                    map.put(colorIndex, size);
                    colorIndex++;
                }
            }
        }
    
        //If there is no island 0 from grid, res should be the size of islands of first color
        //If there is no island 1 from grid, res should be 0 
        int res = map.getOrDefault(2, 0); 
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 0) {
                    //We use a set to avoid repeatly adding islands with the same color
                    Set<Integer> set = new HashSet<>();
                    //If current island is at the boundary, we add 0 to the set, whose value is 0 in the map
                    set.add(i > 0 ? grid[i - 1][j] : 0);
                    set.add(i < n - 1 ? grid[i + 1][j] : 0);
                    set.add(j > 0 ? grid[i][j - 1] : 0);
                    set.add(j < n - 1 ? grid[i][j + 1] : 0);
                    
                    int newSize = 1; //We need to count current island as well, hence we init newSize with 1
                    for (int color : set) newSize += map.get(color);
                    res = Math.max(res, newSize);
                }
            }
        }
        return res;
    }
    
    //Helper method to paint current island and all its connected neighbors
    //Return the size of all painted islands at the end
    private int paint(int[][] grid, int i, int j, int color) {
        if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] != 1) return 0;
        grid[i][j] = color;
        return 1 + paint(grid, i + 1, j, color) + paint(grid, i - 1, j, color) + paint(grid, i, j + 1, color) + paint(grid, i, j - 1, color);
    }
X. Union Find
https://leetcode.com/problems/making-a-large-island/discuss/157446/JAVA-UnoinFind-O(mn)
class UnionFind {
    
    private int[] id;
    private int[] size;
    
    public UnionFind(int[][] grid) {
        
        int m = grid.length, n = grid[0].length;
        this.id = new int[m * n];
        this.size = new int[m * n];
        
        for (int i = 0; i < m * n; i++) {
            id[i] = i;
            size[i] = 1;
        }
    }
    
    private int find(int i) {
    
        while (id[i] != i) {
            i = id[i];
            id[i] = id[id[i]];
        }

        return i;
    }

    private boolean isConnected(int p, int q) {

        return find(p) == find(q);
    }

    private void union(int p, int q) {

        int rp = find(p), rq = find(q);
        if (rp == rq)
            return;
        else if (size[rp] > size[rq]) {
            id[rq] = rp;
            size[rp] += size[rq];
        } else {
            id[rp] = rq;
            size[rq] += size[rp];
        }
    }
}

private UnionFind uf;
private int[][] dirs = new int[][] {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

public int largestIsland(int[][] grid) {
    
    int m = grid.length, n = grid[0].length;
    int max = Integer.MIN_VALUE;
    uf = new UnionFind(grid);
    
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 0)
                continue;
            for (int[] dir : dirs) {
                int ni = i + dir[0];
                int nj = j + dir[1];
                if (ni < 0 || nj < 0 || ni >= m || nj >= n || grid[ni][nj] == 0)
                    continue;
                if (!uf.isConnected(i * n + j, ni * n + nj)) {
                    uf.union(i * n + j, ni * n + nj);
                }
            }
        }
    }
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 1) {
                int root = uf.find(i * n + j);
                max = Math.max(max, uf.size[root]);
            } else {
                Set<Integer> visited = new HashSet<>();
                int sum = 1;
                for (int[] dir : dirs) {
                    int ni = i + dir[0];
                    int nj = j + dir[1];
                    if (ni < 0 || nj < 0 || ni >= m || nj >= n || grid[ni][nj] == 0)
                        continue;
                    int root = uf.find(ni * n + nj);
                    if (visited.add(root)) {
                        sum += uf.size[root];
                    }
                }
                max = Math.max(max, sum);
            }
        }
    }
    
    return max;
}

X. https://leetcode.com/problems/making-a-large-island/discuss/127256/DFS-JAVA-AC-CONCISE-SOLUTION
For each 0, change it to a 1, then do a depth first search to find the size of that component. The answer is the maximum size component found.
Of course, if there is no 0 in the grid, then the answer is the size of the whole grid.
  • Time Complexity: O(N^4), where N is the length and width of the grid.
  • Space Complexity: O(N^2), the additional space used in the depth first search by stack and seen.

  int[] dr = new int[] { -1, 0, 1, 0 };
  int[] dc = new int[] { 0, -1, 0, 1 };

  public int largestIsland(int[][] grid) {
    int N = grid.length;

    int ans = 0;
    boolean hasZero = false;
    for (int r = 0; r < N; ++r)
      for (int c = 0; c < N; ++c)
        if (grid[r][c] == 0) {
          hasZero = true;
          grid[r][c] = 1;
          ans = Math.max(ans, check(grid, r, c));
          grid[r][c] = 0;
        }

    return hasZero ? ans : N * N;
  }

  public int check(int[][] grid, int r0, int c0) {
    int N = grid.length;
    Stack<Integer> stack = new Stack();
    Set<Integer> seen = new HashSet();
    stack.push(r0 * N + c0);
    seen.add(r0 * N + c0);

    while (!stack.isEmpty()) {
      int code = stack.pop();
      int r = code / N, c = code % N;
      for (int k = 0; k < 4; ++k) {
        int nr = r + dr[k], nc = c + dc[k];
        if (!seen.contains(nr * N + nc) && 0 <= nr && nr < N && 0 <= nc && nc < N && grid[nr][nc] == 1) {
          stack.push(nr * N + nc);
          seen.add(nr * N + nc);
        }
      }
    }

    return seen.size();

  }

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts