990. Satisfiability of Equality Equations Medium

990. Satisfiability of Equality Equations Medium

You are given an array of strings equations that represent relationships between variables where each string equations[i] is of length 4 and takes one of two different forms: “xi==yi” or “xi!=yi”.Here, xi and yi are lowercase letters (not necessarily different) that represent one-letter variable names.

Return true if it is possible to assign integers to variable names so as to satisfy all the given equations, or false otherwise.

Two pass, one pass union the equality. Second pass check inequality violations.

class UnionFind:
    def __init__(self, n=26):
        self.parents = list(range(n))

    def find(self, i):
        while i != self.parents[i]:
            self.parents[i] = self.find(self.parents[i])  
            i = self.parents[i]
        return i

    def union(self, p, q):
        root_p, root_q = self.find(p), self.find(q)
        if root_p == root_q: 
            return False
        self.parents[root_p] = root_q
        return True

class Solution:
    def equationsPossible(self, equations: List[str]) -> bool:
        uf = UnionFind(26 + 1)
        
        for eq in equations:
            if eq[1] == "!": 
                continue
            a, b = map(lambda x: ord(x) - ord("a"), [eq[0], eq[~0]])
            uf.union(a, b)

        for eq in equations:
            if eq[1] == "=": 
                continue
            a, b = map(lambda x: ord(x) - ord("a"), [eq[0], eq[~0]])
            if uf.find(a) == uf.find(b): 
                return False
            
        return True

803. Bricks Falling When Hit Hard

You are given an m x n binary grid, where each 1 represents a brick and 0 represents an empty space. A brick is stable if:

1. It is directly connected to the top of the grid, or
2. At least one other brick in its four adjacent cells is stable.

You are also given an array hits, which is a sequence of erasures we want to apply. Each time we want to erase the brick at the location hits[i] = (rowi, coli). The brick on that location (if it exists) will disappear. Some other bricks may no longer be stable because of that erasure and will fall. Once a brick falls, it is immediately erased from the grid (i.e., it does not land on other stable bricks).

Return an array result, where each result[i] is the number of bricks that will fall after the ith erasure is applied.

Note that an erasure may refer to a location with no brick, and if it does, no bricks drop.

Work backwards, add brick to see if the size of the connected components liked to ceiling is increased in size or not.

class UnionFind:
    def __init__(self, n):
        self.parents = list(range(n + 1))
        self.sizes = [1] * (n + 1)

    def find(self, i):
        while i != self.parents[i]:
            self.parents[i] = self.find(self.parents[i])  
            i = self.parents[i]
        return i

    def union(self, p, q):
        root_p, root_q = map(self.find, (p, q))
        if root_p == root_q: return False
        small, big = sorted([root_p, root_q], key=lambda x: self.sizes[x])
        self.parents[small] = big
        self.sizes[big] += self.sizes[small]    
        return True
    
    def size(self, i):
        return self.sizes[self.find(i)]


class Solution:
    def hitBricks(self, grid: List[List[int]], hits: List[List[int]]) -> List[int]:
        nrow, ncol = len(grid), len(grid[1])
        uf = UnionFind(nrow * ncol)

        def neighbors(r, c):
            for nr, nc in ((r-1,c), (r+1,c), (r,c-1), (r,c+1)):
                if 0 <= nr < nrow and 0 <= nc < ncol:
                    yield nr, nc
        
        def to_index(r, c):
            return r * ncol + c
        
        ceiling = nrow * ncol
        
        # from reverse
        g = [row.copy() for row in grid]
        for r, c in hits:
            g[r][c] = 0
    
        for r in range(nrow):
            for c in range(ncol):
                if g[r][c] == 0: continue
                if r == 0:
                    uf.union(to_index(r,c), ceiling)
                if r and g[r-1][c]:
                    uf.union(to_index(r,c), to_index(r-1,c))
                if c and g[r][c-1]:
                    uf.union(to_index(r,c), to_index(r,c-1))
        
        dropped = []
        for r, c in reversed(hits):
            if grid[r][c] == 0:
                dropped.append(0)
                continue
                
            num_stable = uf.size(ceiling)
            for nr, nc in neighbors(r, c):
                if g[nr][nc]:
                    uf.union(to_index(r,c), to_index(nr,nc))
                    
            if r == 0:
                uf.union(to_index(r,c), ceiling)
            g[r][c] = 1
            now_stable = uf.size(ceiling)

            if now_stable > num_stable:
                dropped.append(now_stable - num_stable -1)
            else:
                dropped.append(0)
        return list(reversed(dropped))

200. Number of Islands Medium

