LeetCode 305 Number of Islands II

LeetCode 305 Number of Islands II Problem

Download Code
class Solution(object):
    def numIslands2(self, m, n, positions):
        :type m: int
        :type n: int
        :type positions: List[List[int]]
        :rtype: List[int]
        # quick union find with weights
        ans = []
        islands = Union()
        for p in map(tuple, positions):
            for dp in (0, 1), (0, -1), (1, 0), (-1, 0):
                q = (p[0] + dp[0], p[1] + dp[1])
                if q in islands.id:
                    islands.unite(p, q)
            ans += [islands.count]
        return ans

class Union(object):
    quick union find with weights
    def __init__(self):
        # use dic to reduce index operations
        self.id = {}
        self.sz = {}
        self.count = 0

    def add(self, p):
        self.id[p] = p
        self.sz[p] = 1
        self.count += 1

    def root(self, i):
        while i != self.id[i]:
            self.id[i] = self.id[self.id[i]]
            i = self.id[i]
        return i

    def unite(self, p, q):
        i, j = self.root(p), self.root(q)
        if i == j:
        if self.sz[i] > self.sz[j]:
            i, j = j, i
        self.id[i] = j
        self.sz[j] += self.sz[i]
        self.count -= 1
Download Number of Islands II.py

List of all Number of Islands II problems

Leetcode 305 Number of Islands II problem solution in python3 with explanation. This is the best place to expand your knowledge and get prepared for your next interview.

Feedback is the most important part of any website.

If you have any query, suggestion or feedback, Please feel free to contact us.