Welcome to Subscribe On Youtube

Question

Formatted question description: https://leetcode.ca/all/305.html

305. Number of Islands II

Level

Hard

Description

A 2d grid map of m rows and n columns is initially filled with water. We may perform an addLand operation which turns the water at position (row, col) into a land. Given a list of positions to operate, count the number of islands after each addLand operation. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example:

Input: m = 3, n = 3, positions = [[0,0], [0,1], [1,2], [2,1]]

Output: [1,1,2,3]

Explanation:

Initially, the 2d grid grid is filled with water. (Assume 0 represents water and 1 represents land).

0 0 0
0 0 0
0 0 0

Operation #1: addLand(0, 0) turns the water at grid[0][0] into a land.

1 0 0
0 0 0   Number of islands = 1
0 0 0

Operation #2: addLand(0, 1) turns the water at grid[0][1] into a land.

1 1 0
0 0 0   Number of islands = 1
0 0 0

Operation #3: addLand(1, 2) turns the water at grid[1][2] into a land.

1 1 0
0 0 1   Number of islands = 2
0 0 0

Operation #4: addLand(2, 1) turns the water at grid[2][1] into a land.

1 1 0
0 0 1   Number of islands = 3
0 1 0

Follow up:

Can you do it in time complexity O(k log mn), where k is the length of the positions?

Algorithm

Union Find.

1 . Native UF

p = list(range(n))

def find(x):
    if p[x] != x:
        p[x] = find(p[x])
    return p[x]

# union
p[find(a)] = find(b)

2 . UF with size

p = list(range(n))
size = [1] * n

def find(x):
    if p[x] != x:
        p[x] = find(p[x])
    return p[x]

if find(a) != find(b):
    size[find(b)] += size[find(a)]
    p[find(a)] = find(b)

3 . UF with distance to root

p = list(range(n))
d = [0] * n

def find(x):
    if p[x] != x:
        t = find(p[x])
        d[x] += d[p[x]]
        p[x] = t
    return p[x]

p[find(a)] = find(b)
d[find(a)] = distance

Algorithm - 2 - BFS

Each time a position is visited, first check whether the position is already a land cell.

  • If so, add the current number of islands to the result list, and continue with the next position.
  • Otherwise, check whether the position is adjacent to at least one land cell.
    • If there is no adjacent land cell, then a new island is added, so add a greater island number to the result list, and update the new land cell with a new island number.
    • Otherwise, find the minimum island number that is adjacent to the new land cell, do breadth first search on all cells adjacent to the new land cell, and update all reachable cells with the smallest island number. The number of islands may remain unchanged or decrease, and add the updated number of islands to the result list.

Finally, return the result list.

