Python DSA Complete Reference Page 1
Python DSA
Complete Reference
Every pattern & syntax you need to solve DSA problems
Arrays Linked List Stack & Queue Binary Search
Recursion &
Heaps Binary Tree & BST Graph
Backtracking
Dynamic
Strings Greedy Trie
Programming
All patterns & syntax needed to crack DSA problems in Python
Python DSA Complete Reference Page 2
Table of Contents
01. Arrays — 8 concepts
02. Linked List — 4 concepts
03. Stack & Queue — 3 concepts
04. Binary Search — 3 concepts
05. Heaps — 2 concepts
06. Recursion & Backtracking — 2 concepts
07. Binary Tree & BST — 4 concepts
08. Graph — 6 concepts
09. Dynamic Programming — 3 concepts
10. Strings — 3 concepts
11. Greedy — 1 concept
12. Trie — 2 concepts
All patterns & syntax needed to crack DSA problems in Python
Python DSA Complete Reference Page 3
Arrays
Array Declaration & Access
# 1D array
arr = [1, 2, 3, 4, 5]
arr[0] # first element -> 1
arr[-1] # last element -> 5
arr[1:4] # slice [2,3,4]
arr[::-1] # reverse
# 2D array (matrix)
mat = [[1,2,3],[4,5,6],[7,8,9]]
mat[1][2] # -> 6
rows, cols = len(mat), len(mat[0])
Array Operations — Insert / Delete / Search
arr = [1,2,3,4,5]
[Link](6) # add to end O(1)
[Link](2, 99) # insert at index O(n)
[Link]() # remove last O(1)
[Link](2) # remove at index O(n)
[Link](99) # remove first match O(n)
[Link](3) # find index O(n)
3 in arr # membership check O(n)
[Link]() # sort in-place O(n log n)
sorted(arr) # returns new sorted list
[Link]() # reverse in-place
Two-Pointer Technique
def two_sum_sorted(arr, target):
l, r = 0, len(arr) - 1
while l < r:
s = arr[l] + arr[r]
if s == target: return [l, r]
elif s < target: l += 1
else: r -= 1
return []
# Reverse array in-place
def reverse(arr):
l, r = 0, len(arr)-1
while l < r:
arr[l], arr[r] = arr[r], arr[l]
l += 1; r -= 1
All patterns & syntax needed to crack DSA problems in Python
Python DSA Complete Reference Page 4
Sliding Window
# Fixed window — max sum of size k
def max_sum(arr, k):
win = sum(arr[:k]); best = win
for i in range(k, len(arr)):
win += arr[i] - arr[i-k]
best = max(best, win)
return best
# Variable window — longest subarray with sum <= target
def longest(arr, target):
l = best = cur = 0
for r in range(len(arr)):
cur += arr[r]
while cur > target:
cur -= arr[l]; l += 1
best = max(best, r-l+1)
return best
Prefix Sum & Difference Array
# Prefix sum -> range sum in O(1)
def build(arr):
pre = [0] * (len(arr)+1)
for i,v in enumerate(arr):
pre[i+1] = pre[i] + v
return pre
def query(pre, l, r): # range sum [l,r] inclusive
return pre[r+1] - pre[l]
# 2D prefix sum
pre2 = [[0]*(C+1) for _ in range(R+1)]
for i in range(1,R+1):
for j in range(1,C+1):
pre2[i][j] = (mat[i-1][j-1]
+ pre2[i-1][j] + pre2[i][j-1]
- pre2[i-1][j-1])
All patterns & syntax needed to crack DSA problems in Python
Python DSA Complete Reference Page 5
Kadane's Algorithm — Max Subarray Sum
def max_subarray(arr):
best = cur = arr[0]
for x in arr[1:]:
cur = max(x, cur + x)
best = max(best, cur)
return best
# Track indices too
def max_subarray_idx(arr):
best = cur = arr[0]; start = end = tmp = 0
for i in range(1, len(arr)):
if arr[i] > cur + arr[i]:
cur = arr[i]; tmp = i
else: cur += arr[i]
if cur > best:
best = cur; start, end = tmp, i
return best, start, end
Sorting Algorithms
# Quick sort
def qsort(a, l, r):
if l >= r: return
p = partition(a, l, r)
qsort(a, l, p-1); qsort(a, p+1, r)
def partition(a, l, r):
pivot = a[r]; i = l - 1
for j in range(l, r):
if a[j] <= pivot:
i += 1; a[i],a[j] = a[j],a[i]
a[i+1],a[r] = a[r],a[i+1]
return i+1
# Merge sort
def msort(a):
if len(a) <= 1: return a
m = len(a)//2
L, R = msort(a[:m]), msort(a[m:])
return merge(L, R)
def merge(L, R):
res=[]; i=j=0
while i<len(L) and j<len(R):
if L[i]<=R[j]: [Link](L[i]); i+=1
else: [Link](R[j]); j+=1
return res + L[i:] + R[j:]
All patterns & syntax needed to crack DSA problems in Python
Python DSA Complete Reference Page 6
Matrix Traversal — Spiral & Rotate 90°
# Spiral order
def spiral(mat):
res=[]; t,b,l,r=0,len(mat)-1,0,len(mat[0])-1
while t<=b and l<=r:
for c in range(l,r+1): [Link](mat[t][c]); t+=1
for row in range(t,b+1): [Link](mat[row][r]); r-=1
if t<=b:
for c in range(r,l-1,-1): [Link](mat[b][c]); b-=1
if l<=r:
for row in range(b,t-1,-1): [Link](mat[row][l]); l+=1
return res
# Rotate 90 degrees clockwise
def rotate(mat):
n=len(mat)
for i in range(n): # transpose
for j in range(i+1,n):
mat[i][j],mat[j][i]=mat[j][i],mat[i][j]
for row in mat: [Link]()
All patterns & syntax needed to crack DSA problems in Python
Python DSA Complete Reference Page 7
Linked List
Node Definition & Basic Operations
class ListNode:
def __init__(self, val=0, nxt=None):
[Link] = val; [Link] = nxt
# Build list from array
def build(arr):
dummy = ListNode(0); cur = dummy
for v in arr:
[Link] = ListNode(v); cur = [Link]
return [Link]
# Traverse & print
def traverse(head):
while head:
print([Link], end=" -> "); head = [Link]
Reverse a Linked List
# Iterative O(n) time O(1) space
def reverse(head):
prev = None
while head:
nxt = [Link]; [Link] = prev
prev = head; head = nxt
return prev
# Recursive
def reverseR(head, prev=None):
if not head: return prev
nxt = [Link]; [Link] = prev
return reverseR(nxt, head)
All patterns & syntax needed to crack DSA problems in Python
Python DSA Complete Reference Page 8
Fast & Slow Pointer — Floyd's Cycle
# Detect cycle
def has_cycle(head):
slow = fast = head
while fast and [Link]:
slow = [Link]; fast = [Link]
if slow == fast: return True
return False
# Find middle node
def middle(head):
slow = fast = head
while fast and [Link]:
slow = [Link]; fast = [Link]
return slow
# Find cycle start
def cycle_start(head):
slow = fast = head
while fast and [Link]:
slow=[Link]; fast=[Link]
if slow==fast:
slow=head
while slow!=fast: slow=[Link]; fast=[Link]
return slow
return None
Merge, Delete & Nth-from-End
# Merge two sorted lists
def merge(l1, l2):
dummy = cur = ListNode(0)
while l1 and l2:
if [Link] <= [Link]: [Link]=l1; l1=[Link]
else: [Link]=l2; l2=[Link]
cur=[Link]
[Link] = l1 or l2
return [Link]
# Remove nth from end (one pass)
def remove_nth(head, n):
dummy = ListNode(0, head); l, r = dummy, head
for _ in range(n): r = [Link]
while r: l=[Link]; r=[Link]
[Link] = [Link]
return [Link]
All patterns & syntax needed to crack DSA problems in Python
Python DSA Complete Reference Page 9
Stack & Queue
Stack — List & Monotonic Stack
# List as stack
stack = []
[Link](1) # push O(1)
[Link]() # pop O(1)
stack[-1] # peek O(1)
# Monotonic stack — next greater element
def next_greater(arr):
res = [-1]*len(arr); st = []
for i,v in enumerate(arr):
while st and arr[st[-1]] < v:
res[[Link]()] = v
[Link](i)
return res
# Valid parentheses
def is_valid(s):
st=[]; m={')':'(',']':'[','}':'{'}
for c in s:
if c in m:
if not st or st[-1]!=m[c]: return False
[Link]()
else: [Link](c)
return not st
Queue & Deque
from collections import deque
q = deque()
[Link](1) # enqueue rear O(1)
[Link](0) # enqueue front O(1)
[Link]() # dequeue front O(1)
[Link]() # dequeue rear O(1)
# Sliding window maximum (monotonic deque)
def max_window(arr, k):
dq, res = deque(), []
for i, v in enumerate(arr):
while dq and dq[0] < i-k+1: [Link]()
while dq and arr[dq[-1]] < v: [Link]()
[Link](i)
if i >= k-1: [Link](arr[dq[0]])
return res
All patterns & syntax needed to crack DSA problems in Python
Python DSA Complete Reference Page 10
Min Stack
class MinStack:
def __init__(self):
[Link] = []; self.min_st = []
def push(self, val):
[Link](val)
m = min(val, self.min_st[-1] if self.min_st else val)
self.min_st.append(m)
def pop(self):
[Link](); self.min_st.pop()
def top(self):
return [Link][-1]
def getMin(self):
return self.min_st[-1]
All patterns & syntax needed to crack DSA problems in Python
Python DSA Complete Reference Page 11
Binary Search
Classic Binary Search
# Find exact target
def bs(arr, target):
l, r = 0, len(arr)-1
while l <= r:
m = (l+r)//2
if arr[m] == target: return m
elif arr[m] < target: l = m+1
else: r = m-1
return -1
# Lower bound — first index where arr[i] >= target
def lower_bound(arr, target):
l, r = 0, len(arr)
while l < r:
m = (l+r)//2
if arr[m] < target: l = m+1
else: r = m
return l
# Upper bound — first index where arr[i] > target
def upper_bound(arr, target):
l, r = 0, len(arr)
while l < r:
m = (l+r)//2
if arr[m] <= target: l = m+1
else: r = m
return l
All patterns & syntax needed to crack DSA problems in Python
Python DSA Complete Reference Page 12
BS on Answer & Rotated Array
# Rotated sorted array search
def search_rotated(arr, t):
l, r = 0, len(arr)-1
while l <= r:
m = (l+r)//2
if arr[m] == t: return m
if arr[l] <= arr[m]: # left sorted
if arr[l] <= t < arr[m]: r = m-1
else: l = m+1
else: # right sorted
if arr[m] < t <= arr[r]: l = m+1
else: r = m-1
return -1
# Binary search on answer
def feasible(arr, k, m, mid):
b=c=0
for v in arr:
c = c+1 if v<=mid else 0
if c==k: b+=1; c=0
return b >= m
def min_days(arr, m, k):
l, r = min(arr), max(arr)
while l < r:
mid = (l+r)//2
if feasible(arr, k, m, mid): r = mid
else: l = mid+1
return l
bisect Module (Built-in)
import bisect
a = [1, 3, 5, 7, 9]
bisect.bisect_left(a, 5) # -> 2 (lower_bound)
bisect.bisect_right(a, 5) # -> 3 (upper_bound)
[Link](a, 6) # insert in sorted order
# Count occurrences in sorted array
def count(a, target):
return bisect.bisect_right(a,target) - bisect.bisect_left(a,target)
All patterns & syntax needed to crack DSA problems in Python
Python DSA Complete Reference Page 13
Heaps
heapq — Min Heap
import heapq
h = []
[Link](h, 5) # push O(log n)
[Link](h, 2)
[Link](h) # pop min O(log n)
h[0] # peek min O(1)
[Link](arr) # heapify list O(n)
# Max heap -> negate values
[Link](h, -10)
-[Link](h) # -> 10
[Link](3, arr) # O(n log k)
[Link](3, arr)
Top-K & Median from Data Stream
# Kth largest (min-heap of size k)
def kth_largest(arr, k):
h = arr[:k]; [Link](h)
for v in arr[k:]:
if v > h[0]: [Link](h, v)
return h[0]
# Median from data stream
class MedianFinder:
def __init__(self):
[Link] = [] # max-heap (negated)
[Link] = [] # min-heap
def add(self, n):
[Link]([Link], -n)
[Link]([Link], -[Link]([Link]))
if len([Link]) > len([Link]):
[Link]([Link], -[Link]([Link]))
def median(self):
if len([Link]) > len([Link]): return -[Link][0]
return (-[Link][0] + [Link][0]) / 2
All patterns & syntax needed to crack DSA problems in Python
Python DSA Complete Reference Page 14
Recursion & Backtracking
Recursion Fundamentals
# Template for every recursive function
def solve(params):
if base_condition: return base_value # 1. Base case
# 2. Reduce + 3. Recurse + combine
return combine(solve(smaller_params))
def factorial(n):
return 1 if n<=1 else n*factorial(n-1)
# Memoized fibonacci
def fib(n, memo={}):
if n<=1: return n
if n in memo: return memo[n]
memo[n] = fib(n-1)+fib(n-2)
return memo[n]
# Fast exponentiation O(log n)
def power(base, exp):
if exp==0: return 1
half = power(base, exp//2)
return half*half if exp%2==0 else half*half*base
All patterns & syntax needed to crack DSA problems in Python
Python DSA Complete Reference Page 15
Backtracking Template
def backtrack(state, choices):
if is_solution(state):
[Link](state[:])
return
for choice in choices:
if is_valid(state, choice):
[Link](choice)
backtrack(state, next_choices)
[Link]() # undo
# Subsets (power set)
def subsets(nums):
res=[]; path=[]
def bt(i):
[Link](path[:])
for j in range(i, len(nums)):
[Link](nums[j]); bt(j+1); [Link]()
bt(0); return res
# Permutations
def permute(nums):
res=[]; used=[False]*len(nums); path=[]
def bt():
if len(path)==len(nums): [Link](path[:]); return
for i,v in enumerate(nums):
if not used[i]:
used[i]=True; [Link](v); bt()
used[i]=False; [Link]()
bt(); return res
All patterns & syntax needed to crack DSA problems in Python
Python DSA Complete Reference Page 16
Binary Tree & BST
Tree Node & Traversals
class TreeNode:
def __init__(self, val=0, l=None, r=None):
[Link]=val; [Link]=l; [Link]=r
# Recursive traversals
def inorder(root): # left->root->right
return inorder([Link])+[[Link]]+inorder([Link]) if root else []
def preorder(root): # root->left->right
return [[Link]]+preorder([Link])+preorder([Link]) if root else []
def postorder(root): # left->right->root
return postorder([Link])+postorder([Link])+[[Link]] if root else []
# Iterative inorder
def inorder_iter(root):
res=[]; st=[]; cur=root
while cur or st:
while cur: [Link](cur); cur=[Link]
cur=[Link](); [Link]([Link]); cur=[Link]
return res
BFS — Level Order Traversal
from collections import deque
def level_order(root):
if not root: return []
res=[]; q=deque([root])
while q:
level=[]
for _ in range(len(q)):
node=[Link](); [Link]([Link])
if [Link]: [Link]([Link])
if [Link]: [Link]([Link])
[Link](level)
return res
# Height / max depth
def height(root):
if not root: return 0
return 1 + max(height([Link]), height([Link]))
# Diameter
def diameter(root):
best=[0]
def dfs(node):
if not node: return 0
l,r=dfs([Link]),dfs([Link])
best[0]=max(best[0], l+r); return 1+max(l,r)
dfs(root); return best[0]
All patterns & syntax needed to crack DSA problems in Python
Python DSA Complete Reference Page 17
LCA, Max Path Sum & Balanced Check
# Lowest Common Ancestor
def lca(root, p, q):
if not root or root==p or root==q: return root
l=lca([Link],p,q); r=lca([Link],p,q)
return root if l and r else l or r
# Max path sum
def max_path(root):
best=[float('-inf')]
def dfs(node):
if not node: return 0
l=max(0,dfs([Link])); r=max(0,dfs([Link]))
best[0]=max(best[0], [Link]+l+r)
return [Link]+max(l,r)
dfs(root); return best[0]
# Check balanced
def is_balanced(root):
def dfs(node):
if not node: return 0
l=dfs([Link]); r=dfs([Link])
if l==-1 or r==-1 or abs(l-r)>1: return -1
return 1+max(l,r)
return dfs(root) != -1
BST — Search, Insert, Delete, Validate
def search(root, val):
if not root or [Link]==val: return root
return search([Link] if val<[Link] else [Link], val)
def insert(root, val):
if not root: return TreeNode(val)
if val < [Link]: [Link]=insert([Link],val)
else: [Link]=insert([Link],val)
return root
def delete(root, key):
if not root: return None
if key < [Link]: [Link]=delete([Link],key)
elif key > [Link]: [Link]=delete([Link],key)
else:
if not [Link]: return [Link]
if not [Link]: return [Link]
cur=[Link]
while [Link]: cur=[Link]
[Link]=[Link]
[Link]=delete([Link],[Link])
return root
def is_bst(root, lo=float('-inf'), hi=float('inf')):
if not root: return True
if not (lo < [Link] < hi): return False
return is_bst([Link],lo,[Link]) and is_bst([Link],[Link],hi)
All patterns & syntax needed to crack DSA problems in Python
Python DSA Complete Reference Page 18
Graph
Graph Representation
from collections import defaultdict
# Adjacency list (most common)
graph = defaultdict(list)
graph[0].append(1)
# Build from edge list
def build(n, edges):
g = defaultdict(list)
for u,v in edges:
g[u].append(v)
g[v].append(u) # undirected
return g
# Adjacency matrix
mat = [[0]*n for _ in range(n)]
mat[u][v] = mat[v][u] = 1
DFS & BFS on Graph
# DFS iterative
def dfs(graph, start):
visited=set(); stack=[start]
while stack:
node=[Link]()
if node in visited: continue
[Link](node)
for nb in graph[node]:
if nb not in visited: [Link](nb)
return visited
# BFS — shortest path (unweighted)
from collections import deque
def bfs(graph, start, end):
q=deque([(start,[start])]); vis={start}
while q:
node,path=[Link]()
if node==end: return path
for nb in graph[node]:
if nb not in vis:
[Link](nb); [Link]((nb,path+[nb]))
return []
All patterns & syntax needed to crack DSA problems in Python
Python DSA Complete Reference Page 19
Topological Sort (Kahn's BFS)
from collections import deque, defaultdict
def topo_sort(n, edges):
g=defaultdict(list); indeg=[0]*n
for u,v in edges: g[u].append(v); indeg[v]+=1
q=deque([i for i in range(n) if indeg[i]==0])
order=[]
while q:
u=[Link](); [Link](u)
for v in g[u]:
indeg[v]-=1
if indeg[v]==0: [Link](v)
return order if len(order)==n else [] # [] = cycle
# DFS-based topo
def topo_dfs(n, g):
vis=[0]*n; stack=[]
def dfs(u):
vis[u]=1
for v in g[u]:
if vis[v]==1: return False
if vis[v]==0 and not dfs(v): return False
vis[u]=2; [Link](u); return True
for i in range(n):
if vis[i]==0 and not dfs(i): return []
return stack[::-1]
Dijkstra's Shortest Path
import heapq
def dijkstra(graph, src, n):
dist=[float('inf')]*n; dist[src]=0
pq=[(0,src)]
while pq:
d,u=[Link](pq)
if d>dist[u]: continue
for v,w in graph[u]:
if dist[u]+w < dist[v]:
dist[v]=dist[u]+w
[Link](pq,(dist[v],v))
return dist
# graph[u] = [(v, weight), ...]
# Time: O((V+E) log V)
All patterns & syntax needed to crack DSA problems in Python
Python DSA Complete Reference Page 20
Union-Find (Disjoint Set Union)
class DSU:
def __init__(self, n):
self.p = list(range(n))
[Link] = [0]*n
def find(self, x):
if self.p[x] != x:
self.p[x] = [Link](self.p[x]) # path compression
return self.p[x]
def union(self, x, y):
px, py = [Link](x), [Link](y)
if px == py: return False
if [Link][px] < [Link][py]: px,py = py,px
self.p[py] = px
if [Link][px]==[Link][py]: [Link][px]+=1
return True
Cycle Detection & Connected Components
# Undirected — DFS cycle
def has_cycle(graph, n):
visited=set()
def dfs(u, parent):
[Link](u)
for v in graph[u]:
if v not in visited:
if dfs(v,u): return True
elif v != parent: return True
return False
for i in range(n):
if i not in visited and dfs(i,-1): return True
return False
# Count connected components
def count_components(n, edges):
dsu=DSU(n)
for u,v in edges: [Link](u,v)
return len({[Link](i) for i in range(n)})
All patterns & syntax needed to crack DSA problems in Python
Python DSA Complete Reference Page 21
Dynamic Programming
DP Fundamentals & Memoization
# Top-down with lru_cache
from functools import lru_cache
@lru_cache(maxsize=None)
def dp(state):
if base_case: return base_value
return min(dp(s) for s in transitions)
# Manual memo
memo = {}
def dp(i, j):
if (i,j) in memo: return memo[(i,j)]
# ... compute ...
memo[(i,j)] = result
return result
# Bottom-up tabulation
def fib_tab(n):
if n<=1: return n
dp=[0]*(n+1); dp[1]=1
for i in range(2,n+1): dp[i]=dp[i-1]+dp[i-2]
return dp[n]
Classic 1D DP Patterns
# Coin change — min coins
def coin_change(coins, amount):
dp=[float('inf')]*(amount+1); dp[0]=0
for i in range(1,amount+1):
for c in coins:
if c<=i: dp[i]=min(dp[i], dp[i-c]+1)
return dp[amount] if dp[amount]!=float('inf') else -1
# Longest Increasing Subsequence O(n log n)
def lis(arr):
tails=[]
for v in arr:
lo,hi=0,len(tails)
while lo<hi:
m=(lo+hi)//2
if tails[m]<v: lo=m+1
else: hi=m
if lo==len(tails): [Link](v)
else: tails[lo]=v
return len(tails)
All patterns & syntax needed to crack DSA problems in Python
Python DSA Complete Reference Page 22
2D DP — LCS, Knapsack, Grid
# Longest Common Subsequence
def lcs(a, b):
m,n=len(a),len(b)
dp=[[0]*(n+1) for _ in range(m+1)]
for i in range(1,m+1):
for j in range(1,n+1):
if a[i-1]==b[j-1]: dp[i][j]=dp[i-1][j-1]+1
else: dp[i][j]=max(dp[i-1][j],dp[i][j-1])
return dp[m][n]
# 0/1 Knapsack
def knapsack(W, wts, vals, n):
dp=[[0]*(W+1) for _ in range(n+1)]
for i in range(1,n+1):
for w in range(W+1):
dp[i][w]=dp[i-1][w]
if wts[i-1]<=w:
dp[i][w]=max(dp[i][w],vals[i-1]+dp[i-1][w-wts[i-1]])
return dp[n][W]
# Minimum path sum in grid
def min_path(grid):
r,c=len(grid),len(grid[0])
dp=[[0]*c for _ in range(r)]; dp[0][0]=grid[0][0]
for i in range(1,r): dp[i][0]=dp[i-1][0]+grid[i][0]
for j in range(1,c): dp[0][j]=dp[0][j-1]+grid[0][j]
for i in range(1,r):
for j in range(1,c):
dp[i][j]=grid[i][j]+min(dp[i-1][j],dp[i][j-1])
return dp[r-1][c-1]
All patterns & syntax needed to crack DSA problems in Python
Python DSA Complete Reference Page 23
Strings
String Fundamentals
s = "hello world"
[Link](); [Link](); [Link]()
[Link]() # split on whitespace
[Link](',') # split on delimiter
' '.join(['a','b']) # join list -> string
[Link]('l','L')
[Link]('world') # index or -1
[Link]('he'); [Link]('ld')
[Link](); [Link](); [Link]()
s[::-1] # reverse string
[Link]('l') # count occurrences
ord('a') -> 97; chr(97) -> 'a'
# String is IMMUTABLE — build with list+join
parts=[]; [Link]('x'); ''.join(parts)
Anagram, Palindrome & Substring
from collections import Counter
def is_anagram(s, t):
return Counter(s) == Counter(t)
def is_palindrome(s):
s = ''.join([Link]() for c in s if [Link]())
return s == s[::-1]
# Longest palindromic substring (expand around center)
def longest_palindrome(s):
res=""
for i in range(len(s)):
for l,r in [(i,i),(i,i+1)]: # odd & even
while l>=0 and r<len(s) and s[l]==s[r]:
if r-l+1>len(res): res=s[l:r+1]
l-=1; r+=1
return res
All patterns & syntax needed to crack DSA problems in Python
Python DSA Complete Reference Page 24
Sliding Window on Strings
from collections import Counter
# Minimum window substring
def min_window(s, t):
need=Counter(t); missing=len(t)
best=float('inf'); res=""; l=0
for r,c in enumerate(s):
if need[c]>0: missing-=1
need[c]-=1
if missing==0:
while need[s[l]]<0: need[s[l]]+=1; l+=1
if r-l+1<best: best=r-l+1; res=s[l:r+1]
need[s[l]]+=1; missing+=1; l+=1
return res
# All anagrams in string
def find_anagrams(s, p):
need=Counter(p); window=Counter(); res=[]; l=0
for r in range(len(s)):
window[s[r]]+=1
if r-l+1>len(p): window[s[l]]-=1; l+=1
if window==need: [Link](l)
return res
All patterns & syntax needed to crack DSA problems in Python
Python DSA Complete Reference Page 25
Greedy
Greedy Patterns
# Activity selection / interval scheduling
def max_activities(intervals):
[Link](key=lambda x: x[1])
count=1; end=intervals[0][1]
for s,e in intervals[1:]:
if s >= end: count+=1; end=e
return count
# Merge intervals
def merge(intervals):
[Link](); res=[intervals[0]]
for s,e in intervals[1:]:
if s<=res[-1][1]: res[-1][1]=max(res[-1][1],e)
else: [Link]([s,e])
return res
# Jump game II (min jumps)
def jump(nums):
jumps=cur_end=far=0
for i in range(len(nums)-1):
far=max(far, i+nums[i])
if i==cur_end: jumps+=1; cur_end=far
return jumps
All patterns & syntax needed to crack DSA problems in Python
Python DSA Complete Reference Page 26
Trie
Trie Implementation
class TrieNode:
def __init__(self):
[Link] = {}
self.is_end = False
class Trie:
def __init__(self): [Link] = TrieNode()
def insert(self, word):
cur = [Link]
for c in word:
if c not in [Link]:
[Link][c] = TrieNode()
cur = [Link][c]
cur.is_end = True
def search(self, word):
cur = [Link]
for c in word:
if c not in [Link]: return False
cur = [Link][c]
return cur.is_end
def starts_with(self, prefix):
cur = [Link]
for c in prefix:
if c not in [Link]: return False
cur = [Link][c]
return True
All patterns & syntax needed to crack DSA problems in Python
Python DSA Complete Reference Page 27
Trie — Word Search & Count Prefix
# Word search with wildcard '.'
def search_wild(root, word, i=0):
if i == len(word): return root.is_end
c = word[i]
if c == '.':
return any(search_wild(child, word, i+1)
for child in [Link]())
if c not in [Link]: return False
return search_wild([Link][c], word, i+1)
# Count words with given prefix
def count_prefix(trie, prefix):
cur = [Link]
for c in prefix:
if c not in [Link]: return 0
cur = [Link][c]
def count(node):
total = 1 if node.is_end else 0
for child in [Link]():
total += count(child)
return total
return count(cur)
All patterns & syntax needed to crack DSA problems in Python