Documenting LeetCode solving.
Q108
Medium. Graph.
"""
# 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 []
"""
from typing import Optional
class Solution:
def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
oldToNew = {}
def clone(node):
# already been cloned
if node in oldToNew:
return oldToNew[node]
copy = Node(node.val)
oldToNew[node] = copy
# clone neighbors
for nei in node.neighbors:
copy.neighbors.append(clone(nei))
return copy
return clone(node) if node else None
Q109
417. Pacific Atlantic Water Flow
Medium. Graph
class Solution:
def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
ROWS, COLS = len(heights), len(heights[0])
pac, atl = set(), set()
def dfs(r, c, visit, prevH):
if ((r, c) in visit or
r < 0 or c < 0 or r == ROWS or c == COLS or
heights[r][c] < prevH):
return
visit.add((r, c))
dfs(r + 1, c, visit, heights[r][c])
dfs(r - 1, c, visit, heights[r][c])
dfs(r, c + 1, visit, heights[r][c])
dfs(r, c - 1, visit, heights[r][c])
# from ocean to node instead of node to ocean
for c in range(COLS):
# first row is adjacent to the pacific ocean
dfs(0, c, pac, heights[0][c])
# last row is adjacent to the atlantic ocean
dfs(ROWS - 1, c, atl, heights[ROWS - 1][c])
for r in range(ROWS):
# first column is adjacent to the pacific ocean
dfs(r, 0, pac, heights[r][0])
# last column is adjacent to the atlantic ocean
dfs(r, COLS - 1, atl, heights[r][COLS - 1])
# res = []
# for r in range(ROWS):
# for c in range(COLS):
# if (r, c) in pac and (r, c) in atl:
# res.append([r, c])
# return res
# can replace above for loop
return list(pac.intersection(atl))