DSA Cheat Sheet: Deep Notes

Input size → feasible complexity

Operation costs

Sub-topics

• Opposite ends: 2-sum sorted, 3-sum (fix i, 2-ptr rest), container water, trapping rain.
• Same direction: remove dupes, move zeroes (slow=write).
• Dutch flag: 3-way partition (sort colors) with low/mid/high.
• Boyer–Moore voting: majority element (n/2) in O(1) space.
• Next Permutation: find first a[i]<a[i+1] from right, swap w/ next larger, reverse suffix.
• Kadane: max subarray, reset running sum at 0.

def three_sum(a):
    a.sort(); res=[]
    for i in range(len(a)-2):
        if i and a[i]==a[i-1]: continue      # skip dup
        l, r = i+1, len(a)-1
        while l < r:
            s = a[i]+a[l]+a[r]
            if s==0:
                res.append([a[i],a[l],a[r]])
                l+=1; r-=1
                while l
          
Kadane:  cur = max(x, cur+x); best = max(best, cur)
Dutch flag:  [0..low) 0s | [low..mid) 1s | mid..high ? | (high..] 2s
        

• Fixed size k: add a[r], remove a[r-k].
• Variable: grow right; while invalid shrink left; record best.
• Track state: running sum or a frequency map.

def longest_no_repeat(s):
    last, left, best = {}, 0, 0
    for r, ch in enumerate(s):
        if ch in last and last[ch] >= left:
            left = last[ch] + 1        # jump left
        last[ch] = r
        best = max(best, r - left + 1)
    return best

Sub-topics

• On index: classic, first/last occurrence, rotated search, peak element.
• On answer: Koko bananas, ship in D days, split array, allocate books, aggressive cows.
• On floats: nth root, iterate ~100× or until precision.
• 2D matrix: treat as flattened sorted array, or staircase from top-right.

def lower_bound(a, x):
    lo, hi = 0, len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if a[mid] < x: lo = mid+1
        else:          hi = mid
    return lo                     # first idx with a[idx] >= x

def min_feasible(lo, hi, ok):
    while lo < hi:
        mid = (lo+hi)//2
        if ok(mid): hi = mid
        else:       lo = mid+1
    return lo

Prefix / Difference

• Prefix sum: range = pre[r]-pre[l-1].
• #subarrays sum=k: store freq of prefix; ans+=seen[pre-k].
• Prefix XOR: subarray XOR = pre[r]^pre[l-1].
• 2D prefix: submatrix sum O(1).
• Difference array: range update +v at l, −v at r+1; prefix to apply. Great for many range adds.

seen={0:1}; pre=ans=0
for x in nums:
    pre+=x
    ans+=seen.get(pre-k,0)
    seen[pre]=seen.get(pre,0)+1

Hashing

• "seen / count / group / pair" → dict or set (O(1)).
• Anagram key = sorted string OR 26-length count tuple.
• Longest consecutive: only start counting at nums without n-1 present → O(n).
• Index-as-hash: put value v at index v (cyclic sort) for 1..n problems.

Sub-topics

• NGE/NSE, daily temperatures, stock span.
• Largest rectangle in histogram (nearest smaller both sides).
• Sum of subarray minimums (contribution technique).
• Min-stack (store (val,curMin)); valid parentheses; RPN eval; basic calculator.
• LRU = hashmap + doubly linked list; LFU adds freq buckets.
• Deque = sliding window max/min.

def largest_rectangle(h):
    h.append(0); st=[]; best=0        # sentinel
    for i, x in enumerate(h):
        while st and h[st[-1]] >= x:
            height = h[st.pop()]
            width = i if not st else i-st[-1]-1
            best = max(best, height*width)
        st.append(i)
    return best

NGE: [2,1,3] -> decreasing stack of idx
     push 0; push1; 3 pops 1&0 -> ans[1]=3,ans[0]=3

Sub-topics

• Reverse (full / between / k-group).
• Cycle detect + find start; find middle; palindrome.
• Merge two / merge k (heap); add two numbers.
• Remove Nth from end (two ptr gap = n).
• Copy list with random pointer; reorder list.

def reverse(head):
    prev=None
    while head:
        head.next, prev, head = prev, head, head.next
    return prev

dummy = ListNode(0, head)           # simplifies edge cases
# remove nth from end: advance fast n+1 steps, then move both

reverse:  None<-1  2->3   (flip each next to prev)

Sub-topics

• Traversals: pre/in/post (rec + iterative), Morris (O(1) space, thread to predecessor).
• Views: left/right (last per level), top/bottom (by horizontal distance).
• Metrics: height, diameter (max L+R depth), balanced, count nodes.
• Paths: root-to-leaf sum, max path sum (return one side, update global).
• LCA: return node if it equals p/q or splits.
• Construct from pre+in / in+post; serialize (preorder + null markers).
• Distance-K (convert to graph via parent links, BFS).

