Leetcode # 305. Number of Islands II

https://leetcode.com/problems/number-of-islands-ii

Solution

Time Complexity: O(len(positions))
Space Complexity: O(len(positions))
(The input and output generally do not count towards the space complexity.)

class Dsu:
  def __init__(self, roots = None):
    self.root = {}
    if roots:
      for r in roots:
        self.make_set(r)
  def make_set(self, x): 
    self.root[x] = x
  def find(self, x):
    if self.root[x] == x:
      return x
    self.root[x] = self.find(self.root[x])
    return self.root[x]
  def union(self, x, y): 
    x_root = self.find(x) 
    y_root = self.find(y) 
    if x_root != y_root: 
      self.root[x_root] = y_root
  def are_in_same_set(self, x, y):
    return self.find(x) == self.find(y)
  def get_ds(self): # get disjoint sets
    disjoint_sets = collections.defaultdict(set)
    for key in self.root:
      disjoint_sets[self.find(key)].add(key)
    return disjoint_sets
  def has(self, x): 
    return x in self.root
  
class Solution:
  def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:
    dsu = Dsu()
    lands_n = []
    for y, x in positions:
      # For same position appeared
      if dsu.has((x, y)):
        lands_n.append(lands_n[-1])
        continue
      dsu.make_set((x, y))
      neighbor = set()
      if x > 0 and dsu.has((x - 1, y)):
        neighbor.add(dsu.find((x - 1, y)))
        dsu.union((x, y), (x - 1, y))
      if y > 0 and dsu.has((x, y - 1)):
        neighbor.add(dsu.find((x, y - 1)))
        dsu.union((x, y), (x, y - 1))
      if x < n - 1 and dsu.has((x + 1, y)):
        neighbor.add(dsu.find((x + 1, y)))
        dsu.union((x, y), (x + 1, y))
      if y < m - 1 and dsu.has((x, y + 1)):
        neighbor.add(dsu.find((x, y + 1)))
        dsu.union((x, y), (x, y + 1))
      cur_lands_n = ((lands_n[-1] + 1) if lands_n else 1) - len(neighbor)
      lands_n.append(cur_lands_n)
    return lands_n

❌ 須注意的地方

• m, n 兩個變數名已經被題目使用掉了
• 沒有額外的記憶體讓我們存放 grid (land & water)
  所以 Dsu 增加了 has() 讓我們可以確認新的 position 是否已存在
• 如果要透過 dsu.get_ds() 取得每一次新增土地後島的總數
  會花費過多時間導致 Time Limit Exceeded

  所以改為計算新增土地之後島的總數增減變化

Last Updated on 2023/08/16 by A1go