backtracking + nested dfs

def wordSearch(self, board: list[list[str]], word: str) -> bool:
        rows, cols = len(board), len(board[0])
        path = set()

        def dfs(r, c, i):
            if i == len(word):
                return True
            if (r < 0 or c < 0 or
                r >= rows or c >= cols or
                word[i] != board[r][c] or
                (r, c) in path):
                return False

            path.add((r, c))
            res = (dfs(r + 1, c, i + 1) or
                   dfs(r - 1, c, i + 1) or
                   dfs(r, c + 1, i + 1) or
                   dfs(r, c - 1, i + 1))
            path.remove((r, c))
            return res

        for r in range(rows):
            for c in range(cols):
                if dfs(r, c, 0): return True
        return False

Level-Order Traversal

from collections import deque

def rightSideView(root):
    if not root: 
	    return []
    
    res = []
    q = deque([root])
    
    while q:
        level_size = len(q)
        for i in range(level_size):
	        node = q.popleft()
	        if node.left:
		        q.append(node.left)
	        if node.right:
		        q.append(node.right)
		      if i == level_size-1:
			      res.append(node.val)
    
    return res

BFS Find Shortest Path (unweighted)

from collections import deque

class Airport():
    def __init__(self, name, neighbors=None):
        self.name = name
        self.neighbors = neighbors if neighbors is not None else []
        
    def add_neighbors(self, airport_to_add):
        self.neighbors.append(airport_to_add)

lga = Airport("LGA")
jfk = Airport("JFK")
ewr = Airport("EWR")
bwi = Airport("BWI")
iad = Airport("IAD")
lga.add_neighbors(jfk)
jfk.add_neighbors(lga)
lga.add_neighbors(ewr)
ewr.add_neighbors(lga)
jfk.add_neighbors(ewr)
ewr.add_neighbors(jfk)
bwi.add_neighbors(iad)
iad.add_neighbors(bwi)
iad.add_neighbors(jfk)
jfk.add_neighbors(iad)
                        
def findShortestPath(a: Airport, b: Airport):
    queue = deque([(a, 0)])
    visited = set([a])

    while queue:
        node, dist = queue.popleft()

        if node == b:
            return dist

        for neighbor in node.neighbors:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, dist + 1))

    return -1                        
       
print(findShortestPath(ewr, bwi))       

Priority Heap

import heapq

def reorganizeString(s):
		     # keep char count
        freq = {}
        # invert count to be negative so min heap acts like max heap
        for c in s:
            freq[c] = freq.get(c, 0) - 1
        # build heap
        heap = [[-count, char] for char, count in freq.items()]
		    heapq.heapify(heap)      
        
        prev_count, prev_char = 0, ""
		    output = []
		
		    while heap:
		        count, char = heapq.heappop(heap)
		        output.append(char)
		
		        if prev_count < 0:
		            heapq.heappush(heap, [prev_count, prev_char])
		
		        count += 1
		        prev_count, prev_char = count, char
		
		    result = "".join(output)
		    return result if len(result) == len(s) else ""   
        
print(reorganizeString("AAABC")) 

topological sort/ cycle detection DFS

from collections import deque

def canFinish(numCourses, prerequisites):
    adj = {i: [] for i in range(numCourses)}
    indegree = {i: 0 for i in range(numCourses)}
    
    # Build graph
    for crs, pre in prerequisites:
        adj[pre].append(crs)
        indegree[crs] += 1
        
    # Queue for nodes with 0 in-degree
    queue = deque([n for n in indegree if indegree[n] == 0])
    
    count = 0
    while queue:
        node = queue.popleft()
        count += 1
        for neighbor in adj[node]:
            indegree[neighbor] -= 1
            if indegree[neighbor] == 0:
                queue.append(neighbor)
                
    return count == numCourses

dfs - check tree property

def isSymmetric(self, root):
        """
        :type root: Optional[TreeNode]
        :rtype: bool
        """

        def dfs(left, right):
            if not left and not right:
                return True
            if not left or not right or left.val != right.val:
                return False
            return dfs(left.left, right.right) and dfs(left.right, right.left)
            

        return dfs(root.left, root.right)