10 posts tagged with "Depth-First Search"

515. Find Largest Value in Each Tree Row - LeetCode

October 24, 2023 · One min read

from typing import Optional


# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution1:
    def largestValues(self, root: Optional[TreeNode]) -> list[int]:
        result, nodes = [], [x for x in [root] if x]
        while nodes:
            result.append(max(x.val for x in nodes))
            _next = []
            _next.extend([x.left for x in nodes if x.left])
            _next.extend([x.right for x in nodes if x.right])
            nodes = _next
        return result


class Solution:
    # https://leetcode.com/problems/find-largest-value-in-each-tree-row/solutions/99000/python-bfs/
    def largestValues(self, root: Optional[TreeNode]) -> list[int]:
        result, nodes = [], [root]
        while any(nodes):
            result.append(max(x.val for x in nodes))
            nodes = [x for n in nodes for x in [n.left, n.right] if x]
        return result

547. Number of Provinces - LeetCode

June 8, 2023 · One min read

from ..notes import Uf


class Solution:
    # https://leetcode.com/problems/number-of-provinces/solutions/923039/union-find-with-union-by-ranks-and-path-compression/
    def findCircleNum(self, isConnected: list[list[int]]) -> int:
        uf = Uf(list(range(len(isConnected))))
        for i in range(len(isConnected)):
            for j in range(i + 1, len(isConnected)):
                if isConnected[i][j]:
                    uf.union(i, j)
        return len(set(uf.find(x) for x in range(len(isConnected))))

1971. Find if Path Exists in Graph - LeetCode

June 7, 2023 · One min read

from collections import deque

vertexT = int


class Solution1:
    # [dfs] Runtime 2560 ms Beats 7.20%
    def validPath(
        self, n: int, edges: list[list[int]], source: int, destination: int
    ) -> bool:
        graph: dict[vertexT, list[vertexT]] = {}
        for vertex_1, vertex_2 in edges:
            graph.setdefault(vertex_1, []).append(vertex_2)
            graph.setdefault(vertex_2, []).append(vertex_1)

        visiteds: set[vertexT] = set()

        def dfs(vertex: vertexT):
            if vertex == destination:
                return True
            if vertex in visiteds:
                return False
            visiteds.add(vertex)
            return any(map(dfs, graph[vertex]))

        return dfs(source)


class Solution2:
    # [bfs] Runtime 1971 ms Beats 61.44%
    def validPath(
        self, n: int, edges: list[list[int]], source: int, destination: int
    ) -> bool:
        graph: dict[vertexT, set[vertexT]] = {}
        for vertex_1, vertex_2 in edges:
            graph.setdefault(vertex_1, set()).add(vertex_2)
            graph.setdefault(vertex_2, set()).add(vertex_1)

        visiteds: set[vertexT] = set()
        queue: deque[set[vertexT]] = deque([{source}])
        while queue:
            next_: set[vertexT] = set()
            q = queue.popleft()
            for vertex in q:
                if vertex == destination:
                    return True
                if vertex in visiteds:
                    continue
                visiteds.add(vertex)
                next_ |= graph[vertex]
            if next_:
                queue.append(next_)
        return False


class Uf3:
    def __init__(self, root: dict[vertexT, vertexT]):
        self.root = root

    def find(self, x: vertexT):
        if x not in self.root:
            self.root[x] = x
        if self.root[x] != x:
            self.root[x] = self.find(self.root[x])
        return self.root[x]

    def union(self, x: vertexT, y: vertexT):
        x_root, y_root = self.find(x), self.find(y)
        self.root[x_root] = y_root


class Solution3:
    # [uf]
    def validPath(
        self, n: int, edges: list[list[int]], source: int, destination: int
    ) -> bool:
        uf = Uf3({})
        for x, y in edges:
            uf.union(x, y)
        return uf.find(source) == uf.find(destination)


class Uf4:
    def __init__(self, root: dict[vertexT, vertexT]):
        self.root = root

    def find(self, x: vertexT):
        # [iteratively]
        if x not in self.root:
            self.root[x] = x
        while self.root[x] != x:
            self.root[x] = self.root[self.root[x]]
            x = self.root[x]
        return self.root[x]

    def union(self, x: vertexT, y: vertexT):
        x_root, y_root = self.find(x), self.find(y)
        self.root[x_root] = y_root


class Solution4:
    def validPath(
        self, n: int, edges: list[list[int]], source: int, destination: int
    ) -> bool:
        uf = Uf4({})
        for x, y in edges:
            uf.union(x, y)
        return uf.find(source) == uf.find(destination)


class Uf5:
    def __init__(self, root: dict[vertexT, vertexT]):
        self.root = root

    def find(self, x: vertexT):
        # dict.setdefault
        if self.root.setdefault(x, x) != x:
            self.root[x] = self.find(self.root[x])
        return self.root[x]

    def union(self, x: vertexT, y: vertexT):
        x_root, y_root = self.find(x), self.find(y)
        self.root[x_root] = y_root


class Solution5:
    def validPath(
        self, n: int, edges: list[list[int]], source: int, destination: int
    ) -> bool:
        uf = Uf5({})
        for x, y in edges:
            uf.union(x, y)
        return uf.find(source) == uf.find(destination)