Given an m x n 2D binary grid grid which represents a map of ‘1’s (land) and ‘0’s (water), return the number of islands.

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.

Set num_islands to be number of lands initially. Iterate over lands and union find, decrement the num_islands when union two islands into one.

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        nrow, ncol = len(grid), len(grid[0])
        parents = list(range(nrow * ncol))
        self.n = 0
        
        def to_idx(r, c):
            return r * ncol + c
        
        def find(i):
            while i != parents[i]:
                parents[i] = find(parents[i])
                i = parents[i]
            return i
        
        def union(i, j):
            pi, pj = find(i), find(j)
            if pi == pj:
                return False
            parents[pi] = pj
            self.n -=1
            return True
        
        def neighbors(r, c):
            for nr, nc in ((r-1,c),(r+1,c),(r,c-1),(r,c+1)):
                if 0 <= nr < nrow and 0 <= nc < ncol and grid[nr][nc] == "1":
                    yield nr, nc
        
        for r in range(nrow):
            for c in range(ncol):
                if grid[r][c] == "0":
                    continue
                self.n += 1
                for nr, nc in neighbors(r, c):
                    union(to_idx(r, c), to_idx(nr, nc))
                    
        return self.n

305. Number of Islands II Hard

You are given an empty 2D binary grid grid of size m x n. The grid represents a map where 0’s represent water and 1’s represent land. Initially, all the cells of grid are water cells (i.e., all the cells are 0’s).

We may perform an add land operation which turns the water at position into a land. You are given an array positions where positions[i] = [ri, ci] is the position (ri, ci) at which we should operate the ith operation.

Return an array of integers answer where answer[i] is the number of islands after turning the cell (ri, ci) into a land. You 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.

class UnionFind(object):
    def __init__(self):
        self.parents = dict()
        self.sizes = dict()
        self.n = 0

    def __contains__(self, key):
        return key in self.parents
        
    def insert(self, r, c):
        if self.__contains__((r,c)): return
        self.parents[(r, c)] = (r, c)
        self.sizes[(r, c)] = 1
        self.n += 1
        
    def find(self, i):
        while i != self.parents[i]:
            self.parents[i] = self.find(self.parents[i])  
            i = self.parents[i]
        return i

    def union(self, p, q):
        root_p, root_q = map(self.find, (p, q))
        if root_p == root_q: return
        small, big = sorted([root_p, root_q], key=lambda x: self.sizes[x])
        self.parents[small] = big
        self.sizes[big] += self.sizes[small] 
        self.n -= 1

class Solution:
    def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:
        uf = UnionFind()
        num_islands = []
        for r, c in positions:
            uf.insert(r, c)
            for rr, cc in [(r-1,c), (r+1,c), (r,c-1), (r,c+1)]:
                if (rr, cc) not in uf: continue
                uf.union((r,c), (rr,cc))
            num_islands.append(uf.n)
        return num_islands     

778. Swim in Rising Water Hard

You are given an n x n integer matrix grid where each value grid[i][j] represents the elevation at that point (i, j).

The rain starts to fall. At time t, the depth of the water everywhere is t. You can swim from a square to another 4-directionally adjacent square if and only if the elevation of both squares individually are at most t. You can swim infinite distances in zero time. Of course, you must stay within the boundaries of the grid during your swim.

Return the least time until you can reach the bottom right square (n - 1, n - 1) if you start at the top left square (0, 0).

Iterate over time, union lands as they appear. Check when topleft and bottom right are in the same component.

class UnionFind:
    def __init__(self):
        self.parents = dict()
        self.sizes = dict()
        
    def __contains__(self, i):
        return i in self.parents
    
    def insert(self, i):
        if self.__contains__(i): return
        self.parents[i] = i
        self.sizes[i] = 1
        
    def find(self, i):
        while i != self.parents[i]:
            self.parents[i] = self.find(self.parents[i])  
            i = self.parents[i]
        return i

    def union(self, p, q):
        root_p, root_q = map(self.find, (p, q))
        if root_p == root_q: return
        small, big = sorted([root_p, root_q], key=lambda x: self.sizes[x])
        self.parents[small] = big
        self.sizes[big] += self.sizes[small]    

class Solution:
    def swimInWater(self, grid: List[List[int]]) -> int:
        n = len(grid)
        t_to_loc = {grid[r][c]: (r,c) for r in range(n) for c in range(n)}
        uf = UnionFind()
        for t in range(n**2):
            r, c = t_to_loc[t]
            uf.insert((r,c))
            for rr, cc in [(r-1,c),(r+1,c),(r,c-1),(r,c+1)]:
                if (rr, cc) not in uf: continue
                uf.union((r,c), (rr,cc))
            if (0,0) in uf and (n-1,n-1) in uf and uf.find((0,0)) == uf.find((n-1,n-1)):
                return t

