Shortest Path in Binary Matrix

def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int: q = collections.deque([(1, 0, 0)]) rows = len(grid) cols = len(grid[0]) visited = set((0, 0)) if grid[0][0] == 1: return -1 while q: hop, y, x = q.popleft() if y == rows - 1 and x == cols - 1: return hop for ox, oy in [(-1, -1), (0, -1), (1, -1), (1, 0), (1, 1), (0, 1), (-1,..

Network Delay Time

def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int: g = collections.defaultdict(lambda: collections.defaultdict(int)) for u, v, w in times: g[u][v] = w dists = {i: float('inf') for i in range(1, n + 1)} dists[k] = 0 q = [(0, k)] while q: inc, u = heapq.heappop(q) for v, cost in g[u].items(): if inc + cost >= dists[v]: ..

Cheapest Flights Within K Stops

class Solution: def find_cheapest_price(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int: g = collections.defaultdict(lambda: collections.defaultdict(int)) for u, v, weight in flights: g[u][v] = weight q = [(0, k + 1, src)] while q: dist, k, u = heapq.heappop(q) if u == dst: return dist ..

Graph Valid Tree

class Solution: """ @param n: An integer @param edges: a list of undirected edges @return: true if it's a valid tree, or false """ def valid_tree(self, n, edges): parents = [i for i in range(n)] def find_root(node): while parents[node] != node: node = parents[node] return node for u, v in edges: ur = find_root..

Palindrome Permutation

class Solution: """ @param s: the given string @return: if a permutation of the string could form a palindrome """ def can_permute_palindrome(self, s: str) -> bool: freq = collections.Counter(s) if len(freq.items()) == 1: return True odd_count = 0 for ch, count in freq.items(): if count % 2 != 0: odd_count += 1 ..

class Solution: def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool: g = collections.defaultdict(list) for u, v in prerequisites: g[u] += v, topology = collections.defaultdict(int) for u, adjs in g.items(): for v in adjs: topology[v] += 1 q = collections.deque() visited = set() for i..