class Uf6:
    DUMMY_VERTEX = -1

    def __init__(self, root: list[vertexT]):
        # use `list`
        self.root = root

    def find(self, x: vertexT):
        if self.root[x] is self.DUMMY_VERTEX:
            self.root[x] = x
        if self.root[x] != x:
            self.root[x] = self.find(self.root[x])
        return self.root[x]

    def union(self, x: vertexT, y: vertexT):
        x_root, y_root = self.find(x), self.find(y)
        self.root[x_root] = y_root


class Solution6:
    def validPath(
        self, n: int, edges: list[list[int]], source: int, destination: int
    ) -> bool:
        uf = Uf6(list(range(n)))
        for x, y in edges:
            uf.union(x, y)
        return uf.find(source) == uf.find(destination)


class Uf7:
    def __init__(self, root: list[vertexT]):
        self.root = root

    def find(self, x: vertexT):
        # without dummy (run union)
        if self.root[x] != x:
            self.root[x] = self.find(self.root[x])
        return self.root[x]

    def union(self, x: vertexT, y: vertexT):
        x_root, y_root = self.find(x), self.find(y)
        self.root[x_root] = y_root


class Solution7:
    def validPath(
        self, n: int, edges: list[list[int]], source: int, destination: int
    ) -> bool:
        uf = Uf7(list(range(n)))
        for x, y in edges:
            uf.union(x, y)
        return uf.find(source) == uf.find(destination)

133. Clone Graph - LeetCode

April 22, 2023 · One min read

from collections import deque


# Definition for a Node.
class Node:
    def __init__(self, val=0, neighbors=None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []


class Solution1:
    def cloneGraph(self, node: 'Node') -> 'Node':
        visited = {}

        def dfs(node):
            if node in visited:
                return visited[node]
            visited[node] = Node(val=node.val)
            # note: create new node first, then update the neighbors
            visited[node].neighbors = [dfs(x) for x in node.neighbors]
            return visited[node]

        return node and dfs(node)


class Solution2:
    def cloneGraph(self, node: 'Node') -> 'Node':
        def bfs(node):
            visited = {node: Node(val=node.val)}
            queue = [node]
            while queue:
                next_ = []
                for q in queue:
                    for n in q.neighbors:
                        if n not in visited:
                            visited[n] = Node(val=n.val)
                            next_.append(n)
                        visited[q].neighbors.append(visited[n])
                queue = next_
            return visited[node]

        return node and bfs(node)


class Solution:
    def cloneGraph(self, node: 'Node') -> 'Node':
        def bfs(node):
            visited = {node: Node(val=node.val)}
            queue = deque([node])
            while queue:
                q = queue.popleft()
                for n in q.neighbors:
                    if n not in visited:
                        visited[n] = Node(val=n.val)
                        queue.append(n)
                    visited[q].neighbors.append(visited[n])
            return visited[node]

        return node and bfs(node)

1706. Where Will the Ball Fall - LeetCode

March 13, 2023 · One min read

class Solution:
    def findBall(self, grid: list[list[int]]) -> list[int]:
        N = len(grid[0])

        def drop(pos: int) -> int:
            for row in grid:
                adj = pos + row[pos]
                if not 0 <= adj < N:
                    return -1
                if row[pos] != row[adj]:
                    return -1
                pos = adj
            return pos

        return [drop(x) for x in range(N)]

200. Number of Islands - LeetCode

November 13, 2022 · One min read

class Solution:
    def numIslands(self, grid) -> int:
        M, N = len(grid), len(grid[0])

        def dfs(m, n):
            r = 0 <= m < M and 0 <= n < N and grid[m][n] == '1'
            if r:
                grid[m][n] = None
                list(map(dfs, (m + 1, m - 1, m, m), (n, n, n + 1, n - 1)))
            return r

        return sum(dfs(m, n) for m in range(M) for n in range(N))

235. Lowest Common Ancestor of a Binary Search Tree - LeetCode

November 13, 2022 · One min read

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None


class Solution:
    def lowestCommonAncestor(self, root, p, q):
        if root.val > max(p.val, q.val):
            return self.lowestCommonAncestor(root.left, p, q)
        if root.val < min(p.val, q.val):
            return self.lowestCommonAncestor(root.right, p, q)
        return root

733. Flood Fill - LeetCode

November 13, 2022 · One min read

class Solution:
    def floodFill(
        self, image: list[list[int]], sr: int, sc: int, color: int
    ) -> list[list[int]]:
        COLOR, M, N = image[sr][sc], len(image), len(image[0])

        def dfs(m, n):
            if not all([0 <= m < M, 0 <= n < N]):
                return

            if not all([image[m][n] == COLOR, image[m][n] != color]):
                return

            image[m][n] = color
            list(map(dfs, (m + 1, m - 1, m, m), (n, n, n + 1, n - 1)))

        dfs(sr, sc)
        return image

98. Validate Binary Search Tree - LeetCode

November 12, 2022 · One min read

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isValidBST(self, root, lo=float('-inf'), hi=float('inf')) -> bool:
        '''
        [5,4,6,null,null,3,7] => false
        '''
        return (not root) or all(
            [
                lo < root.val < hi,
                self.isValidBST(root.left, lo, root.val),
                self.isValidBST(root.right, root.val, hi),
            ]
        )

589. N-ary Tree Preorder Traversal - LeetCode

November 10, 2022 · One min read

class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children


class Solution:
    def preorder(self, root):
        return (
            (root.val,) + sum((self.preorder(x) for x in root.children), ())
            if root
            else ()
        )