1254. Number of Closed Islands Medium

Given a 2D grid consists of 0s (land) and 1s (water). An island is a maximal 4-directionally connected group of 0s and a closed island is an island totally (all left, top, right, bottom) surrounded by 1s.

Return the number of closed islands.

Find all islands, union islands on the edge to the sea. check number of islands not in the sea.

class UnionFind:
    def __init__(self):
        self.parents = dict()
        self.sizes = dict()
        
    def __contains__(self, i):
        return i in self.parents
    
    def insert(self, i):
        if self.__contains__(i): return
        self.parents[i] = i
        self.sizes[i] = 1
        
    def find(self, i):
        if not self.__contains__(i):
            self.insert(i)
        while i != self.parents[i]:
            self.parents[i] = self.find(self.parents[i])  
            i = self.parents[i]
        return i

    def union(self, p, q):
        root_p, root_q = map(self.find, (p, q))
        if root_p == root_q: return
        small, big = sorted([root_p, root_q], key=lambda x: self.sizes[x])
        self.parents[small] = big
        self.sizes[big] += self.sizes[small]    


class Solution:
    def closedIsland(self, grid: List[List[int]]) -> int:
        nrow, ncol = len(grid), len(grid[0])
        sea =  (nrow, ncol)
        
        uf = UnionFind()
        
        def neighbors(r, c):
            for nr, nc in ((r-1,c), (r+1,c), (r,c-1), (r,c+1)):
                if 0 <= nr < nrow and 0 <= nc < ncol:
                    yield nr, nc
        
        for r in range(nrow):
            for c in range(ncol):
                if grid[r][c] == 1: continue
                    
                uf.insert((r, c))
                
                if r == 0 or c == 0 or r == nrow - 1 or c == ncol - 1:
                    uf.union((r,c), sea)
                
                for nr, nc in neighbors(r, c):
                    if grid[nr][nc] == 0:
                        uf.union((r,c), (nr,nc))
                    
        total = 0
        for land in uf.parents.keys():
            if land == out: continue
            if uf.find(land) == land:
                total += 1
        return total        

695. Max Area of Island Medium