Code

  • import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.List;
    
    public class Number_of_Islands_II {
    
        int[][] dirs = { {0, 1}, {1, 0}, {-1, 0}, {0, -1} };
    
        public List<Integer> numIslands2(int m, int n, int[][] positions) {
            List<Integer> result = new ArrayList<>();
            if(m <= 0 || n <= 0) {
                return result;
            }
    
            int count = 0;                      // number of islands
    
            // roots[c] = p means the parent of node c is p
            int[] roots = new int[m * n];       // one island = one tree
    
            Arrays.fill(roots, -1);
    
            for(int[] p : positions) {
                int root = n * p[0] + p[1];     // assume new point is isolated island
                roots[root] = root;             // add new island
                count++;
    
                for(int[] dir : dirs) { // probe 4 directions
                    int x = p[0] + dir[0];
                    int y = p[1] + dir[1];
                    int nb = n * x + y;
                    if(x < 0 || x >= m || y < 0 || y >= n || roots[nb] == -1) {
                        continue;
                    }
    
                    int rootNb = findIsland(roots, nb);
                    if(root != rootNb) {        // if neighbor is in another island
                        roots[root] = rootNb;   // union two islands
                        root = rootNb;          // current tree root = joined tree root
                        count--;
                    }
                }
    
                result.add(count);
            }
    
            return result;
        }
    
        public int findIsland(int[] roots, int id) {
            while(id != roots[id]) {
                id = roots[id];
            }
            return id;
        }
    }
    
    
    // BFS
    class Solution {
        Set<Integer> set = new HashSet<Integer>();
    
        public List<Integer> numIslands2(int m, int n, int[][] positions) {
            int[][] grid = new int[m][n];
            int[][] directions = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
            int length = positions.length;
            List<Integer> islands = new ArrayList<Integer>();
            int islandsCount = 0;
            for (int i = 0; i < length; i++) {
                int[] position = positions[i];
                int row = position[0], column = position[1];
                if (grid[row][column] != 0) {
                    islands.add(set.size());
                    continue;
                }
                int minAdjacent = Integer.MAX_VALUE;
                for (int[] direction : directions) {
                    int newRow = row + direction[0], newColumn = column + direction[1];
                    if (newRow >= 0 && newRow < m && newColumn >= 0 && newColumn < n && grid[newRow][newColumn] != 0)
                        minAdjacent = Math.min(minAdjacent, grid[newRow][newColumn]);
                }
                if (minAdjacent == Integer.MAX_VALUE) {
                    set.add(islandsCount + 1);
                    islandsCount++;
                    grid[row][column] = islandsCount;
                } else {
                    grid[row][column] = minAdjacent;
                    breadthFirstSearch(grid, row, column);
                }
                islands.add(set.size());
            }
            return islands;
        }
    
        public void breadthFirstSearch(int[][] grid, int row, int column) {
            int m = grid.length, n = grid[0].length;
            int curNumber = grid[row][column];
            int[][] directions = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
            Queue<int[]> queue = new LinkedList<int[]>();
            queue.offer(new int[]{row, column});
            while (!queue.isEmpty()) {
                int[] square = queue.poll();
                int curRow = square[0], curColumn = square[1];
                for (int[] direction : directions) {
                    int newRow = curRow + direction[0], newColumn = curColumn + direction[1];
                    if (newRow >= 0 && newRow < m && newColumn >= 0 && newColumn < n) {
                        int prevNumber = grid[newRow][newColumn];
                        if (prevNumber > curNumber) {
                            grid[newRow][newColumn] = curNumber;
                            set.remove(prevNumber);
                            queue.offer(new int[]{newRow, newColumn});
                        }
                    }
                }
            }
        }
    }
    
    
    ############
    
    class Solution {
        private int[] p;
    
        public List<Integer> numIslands2(int m, int n, int[][] positions) {
            p = new int[m * n];
            for (int i = 0; i < p.length; ++i) {
                p[i] = i;
            }
            int[][] grid = new int[m][n];
            int cnt = 0;
            List<Integer> ans = new ArrayList<>();
            int[] dirs = {-1, 0, 1, 0, -1};
            for (int[] pos : positions) {
                int i = pos[0];
                int j = pos[1];
                if (grid[i][j] == 1) {
                    ans.add(cnt);
                    continue;
                }
                grid[i][j] = 1;
                ++cnt;
                for (int k = 0; k < 4; ++k) {
                    int x = i + dirs[k];
                    int y = j + dirs[k + 1];
                    if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1
                        && find(x * n + y) != find(i * n + j)) {
                        p[find(x * n + y)] = find(i * n + j);
                        --cnt;
                    }
                }
                ans.add(cnt);
            }
            return ans;
        }
    
        private int find(int x) {
            if (p[x] != x) {
                p[x] = find(p[x]);
            }
            return p[x];
        }
    }
    
  • class Solution {
    public:
        vector<int> p;
    
        vector<int> numIslands2(int m, int n, vector<vector<int>>& positions) {
            p.resize(m * n);
            for (int i = 0; i < p.size(); ++i) p[i] = i;
            vector<vector<int>> grid(m, vector<int>(n));
            vector<int> ans;
            int cnt = 0;
            vector<int> dirs = {-1, 0, 1, 0, -1};
            for (auto& pos : positions) {
                int i = pos[0], j = pos[1];
                if (grid[i][j] == 1) {
                    ans.push_back(cnt);
                    continue;
                }
                grid[i][j] = 1;
                ++cnt;
                for (int k = 0; k < 4; ++k) {
                    int x = i + dirs[k], y = j + dirs[k + 1];
                    if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1 && find(x * n + y) != find(i * n + j)) {
                        p[find(x * n + y)] = find(i * n + j);
                        --cnt;
                    }
                }
                ans.push_back(cnt);
            }
            return ans;
        }
    
        int find(int x) {
            if (p[x] != x) p[x] = find(p[x]);
            return p[x];
        }
    };
    
  • class Solution:
        def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:
            def check(i, j):
                return 0 <= i < m and 0 <= j < n and grid[i][j] == 1
    
            def find(x):
                if p[x] != x:
                    p[x] = find(p[x])
                return p[x]
    
            p = list(range(m * n))
            grid = [[0] * n for _ in range(m)]
            res = []
            cur = 0
            for i, j in positions:
                if grid[i][j] == 1: # already counted, same as previous island count
                    res.append(cur)
                    continue
                grid[i][j] = 1
                cur += 1
                for x, y in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                    if check(i + x, j + y) and find(i * n + j) != find((i + x) * n + j + y):
                        p[find(i * n + j)] = find((i + x) * n + j + y)
                        cur -= 1
                        # 1 0 1
                        # 0 1 0
                        # for above, if setting 1st-row 2nd-col 0-to-1
                        # cur will -1 for 3 times
                        # but cur += 1 after grid[i][j] = 1 so cur final result is 1
                res.append(cur)
            return res
    
    ############
    
    class UnionFind(object):
      def __init__(self, m, n):
        self.dad = [i for i in range(m * n)]
        self.rank = [0 for _ in range(m * n)]
    
      def find(self, x):
        if self.dad[x] != x:
          self.dad[x] = self.find(self.dad[x])
        return self.dad[x]
    
      def union(self, xy): # xy is a tuple (x,y), with x and y value inside
        x, y = map(self.find, xy)
        if x == y:
          return False
        if self.rank[x] > self.rank[y]:
          self.dad[y] = x
        elif self.rank[x] < self.rank[y]:
          self.dad[x] = y
        else:
          self.dad[y] = x # search to the left, to find parent
          self.rank[x] += 1 # now x a parent, so +1 its rank
        return True
    
    
    class Solution(object):
      def numIslands2(self, m, n, positions):
        """
        :type m: int
        :type n: int
        :type positions: List[List[int]]
        :rtype: List[int]
        """
        uf = UnionFind(m, n)
        ans = 0
        ret = []
        dirs = [(0, -1), (0, 1), (1, 0), (-1, 0)]
        grid = set()
        for i, j in positions:
          ans += 1
          grid |= {(i, j)}
          for di, dj in dirs:
            ni, nj = i + di, j + dj
            if 0 <= ni < m and 0 <= nj < n and (ni, nj) in grid:
              if uf.union((ni * n + nj, i * n + j)):
                ans -= 1
          ret.append(ans)
        return ret
    
    
  • func numIslands2(m int, n int, positions [][]int) []int {
    	p := make([]int, m*n)
    	for i := 0; i < len(p); i++ {
    		p[i] = i
    	}
    	grid := make([][]int, m)
    	for i := 0; i < m; i++ {
    		grid[i] = make([]int, n)
    	}
    	var find func(x int) int
    	find = func(x int) int {
    		if p[x] != x {
    			p[x] = find(p[x])
    		}
    		return p[x]
    	}
    	var ans []int
    	cnt := 0
    	dirs := []int{-1, 0, 1, 0, -1}
    	for _, pos := range positions {
    		i, j := pos[0], pos[1]
    		if grid[i][j] == 1 {
    			ans = append(ans, cnt)
    			continue
    		}
    		grid[i][j] = 1
    		cnt++
    		for k := 0; k < 4; k++ {
    			x, y := i+dirs[k], j+dirs[k+1]
    			if x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1 && find(x*n+y) != find(i*n+j) {
    				p[find(x*n+y)] = find(i*n + j)
    				cnt--
    			}
    		}
    		ans = append(ans, cnt)
    	}
    	return ans
    }
    

All Problems

All Solutions