def diameter(root):
    best = 0
    def depth(n):
        nonlocal best
        if not n: return 0
        L, R = depth(n.left), depth(n.right)
        best = max(best, L + R)     # path through n
        return 1 + max(L, R)
    depth(root); return best

        1
       / \
      2   3      Pre 1 2 4 5 3 | In 4 2 5 1 3
     / \         Post 4 5 2 3 1 | BFS 1|2 3|4 5
    4   5

Sub-topics & properties

• Search/Insert: go left if target < node else right (O(h)).
• Delete: replace with inorder successor (smallest in right subtree).
• Validate: pass (low, high) bounds down, or check inorder increasing.
• LCA in BST: walk down; the first node between p and q is the LCA.
• Floor/Ceil: track candidate while walking down.
• Kth smallest/largest: inorder (or reverse-inorder) with a counter.
• Predecessor/Successor via inorder neighbors.

def kth_smallest(root, k):
    st, node = [], root
    while st or node:
        while node:                 # go left
            st.append(node); node = node.left
        node = st.pop(); k -= 1     # inorder visit
        if k == 0: return node.val
        node = node.right

def lca_bst(root, p, q):
    while root:
        if proot.val and q>root.val: root=root.right
        else: return root           # split point

• Kth largest: min-heap of size k → root = answer.
• Top-K frequent: Counter + heap (or bucket sort).
• Median of stream: two heaps, keep sizes balanced.
• Merge k lists/arrays: heap of (val, listIdx, elemIdx).
• Greedy + heap: task scheduler, IPO, connect ropes.

• Subsets 2ⁿ; permutations n!; combination sum (reuse vs not).
• N-Queens/Sudoku: track cols & diagonals in sets; prune.
• Word search: DFS + mark visited, unmark on return.
• Palindrome partitioning: try every prefix that is a palindrome.

def subsets(nums):
    res=[]
    def bt(start, path):
        res.append(path[:])
        for i in range(start, len(nums)):
            path.append(nums[i])
            bt(i+1, path)          # i+1: no reuse
            path.pop()
    bt(0, []); return res

Traversal / Topo / Cycle

from collections import deque, defaultdict
def topo_kahn(n, edges):
    adj=defaultdict(list); indeg=[0]*n
    for u,v in edges: adj[u].append(v); indeg[v]+=1
    q=deque([i for i in range(n) if indeg[i]==0]); order=[]
    while q:
        u=q.popleft(); order.append(u)
        for v in adj[u]:
            indeg[v]-=1
            if indeg[v]==0: q.append(v)
    return order if len(order)==n else []   # [] => cycle

• Cycle (directed): DFS 3-color (white/gray/black) or Kahn fails.
• Cycle (undirected): DSU union, or DFS with parent.
• Bipartite: 2-color via BFS; conflict → not bipartite.

Shortest path / MST

import heapq
def dijkstra(src, adj, n):
    dist=[float('inf')]*n; dist[src]=0; pq=[(0,src)]
    while pq:
        d,u=heapq.heappop(pq)
        if d>dist[u]: continue
        for v,w in adj[u]:
            if d+w
          

            
Bellman-Ford: relax all edges V−1 times; extra relax → negative cycle.
            
Floyd-Warshall: dp[i][j]=min(dp[i][j], dp[i][k]+dp[k][j]).
            
MST: Kruskal (sort edges + DSU) or Prim (heap).
          
        

Pattern → state

from functools import lru_cache
@lru_cache(None)
def knap(i, cap):
    if i==n or cap==0: return 0
    best = knap(i+1, cap)                 # skip
    if wt[i] <= cap:
        best = max(best, val[i]+knap(i+1, cap-wt[i]))
    return best

# LIS in O(n log n)
import bisect
def lis(a):
    tails=[]
    for x in a:
        i=bisect.bisect_left(tails, x)
        if i==len(tails): tails.append(x)
        else: tails[i]=x
    return len(tails)

• Single number: XOR all → unpaired survives.
• Count set bits: loop x&=x-1, or bin(x).count('1').
• Subsets: iterate mask in range(1<<n).
• Check/set/clear bit i: x>>i&1, x|1<<i, x&~(1<<i).

• GCD (Euclid): gcd(a,b)=gcd(b,a%b); LCM = a*b/gcd.
• Modular: (a+b)%m, (a*b)%m; use pow(a,b,m) for modular power.
• Primes: sieve up to n; a number n is prime if no divisor ≤ √n.
• Combinatorics: nCr = n!/(r!(n−r)!); Pascal for small n.
• Overflow: Python ints are arbitrary precision (no overflow), but state it in other languages.