You are given an m x n binary matrix grid. An island is a group of 1’s (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.

The area of an island is the number of cells with a value 1 in the island.

Return the maximum area of an island in grid. If there is no island, return 0.

Stright up union find and compare component sizes.

class UnionFind:
    def __init__(self):
        self.parents = dict()
        self.sizes = dict()
        
    def __contains__(self, i):
        return i in self.parents
    
    def insert(self, i):
        if self.__contains__(i): return
        self.parents[i] = i
        self.sizes[i] = 1
        
    def find(self, i):
        if not self.__contains__(i):
            self.insert(i)
        while i != self.parents[i]:
            self.parents[i] = self.find(self.parents[i])  
            i = self.parents[i]
        return i

    def union(self, p, q):
        root_p, root_q = map(self.find, (p, q))
        if root_p == root_q: return
        small, big = sorted([root_p, root_q], key=lambda x: self.sizes[x])
        self.parents[small] = big
        self.sizes[big] += self.sizes[small]    


class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        nrow, ncol = len(grid), len(grid[0])
        uf = UnionFind()
        for r in range(nrow):
            for c in range(ncol):
                if grid[r][c] == 0: continue
                uf.insert((r,c))        
                for nr, nc in ((r-1, c), (r+1, c), (r, c-1), (r, c+1)):
                    if 0 <= nr < nrow and 0 <= nc < ncol and grid[nr][nc]:
                        uf.insert((nr,nc))
                        uf.union((r,c), (nr,nc))
        
        return max(list(uf.sizes.values()), default=0)

1102. Path With Maximum Minimum Value Medium

Given an m x n integer matrix grid, return the maximum score of a path starting at (0, 0) and ending at (m - 1, n - 1) moving in the 4 cardinal directions.

The score of a path is the minimum value in that path.

Iterate over reverse sorted cell values, insert and union cell along the way. Check when top left and bottom right are connected.

class UnionFind:
    def __init__(self):
        self.parents = dict()
        self.sizes = dict()
        
    def __contains__(self, i):
        return i in self.parents
    
    def insert(self, i):
        if self.__contains__(i): return
        self.parents[i] = i
        self.sizes[i] = 1
        
    def find(self, i):
        if not self.__contains__(i):
            self.insert(i)
        while i != self.parents[i]:
            self.parents[i] = self.find(self.parents[i])  
            i = self.parents[i]
        return i

    def union(self, p, q):
        root_p, root_q = map(self.find, (p, q))
        if root_p == root_q: return
        small, big = sorted([root_p, root_q], key=lambda x: self.sizes[x])
        self.parents[small] = big
        self.sizes[big] += self.sizes[small]    

class Solution:
    def maximumMinimumPath(self, grid: List[List[int]]) -> int:
        nrow, ncol = len(grid), len(grid[0])
        
        uf = UnionFind()
        for val, r, c in sorted(((grid[r][c], r, c) for r in range(nrow) for c in range(ncol)), reverse=True):
            uf.insert((r,c))
            for nr, nc in ((r-1,c),(r+1,c),(r,c-1),(r,c+1)):
                if 0 <= nr < nrow and 0 <= nc < ncol and (nr, nc) in uf:
                    uf.union((r,c), (nr,nc))            
                
                if (0, 0) in uf and (nrow-1, ncol-1) in uf and uf.find((0, 0)) == uf.find((nrow-1, ncol-1)):
                    return val

261. Graph Valid Tree Medium

You have a graph of n nodes labeled from 0 to n - 1. You are given an integer n and a list of edges where edges[i] = [ai, bi] indicates that there is an undirected edge between nodes ai and bi in the graph.

Return true if the edges of the given graph make up a valid tree, and false otherwise.

class UnionFind:
    def __init__(self):
        self.parents = dict()
        self.sizes = dict()
        self.n_comp = 0
        self.n_elems = 0
        
    def __contains__(self, i):
        return i in self.parents
    
    def insert(self, i):
        if self.__contains__(i): return
        self.parents[i] = i
        self.sizes[i] = 1
        self.n_comp += 1
        self.n_elems += 1
        
    def find(self, i):
        if not self.__contains__(i):
            self.insert(i)
        while i != self.parents[i]:
            self.parents[i] = self.find(self.parents[i])  
            i = self.parents[i]
        return i

    def union(self, p, q):
        root_p, root_q = map(self.find, (p, q))
        if root_p == root_q: return
        small, big = sorted([root_p, root_q], key=lambda x: self.sizes[x])
        self.parents[small] = big
        self.sizes[big] += self.sizes[small]    
        self.n_comp -= 1


class Solution:
    def validTree(self, n: int, edges: List[List[int]]) -> bool:
        if n == 1: return True
        uf = UnionFind()
        for n1, n2 in edges:
            if uf.find(n1) == uf.find(n2): return False
            uf.union(n1, n2)
        return uf.n_comp == 1 and uf.n_elems == n

827. Making A Large Island Hard

You are given an n x n binary matrix grid. You are allowed to change at most one 0 to be 1.

Return the size of the largest island in grid after applying this operation.

An island is a 4-directionally connected group of 1s.

class UnionFind:
    def __init__(self):
        self.parents = dict()
        self.sizes = dict()

    def __contains__(self, i):
        return i in self.parents

    def insert(self, i):
        if self.__contains__(i): return
        self.parents[i] = i
        self.sizes[i] = 1

    def find(self, i):
        while i != self.parents[i]:
            self.parents[i] = self.find(self.parents[i])  
            i = self.parents[i]
        return i

    def union(self, p, q):
        root_p, root_q = map(self.find, (p, q))
        if root_p == root_q: return
        small, big = sorted([root_p, root_q], key=lambda x: self.sizes[x])
        self.parents[small] = big
        self.sizes[big] += self.sizes[small]    

        
class Solution:
    def largestIsland(self, grid: List[List[int]]) -> int:        
        nrows, ncols = len(grid), len(grid[0])
        
        def get_neighbors(r, c):
            for nr, nc in [(r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)]:
                if 0 <= nr < nrows and 0 <= nc < ncols:
                    yield nr, nc
                    
        uf = UnionFind()
        
        for r in range(nrows):
            for c in range(ncols):
                if not grid[r][c]: continue
                uf.insert((r, c)) 
                for nr, nc in get_neighbors(r, c):
                    if not grid[nr][nc]: continue
                    uf.insert((nr, nc))       
                    uf.union((r,c), (nr, nc))
                        
        
        max_size = 0 if not uf.sizes else max(uf.sizes.values())
        for r in range(nrows):
            for c in range(ncols):
                if grid[r][c]: continue
                
                neighbor_info = dict()
                for loc in get_neighbors(r, c):
                    if loc not in uf: continue
                    island_id = uf.find(loc)                        
                    neighbor_info[island_id] = uf.sizes[island_id]
                max_size = max(max_size, 1 + sum(neighbor_info.values(), 0))

        return max_size