7 posts tagged with "Breadth-First Search"

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

class Solution:
    def coinChange(self, coins: list[int], amount: int) -> int:
        dp = [0] + [0xFFFFFFFF] * (amount)
        for coin in coins:
            for i in range(coin, amount + 1):
                dp[i] = min(dp[i], dp[i - coin] + 1)
        return (dp[-1], -1)[dp[-1] == 0xFFFFFFFF]

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))))

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)

from collections import deque
from heapq import heappop, heappush
from itertools import product
from sys import maxsize

cellT = tuple[int, int]
countT = int


class Solution1:
    # [BFS] Runtime 1349 ms Beats 5.1%
    def shortestPathBinaryMatrix(self, grid: list[list[int]]):
        cellsT = set[cellT]

        N = len(grid)
        dummy_start_cell = (-1, -1)
        bottom_right_cell = (N - 1, N - 1)

        def find_adjacents(curr_row: int, curr_col: int):
            def is_valid(cand_cell: cellT):
                cand_row, cand_col = cand_cell
                return (
                    0 <= cand_row < N
                    and 0 <= cand_col < N
                    and grid[cand_row][cand_col] == 0
                )

            cand_cells = (
                (curr_row + row_offset, curr_col + col_offset)
                for row_offset, col_offset in product(range(-1, 2), repeat=2)
            )
            return filter(is_valid, cand_cells)

        queue: deque[cellsT] = deque([{dummy_start_cell}])
        visiteds: cellsT = set()
        count: countT = 1
        while queue:
            next_: cellsT = set()
            q: cellsT = queue.popleft()
            for cell in q:
                visiteds.add(cell)
                for adjacent in find_adjacents(*cell):
                    if adjacent in visiteds:
                        continue
                    if adjacent == bottom_right_cell:
                        return count
                    next_.add(adjacent)
            if next_:
                queue.append(next_)
            count += 1
        return -1


class Solution2:
    # [dijkstra] Runtime 995 ms Beats 6.89%
    def shortestPathBinaryMatrix(self, grid: list[list[int]]):
        N = len(grid)
        dummy_start_cell = (-1, -1)
        bottom_right_cell = (N - 1, N - 1)

        def find_adjacents(curr_row: int, curr_col: int):
            def is_valid(cand_cell: cellT):
                cand_row, cand_col = cand_cell
                return (
                    0 <= cand_row < N
                    and 0 <= cand_col < N
                    and grid[cand_row][cand_col] == 0
                )

            cand_cells = (
                (curr_row + row_offset, curr_col + col_offset)
                for row_offset, col_offset in product(range(-1, 2), repeat=2)
            )
            return filter(is_valid, cand_cells)

        heap: list[tuple[countT, cellT]] = [(0, dummy_start_cell)]
        visiteds: set[cellT] = set()
        while heap:
            cost, vertex = heappop(heap)
            if vertex == bottom_right_cell:
                return cost
            for new_vertex in find_adjacents(*vertex):
                if new_vertex in visiteds:
                    continue
                visiteds.add(new_vertex)
                new_cost = cost + 1
                heappush(heap, (new_cost, new_vertex))
        return -1


class Solution3:
    # [A*] Runtime 513 ms Beats 97.17%
    def shortestPathBinaryMatrix(self, grid: list[list[int]]):
        N = len(grid)
        dummy_start_cell = (-1, -1)
        bottom_right_cell = (N - 1, N - 1)

        def find_adjacents(curr_row: int, curr_col: int):
            def is_valid(cand_cell: cellT):
                cand_row, cand_col = cand_cell
                return (
                    0 <= cand_row < N
                    and 0 <= cand_col < N
                    and grid[cand_row][cand_col] == 0
                )

            cand_cells = (
                (curr_row + row_offset, curr_col + col_offset)
                for row_offset, col_offset in product(range(-1, 2), repeat=2)
            )
            return filter(is_valid, cand_cells)

        def heuristic(cell_row: int, cell_col: int):
            return max(abs(N - 1 - cell_row), abs(N - cell_col))

        heap: list[tuple[countT, countT, cellT]] = [(-maxsize, 0, dummy_start_cell)]
        costs: dict[cellT, countT] = {}
        while heap:
            estimate, cost, vertex = heappop(heap)
            if vertex == bottom_right_cell:
                return cost
            for new_vertex in find_adjacents(*vertex):
                new_cost = cost + 1
                if costs.get(new_vertex, maxsize) > new_cost:
                    costs[new_vertex] = new_cost
                    new_estimate = new_cost + heuristic(*new_vertex)
                    heappush(heap, (new_estimate, new_cost, new_vertex))
        return -1

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)

from functools import reduce


# 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 levelOrder(self, root) -> list[list[int]]:
        result, q = [], [root]
        while True:
            q = [x for x in q if x]
            v = [x.val for x in q]
            if not v:
                break
            result.append(v)
            q = reduce(lambda a, b: a + [b.left, b.right], q, [])
        return result