Graph

694. Number of Distinct Islands

class Solution:
    def numDistinctIslands(self, grid: List[List[int]]) -> int:
        islands = collections.defaultdict(list)
        if not grid or not grid[0]:return 0
        R, C = len(grid), len(grid[0])
        def dfs(i,j):
            if i<0 or i>=R or j<0 or j>=C or grid[i][j]==0:return
            this_island.append((i,j))
            grid[i][j] = 0
            for di, dj in [(0,1),(0,-1),(1,0),(-1,0)]:
                r, c = i+di, j+dj
                dfs(r,c)
            
        for i in range(R):
            for j in range(C):
                if grid[i][j]:
                    this_island = []
                    dfs(i, j)
                    l = len(this_island)
                    islands[l].append(this_island)
        res = 0
        def convert(island):
            di, dj = min(island)
            return tuple(sorted([(i-di, j-dj) for i,j in island ]))
        for key in islands:
            if len(islands[key])==1:
                res += 1
            else:
                distinct_islands = {convert(island) for island in islands[key]}
                res += len(distinct_islands)
        return res

1102. Path With Maximum Minimum Value

Solution 1: backtracking got TLE (31 / 85 test cases passed.)

class Solution:
    def maximumMinimumPath(self, A: List[List[int]]) -> int:
        R, C = len(A), len(A[0])
        self.res = -float('inf')
        def dfs(i,j, min_val, visited):
            if (i,j)==(R-1, C-1):self.res = max(self.res, min_val)
            if min_val <= self.res:return
            for di, dj in [(0,1),(0,-1),(1,0),(-1,0)]:
                r, c = i+di, j+dj
                if 0<=r<R and 0<=c<C and (r,c) not in visited:
                    visited.add((r,c))
                    this_min_val = min(min_val, A[r][c])
                    dfs(r,c, this_min_val, visited)
                    visited.remove((r,c))
        dfs(0,0, A[0][0], {(0,0)})
        return self.res

Binary search and union find still TLE (67 / 85 test cases passed.)

class Solution:
    def maximumMinimumPath(self, A: List[List[int]]) -> int:
        R, C = len(A), len(A[0])
        min_, max_ = float('inf'), -float('inf')
        for i in range(R):
            for j in range(C):
                a = A[i][j]
                min_= min(min_, a)
                max_=max(max_, a)
        l, r = min_, max_
        
        def good(m):
            uf = {}
            def find(x):
                uf.setdefault(x,x)
                if x!=uf[x]:
                    uf[x] = find(uf[x])
                return uf[x]
            def union(x,y):
                uf[find(y)] = find(x)
            for i in range(R):
                for j in range(C):
                    if A[i][j]<m:continue
                    for di, dj in [(0,1),(0,-1),(1,0),(-1,0)]:
                        r, c = i+di, j+dj
                        if 0<=r<R and 0<=c<C and A[r][c]>=m:
                            union((i,j), (r,c))
            return find((0,0)) ==find((R-1, C-1))
            
        while l<r:
            m = (l+r+1)//2
            #print(m)
            if good(m):
                #print('True')
                l = m
            else:
                #print('False')
                r = m-1
        return l

Binary search and union find improved version still TLE (72 / 85 test cases passed.)

class Solution:
    def maximumMinimumPath(self, A: List[List[int]]) -> int:
        R, C = len(A), len(A[0])
        min_ = min(A[0][0], A[-1][-1])
        candidates = {A[i][j] for i in range(R)
                              for j in range(C)
                              if A[i][j]<=min_}
        candidates = sorted(candidates)
        l, r = 0, len(candidates)-1
        
        def good(m):
            uf = {}
            def find(x):
                uf.setdefault(x,x)
                if x!=uf[x]:
                    uf[x] = find(uf[x])
                return uf[x]
            def union(x,y):
                uf[find(y)] = find(x)
            for i in range(R):
                for j in range(C):
                    if A[i][j]<m:continue
                    for di, dj in [(0,1),(0,-1),(1,0),(-1,0)]:
                        r, c = i+di, j+dj
                        if 0<=r<R and 0<=c<C and A[r][c]>=m:
                            union((i,j), (r,c))
            return find((0,0)) ==find((R-1, C-1))
            
        while l<r:
            m = (l+r+1)//2
            #print(m, candidates[m])
            if good(candidates[m]):
                #print('True')
                l = m
            else:
                #print('False')
                r = m-1
        return candidates[l]

79. Word Search

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        root = []
        if not board or not board[0]:return False
        R, C = len(board), len(board[0])
        if len(word)>R*C:return False
        if not word:return False
        for i in range(R):
            for j in range(C):
                if board[i][j]==word[0]:root.append((i,j))
        self.found = False
        def dfs(i,j, k):
            if k+1==len(word):self.found=True
            if not self.found:
                original_val = board[i][j]
                board[i][j] = '#'
                for di, dj in [(0,1),(0,-1),(1,0),(-1,0)]:
                    r, c = i+di, j+dj
                    if 0<=r<R and 0<=c<C and board[r][c]==word[k+1]:
                        dfs(r,c,k+1)
                board[i][j] = original_val
        for i,j in root:
            dfs(i,j, 0)
        return self.found