Week 04 - Advanced Graph + Heap

Reference extracted from the detailed guide.

Day 1-2: Advanced Graph Algorithms

Watch First:

• William Fiset: Dijkstra's → https://www.youtube.com/watch?v=pSqmAO-m7Lk
• NeetCode: Union Find → https://www.youtube.com/watch?v=ibjEGG7ylHk

Template: Dijkstra's

import heapq
def networkDelayTime(times, n, k):
    graph = defaultdict(list)
    for u, v, w in times:
        graph[u].append((v, w))
    
    dist = {k: 0}
    heap = [(0, k)]  # (distance, node)
    
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist.get(u, float('inf')):
            continue
        for v, w in graph[u]:
            if d + w < dist.get(v, float('inf')):
                dist[v] = d + w
                heapq.heappush(heap, (d + w, v))
    
    return max(dist.values()) if len(dist) == n else -1

Template: Union Find

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
    
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # path compression
        return self.parent[x]
    
    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return False  # already connected
        if self.rank[px] < self.rank[py]:
            px, py = py, px
        self.parent[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        return True

Day 3-4: Heap / Priority Queue

Watch First:

• NeetCode: Heap pattern → https://www.youtube.com/watch?v=t0Cq6tVNRBA

Template: Two Heaps (Median)

import heapq
class MedianFinder:
    def __init__(self):
        self.small = []  # max heap (negated)
        self.large = []  # min heap
    
    def addNum(self, num):
        heapq.heappush(self.small, -num)
        
        # Ensure small's max <= large's min
        if self.small and self.large and -self.small[0] > self.large[0]:
            heapq.heappush(self.large, -heapq.heappop(self.small))
        
        # Balance sizes
        if len(self.small) > len(self.large) + 1:
            heapq.heappush(self.large, -heapq.heappop(self.small))
        if len(self.large) > len(self.small) + 1:
            heapq.heappush(self.small, -heapq.heappop(self.large))
    
    def findMedian(self):
        if len(self.small) > len(self.large):
            return -self.small[0]
        if len(self.large) > len(self.small):
            return self.large[0]
        return (-self.small[0] + self.large[0]) / 2

Day 5-6: Trie

Watch First:

• NeetCode: Trie → https://www.youtube.com/watch?v=oobqoCJlHA0

Template: Trie

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    def insert(self, word):
        node = self.root
        for c in word:
            if c not in node.children:
                node.children[c] = TrieNode()
            node = node.children[c]
        node.is_end = True
    
    def search(self, word):
        node = self._find(word)
        return node is not None and node.is_end
    
    def startsWith(self, prefix):
        return self._find(prefix) is not None
    
    def _find(self, prefix):
        node = self.root
        for c in prefix:
            if c not in node.children:
                return None
            node = node.children[c]
        return node

Day 7: Binary Search Mastery

Watch First:

• NeetCode: Binary Search patterns → https://www.youtube.com/watch?v=W9QJ8HaRvJQ

Template: Binary Search on Answer

def minEatingSpeed(piles, h):
    def canFinish(k):
        return sum((p + k - 1) // k for p in piles) <= h
    
    left, right = 1, max(piles)
    while left < right:
        mid = (left + right) // 2
        if canFinish(mid):
            right = mid
        else:
            left = mid + 1
    return left

---