LeetCode Patterns

left, right = 0, len(arr) - 1
while left < right:
    if condition:
        left += 1
    else:
        right -= 1

left = 0
for right in range(len(arr)):
    # expand window
    while window_invalid:
        # shrink from left
        left += 1
    # update best answer

lo, hi = 0, len(arr) - 1
while lo <= hi:
    mid = (lo + hi) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        lo = mid + 1
    else:
        hi = mid - 1

slow = fast = head
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next
    if slow == fast:
        # cycle detected

prefix = [0] * (len(arr) + 1)
for i in range(len(arr)):
    prefix[i+1] = prefix[i] + arr[i]
# sum(arr[l:r]) = prefix[r] - prefix[l]

stack = []
for i, val in enumerate(arr):
    while stack and arr[stack[-1]] < val:
        idx = stack.pop()
        # arr[idx]'s next greater = val
    stack.append(i)

from collections import deque
queue = deque([start])
visited = {start}
while queue:
    node = queue.popleft()
    for neighbor in graph[node]:
        if neighbor not in visited:
            visited.add(neighbor)
            queue.append(neighbor)

def dfs(node, visited):
    if node in visited:
        return
    visited.add(node)
    for neighbor in graph[node]:
        dfs(neighbor, visited)

def backtrack(path, choices):
    if is_solution(path):
        result.append(path[:])
        return
    for choice in choices:
        path.append(choice)    # choose
        backtrack(path, ...)   # explore
        path.pop()             # unchoose

# Bottom-up
dp = [base_case] * (n + 1)
for i in range(1, n + 1):
    dp[i] = recurrence(dp[i-1], ...)
return dp[n]

# Sort by end time / weight / ratio
items.sort(key=lambda x: x.end)
for item in items:
    if can_take(item):
        take(item)  # never backtrack

intervals.sort(key=lambda x: x[0])
merged = [intervals[0]]
for start, end in intervals[1:]:
    if start <= merged[-1][1]:
        merged[-1][1] = max(merged[-1][1], end)
    else:
        merged.append([start, end])

# Kahn's algorithm (BFS)
indegree = {u: 0 for u in graph}
for u in graph:
    for v in graph[u]:
        indegree[v] += 1
queue = deque(u for u in indegree if indegree[u] == 0)
order = []
while queue:
    u = queue.popleft()
    order.append(u)
    for v in graph[u]:
        indegree[v] -= 1
        if indegree[v] == 0:
            queue.append(v)

parent = list(range(n))
rank = [0] * n
def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])  # path compression
    return parent[x]
def union(a, b):
    ra, rb = find(a), find(b)
    if ra == rb: return False
    if rank[ra] < rank[rb]: ra, rb = rb, ra
    parent[rb] = ra
    if rank[ra] == rank[rb]: rank[ra] += 1
    return True

import heapq
# Top K largest
heap = []
for num in arr:
    heapq.heappush(heap, num)
    if len(heap) > k:
        heapq.heappop(heap)  # remove smallest
return heap  # k largest remain