DSA โ 56 Core Patterns with Complete Examples¶
Goal: Recognize the pattern first โ then code. 80% of interview problems = 20% of patterns. Every pattern below has: When to use + Example problem + Complete code + Complexity + Memory trick.
Memory Hook โ "TWO-SLIDE-FBI-DGT"¶
| Letter | Pattern Group |
|---|---|
| TWO | Two Pointers |
| SLIDE | Sliding Window |
| F | Fast & Slow Pointers |
| B | BFS |
| I | Intervals |
| D | Dynamic Programming |
| G | Graphs |
| T | Trees / Tries |
A) ARRAYS & STRINGS (Patterns 1-10)¶
1. Two Pointers¶
When: Sorted array, find a pair, palindrome check. Problem: Find pair that sums to target in sorted array.
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 [-1, -1]
# Example: two_sum_sorted([1,2,3,4,6], 6) โ [1, 3] (2+4)
2. Sliding Window (Fixed Size)¶
When: Max/min/avg of K consecutive elements. Problem: Max sum of subarray of size K.
def max_sum_k(arr, k):
window = sum(arr[:k])
best = window
for i in range(k, len(arr)):
window += arr[i] - arr[i - k]
best = max(best, window)
return best
# Example: max_sum_k([2,1,5,1,3,2], 3) โ 9 (5+1+3)
3. Sliding Window (Variable Size)¶
When: Longest/shortest substring with condition. Problem: Longest substring without repeating chars.
def longest_unique(s):
seen = {}
l = best = 0
for r, ch in enumerate(s):
if ch in seen and seen[ch] >= l:
l = seen[ch] + 1
seen[ch] = r
best = max(best, r - l + 1)
return best
# Example: longest_unique("abcabcbb") โ 3 ("abc")
4. Prefix Sum¶
When: Many range-sum queries on same array. Problem: Sum from index i to j.
def build_prefix(arr):
prefix = [0]
for n in arr:
prefix.append(prefix[-1] + n)
return prefix
def range_sum(prefix, i, j):
return prefix[j + 1] - prefix[i]
# Example:
# arr = [3, 1, 4, 1, 5, 9, 2, 6]
# prefix = build_prefix(arr) โ [0, 3, 4, 8, 9, 14, 23, 25, 31]
# range_sum(prefix, 2, 5) โ 19 (4+1+5+9)
5. Kadane's Algorithm (Max Subarray Sum)¶
When: Maximum sum of a contiguous subarray (can have negatives). Problem: Find max sum subarray.
def max_subarray(arr):
cur = best = arr[0]
for n in arr[1:]:
cur = max(n, cur + n)
best = max(best, cur)
return best
# Example: max_subarray([-2,1,-3,4,-1,2,1,-5,4]) โ 6 ([4,-1,2,1])
6. Dutch National Flag (3-way Partition)¶
When: Sort 0s, 1s, 2s in one pass without extra space. Problem: Sort array of 0/1/2 in-place.
def sort_012(arr):
low, mid, high = 0, 0, len(arr) - 1
while mid <= high:
if arr[mid] == 0:
arr[low], arr[mid] = arr[mid], arr[low]
low += 1; mid += 1
elif arr[mid] == 1:
mid += 1
else: # arr[mid] == 2
arr[mid], arr[high] = arr[high], arr[mid]
high -= 1
return arr
# Example: sort_012([2,0,2,1,1,0]) โ [0,0,1,1,2,2]
7. Merge Intervals¶
When: Overlapping intervals (meetings, ranges). Problem: Merge all overlapping intervals.
def merge_intervals(intervals):
intervals.sort(key=lambda x: x[0])
out = [intervals[0]]
for s, e in intervals[1:]:
if s <= out[-1][1]:
out[-1][1] = max(out[-1][1], e)
else:
out.append([s, e])
return out
# Example: merge_intervals([[1,3],[2,6],[8,10],[15,18]])
# โ [[1,6],[8,10],[15,18]]
8. Cyclic Sort¶
When: Array contains numbers from 1 to N (or 0 to N-1). Problem: Sort in O(N) without extra space.
def cyclic_sort(arr):
i = 0
while i < len(arr):
correct = arr[i] - 1 # for 1..N
if arr[i] != arr[correct]:
arr[i], arr[correct] = arr[correct], arr[i]
else:
i += 1
return arr
# Example: cyclic_sort([3,1,5,4,2]) โ [1,2,3,4,5]
# Find missing number variant:
def find_missing(arr): # arr contains 0..N with one missing
i = 0
while i < len(arr):
if arr[i] < len(arr) and arr[i] != arr[arr[i]]:
arr[arr[i]], arr[i] = arr[i], arr[arr[i]]
else:
i += 1
for i, n in enumerate(arr):
if i != n:
return i
return len(arr)
# Example: find_missing([3,0,1]) โ 2
9. Reverse In-place (Array / String)¶
When: Reverse without extra memory. Problem: Reverse array / rotate by K.
def reverse(arr, l, r):
while l < r:
arr[l], arr[r] = arr[r], arr[l]
l += 1; r -= 1
def rotate(arr, k):
n = len(arr)
k %= n
reverse(arr, 0, n - 1)
reverse(arr, 0, k - 1)
reverse(arr, k, n - 1)
return arr
# Example: rotate([1,2,3,4,5,6,7], 3) โ [5,6,7,1,2,3,4]
10. Anagram Grouping¶
When: Group strings that are anagrams of each other. Problem: Group anagrams together.
from collections import defaultdict
def group_anagrams(strs):
groups = defaultdict(list)
for s in strs:
key = ''.join(sorted(s)) # signature
groups[key].append(s)
return list(groups.values())
# Example: group_anagrams(["eat","tea","tan","ate","nat","bat"])
# โ [["eat","tea","ate"],["tan","nat"],["bat"]]
B) HASHING / FREQUENCY (Patterns 11-15)¶
11. HashMap Frequency Count¶
When: Find first non-repeating, most frequent, etc. Problem: First non-repeating character.
from collections import Counter
def first_unique_char(s):
freq = Counter(s)
for i, ch in enumerate(s):
if freq[ch] == 1:
return i
return -1
# Example: first_unique_char("leetcode") โ 0 ('l')
# Example: first_unique_char("loveleetcode") โ 2 ('v')
12. Two Sum (Unsorted)¶
When: Find pair summing to target in unsorted array.
def two_sum(arr, target):
seen = {}
for i, n in enumerate(arr):
if target - n in seen:
return [seen[target - n], i]
seen[n] = i
return [-1, -1]
# Example: two_sum([2,7,11,15], 9) โ [0, 1]
13. Subarray Sum equals K (Prefix Sum + HashMap)¶
When: Count subarrays whose sum equals K (can have negatives).
from collections import defaultdict
def subarray_sum_k(arr, k):
count = 0
cur_sum = 0
prefix_count = defaultdict(int)
prefix_count[0] = 1 # empty prefix
for n in arr:
cur_sum += n
count += prefix_count[cur_sum - k]
prefix_count[cur_sum] += 1
return count
# Example: subarray_sum_k([1,1,1], 2) โ 2 ([1,1] twice)
# Example: subarray_sum_k([1,2,3], 3) โ 2 ([1,2] and [3])
14. Longest Consecutive Sequence¶
When: Find longest sequence of consecutive numbers (unsorted).
def longest_consecutive(arr):
nums = set(arr)
best = 0
for n in nums:
if n - 1 not in nums: # only start at sequence head
length = 1
while n + length in nums:
length += 1
best = max(best, length)
return best
# Example: longest_consecutive([100,4,200,1,3,2]) โ 4 ([1,2,3,4])
15. LRU Cache (HashMap + Doubly Linked List)¶
When: Cache that evicts least recently used item.
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity):
self.cap = capacity
self.cache = OrderedDict()
def get(self, key):
if key not in self.cache:
return -1
self.cache.move_to_end(key) # mark as recently used
return self.cache[key]
def put(self, key, value):
if key in self.cache:
self.cache.move_to_end(key)
self.cache[key] = value
if len(self.cache) > self.cap:
self.cache.popitem(last=False) # evict oldest
# Example:
# cache = LRUCache(2)
# cache.put(1, 1); cache.put(2, 2); cache.get(1) โ 1
# cache.put(3, 3) # evicts key 2
# cache.get(2) โ -1
C) LINKED LISTS (Patterns 16-20)¶
16. Fast & Slow Pointer (Floyd's Cycle Detection)¶
When: Detect cycle in linked list.
class Node:
def __init__(self, val=0, next=None):
self.val = val; self.next = next
def has_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
def cycle_start(head): # Find node where cycle begins
slow = fast = head
while fast and fast.next:
slow = slow.next; fast = fast.next.next
if slow == fast:
break
else:
return None
slow = head
while slow != fast:
slow = slow.next; fast = fast.next
return slow
17. Reverse Linked List¶
When: Reverse entire or part of linked list.
def reverse_list(head):
prev = None
while head:
nxt = head.next
head.next = prev
prev = head
head = nxt
return prev
# Recursive version
def reverse_rec(head):
if not head or not head.next:
return head
new_head = reverse_rec(head.next)
head.next.next = head
head.next = None
return new_head
18. Merge Two Sorted Linked Lists¶
When: Merge two sorted lists into one.
def merge_two(l1, l2):
dummy = Node(0)
tail = dummy
while l1 and l2:
if l1.val <= l2.val:
tail.next = l1; l1 = l1.next
else:
tail.next = l2; l2 = l2.next
tail = tail.next
tail.next = l1 or l2
return dummy.next
# Example: 1โ3โ5 merged with 2โ4โ6 โ 1โ2โ3โ4โ5โ6
19. Find Middle of Linked List (Slow/Fast)¶
When: Get middle node in one pass.
def find_middle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow
# Example: 1โ2โ3โ4โ5 โ returns node with val 3
# Example: 1โ2โ3โ4 โ returns node with val 3 (second middle)
20. Remove Nth Node from End¶
When: Delete nth-from-last in one pass (two pointers, N gap).
def remove_nth_from_end(head, n):
dummy = Node(0, head)
fast = slow = dummy
for _ in range(n):
fast = fast.next
while fast.next:
fast = fast.next
slow = slow.next
slow.next = slow.next.next
return dummy.next
# Example: 1โ2โ3โ4โ5, n=2 โ 1โ2โ3โ5
D) STACK & QUEUE (Patterns 21-25)¶
21. Monotonic Stack¶
When: "Next greater / smaller element", histogram problems.
def next_greater(arr):
res = [-1] * len(arr)
stack = [] # stores indices
for i, n in enumerate(arr):
while stack and arr[stack[-1]] < n:
res[stack.pop()] = n
stack.append(i)
return res
# Example: next_greater([2,1,2,4,3]) โ [4,2,4,-1,-1]
22. Valid Parentheses¶
When: Check matching brackets ()[]{}.
def is_valid(s):
stack = []
pairs = {')': '(', ']': '[', '}': '{'}
for ch in s:
if ch in '([{':
stack.append(ch)
else:
if not stack or stack.pop() != pairs[ch]:
return False
return not stack
# Example: is_valid("()[]{}") โ True
# Example: is_valid("(]") โ False
23. Min Stack (Track min in O(1))¶
When: Stack with getMin() in O(1).
class MinStack:
def __init__(self):
self.stack = []
self.min_stack = [] # parallel stack of running min
def push(self, x):
self.stack.append(x)
if not self.min_stack or x <= self.min_stack[-1]:
self.min_stack.append(x)
def pop(self):
x = self.stack.pop()
if x == self.min_stack[-1]:
self.min_stack.pop()
def top(self):
return self.stack[-1]
def get_min(self):
return self.min_stack[-1]
24. Queue using Two Stacks¶
When: Implement FIFO using only LIFO ops.
class MyQueue:
def __init__(self):
self.in_st = []
self.out_st = []
def push(self, x):
self.in_st.append(x)
def _shift(self):
if not self.out_st:
while self.in_st:
self.out_st.append(self.in_st.pop())
def pop(self):
self._shift()
return self.out_st.pop()
def peek(self):
self._shift()
return self.out_st[-1]
def empty(self):
return not self.in_st and not self.out_st
25. Sliding Window Maximum (Monotonic Deque)¶
When: Max in every window of size K.
from collections import deque
def max_sliding_window(arr, k):
dq = deque() # stores indices, values decreasing
res = []
for i, n in enumerate(arr):
while dq and dq[0] <= i - k: # out of window
dq.popleft()
while dq and arr[dq[-1]] < n: # maintain decreasing
dq.pop()
dq.append(i)
if i >= k - 1:
res.append(arr[dq[0]])
return res
# Example: max_sliding_window([1,3,-1,-3,5,3,6,7], 3)
# โ [3,3,5,5,6,7]
E) TREES (Patterns 26-32)¶
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val; self.left = left; self.right = right
26. DFS Traversals (Inorder, Preorder, Postorder)¶
def inorder(root): # Left โ Root โ Right
if not root: return []
return inorder(root.left) + [root.val] + inorder(root.right)
def preorder(root): # Root โ Left โ Right
if not root: return []
return [root.val] + preorder(root.left) + preorder(root.right)
def postorder(root): # Left โ Right โ Root
if not root: return []
return postorder(root.left) + postorder(root.right) + [root.val]
# Iterative inorder
def inorder_iter(root):
res, stack = [], []
cur = root
while cur or stack:
while cur:
stack.append(cur); cur = cur.left
cur = stack.pop()
res.append(cur.val)
cur = cur.right
return res
27. BFS / Level Order Traversal¶
from collections import deque
def level_order(root):
if not root: return []
q = deque([root])
res = []
while q:
level = []
for _ in range(len(q)):
node = q.popleft()
level.append(node.val)
if node.left: q.append(node.left)
if node.right: q.append(node.right)
res.append(level)
return res
# Example tree: 1
# / \
# 2 3
# / \
# 4 5
# level_order(root) โ [[1],[2,3],[4,5]]
28. Diameter of Binary Tree¶
When: Longest path between any two nodes (may not pass through root).
def diameter(root):
best = [0]
def depth(node):
if not node: return 0
l = depth(node.left)
r = depth(node.right)
best[0] = max(best[0], l + r)
return 1 + max(l, r)
depth(root)
return best[0]
# Diameter = max(left_depth + right_depth) across all nodes
29. Lowest Common Ancestor (LCA) โ Binary Tree¶
def lca(root, p, q):
if not root or root == p or root == q:
return root
left = lca(root.left, p, q)
right = lca(root.right, p, q)
if left and right:
return root
return left or right
# Example: For tree 3
# / \
# 5 1
# / \ / \
# 6 2 0 8
# lca(root, 5, 1) โ 3
# lca(root, 5, 4) โ 5
30. Validate BST (Min/Max Bounds)¶
def is_valid_bst(root, low=float('-inf'), high=float('inf')):
if not root:
return True
if not (low < root.val < high):
return False
return (is_valid_bst(root.left, low, root.val) and
is_valid_bst(root.right, root.val, high))
# Example BST: 5
# / \
# 1 7
# / \
# 6 8
# is_valid_bst(root) โ True
31. Serialize / Deserialize Binary Tree (BFS)¶
from collections import deque
def serialize(root):
if not root: return ""
q = deque([root])
res = []
while q:
node = q.popleft()
if node:
res.append(str(node.val))
q.append(node.left); q.append(node.right)
else:
res.append("#")
return ",".join(res)
def deserialize(data):
if not data: return None
vals = data.split(",")
root = TreeNode(int(vals[0]))
q = deque([root]); i = 1
while q and i < len(vals):
node = q.popleft()
if vals[i] != "#":
node.left = TreeNode(int(vals[i])); q.append(node.left)
i += 1
if i < len(vals) and vals[i] != "#":
node.right = TreeNode(int(vals[i])); q.append(node.right)
i += 1
return root
# Example: tree [1,2,3,null,null,4,5] โ "1,2,3,#,#,4,5,#,#,#,#"
32. Path Sum (Root to Leaf)¶
def has_path_sum(root, target):
if not root:
return False
if not root.left and not root.right:
return root.val == target
return (has_path_sum(root.left, target - root.val) or
has_path_sum(root.right, target - root.val))
# Count all paths (anywhere โ anywhere going down) summing to K
def path_sum_count(root, k):
from collections import defaultdict
count = [0]
prefix = defaultdict(int)
prefix[0] = 1
def dfs(node, cur_sum):
if not node: return
cur_sum += node.val
count[0] += prefix[cur_sum - k]
prefix[cur_sum] += 1
dfs(node.left, cur_sum); dfs(node.right, cur_sum)
prefix[cur_sum] -= 1
dfs(root, 0)
return count[0]
F) HEAP / PRIORITY QUEUE (Patterns 33-36)¶
33. Top K Elements (Min-Heap of size K)¶
import heapq
def top_k_largest(nums, k):
return heapq.nlargest(k, nums)
# Manual min-heap approach
def top_k(nums, k):
heap = []
for n in nums:
heapq.heappush(heap, n)
if len(heap) > k:
heapq.heappop(heap)
return heap
# Example: top_k_largest([3,2,1,5,6,4], 2) โ [6, 5]
34. K Closest Points to Origin¶
import heapq
def k_closest(points, k):
heap = []
for x, y in points:
dist = -(x*x + y*y) # negate for max-heap behavior
heapq.heappush(heap, (dist, x, y))
if len(heap) > k:
heapq.heappop(heap)
return [[x, y] for _, x, y in heap]
# Example: k_closest([[1,3],[-2,2],[5,8]], 2) โ [[1,3],[-2,2]]
35. Merge K Sorted Lists¶
import heapq
def merge_k_lists(lists):
heap = []
for i, node in enumerate(lists):
if node:
heapq.heappush(heap, (node.val, i, node))
dummy = Node(0); tail = dummy
while heap:
val, i, node = heapq.heappop(heap)
tail.next = node; tail = node
if node.next:
heapq.heappush(heap, (node.next.val, i, node.next))
return dummy.next
# Example: merge_k_lists([1โ4โ5, 1โ3โ4, 2โ6]) โ 1โ1โ2โ3โ4โ4โ5โ6
36. Median from Data Stream (Two Heaps)¶
import heapq
class MedianFinder:
def __init__(self):
self.low = [] # max-heap (negate values)
self.high = [] # min-heap
def add(self, num):
heapq.heappush(self.low, -num)
heapq.heappush(self.high, -heapq.heappop(self.low))
if len(self.high) > len(self.low):
heapq.heappush(self.low, -heapq.heappop(self.high))
def median(self):
if len(self.low) > len(self.high):
return -self.low[0]
return (-self.low[0] + self.high[0]) / 2
# Example:
# m = MedianFinder()
# m.add(1); m.add(2); m.median() โ 1.5
# m.add(3); m.median() โ 2
G) BACKTRACKING (Patterns 37-40)¶
37. Subsets (Power Set)¶
def subsets(nums):
res = []
def backtrack(start, path):
res.append(path[:])
for i in range(start, len(nums)):
path.append(nums[i])
backtrack(i + 1, path)
path.pop()
backtrack(0, [])
return res
# Example: subsets([1,2,3])
# โ [[],[1],[1,2],[1,2,3],[1,3],[2],[2,3],[3]]
38. Permutations¶
def permutations(nums):
res = []
def backtrack(path, used):
if len(path) == len(nums):
res.append(path[:]); return
for i in range(len(nums)):
if used[i]: continue
used[i] = True; path.append(nums[i])
backtrack(path, used)
path.pop(); used[i] = False
backtrack([], [False] * len(nums))
return res
# Example: permutations([1,2,3])
# โ [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
39. Combination Sum (Element can be reused)¶
def combination_sum(candidates, target):
res = []
def backtrack(start, path, remaining):
if remaining == 0:
res.append(path[:]); return
if remaining < 0: return
for i in range(start, len(candidates)):
path.append(candidates[i])
backtrack(i, path, remaining - candidates[i]) # i (not i+1) for reuse
path.pop()
backtrack(0, [], target)
return res
# Example: combination_sum([2,3,6,7], 7)
# โ [[2,2,3],[7]]
40. N-Queens¶
def solve_n_queens(n):
res = []
cols, diag1, diag2 = set(), set(), set()
board = [['.'] * n for _ in range(n)]
def backtrack(r):
if r == n:
res.append([''.join(row) for row in board]); return
for c in range(n):
if c in cols or (r-c) in diag1 or (r+c) in diag2:
continue
cols.add(c); diag1.add(r-c); diag2.add(r+c)
board[r][c] = 'Q'
backtrack(r + 1)
cols.remove(c); diag1.remove(r-c); diag2.remove(r+c)
board[r][c] = '.'
backtrack(0)
return res
# Example: solve_n_queens(4) โ 2 solutions
H) DYNAMIC PROGRAMMING (Patterns 41-46)¶
41. Fibonacci-style (1D DP)¶
def fib(n):
if n < 2: return n
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
return a
# Climbing stairs (same pattern):
def climb_stairs(n):
if n <= 2: return n
a, b = 1, 2
for _ in range(3, n + 1):
a, b = b, a + b
return b
# Example: climb_stairs(5) โ 8
42. 0/1 Knapsack¶
def knapsack(weights, values, capacity):
n = len(weights)
dp = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for w in range(capacity + 1):
dp[i][w] = dp[i-1][w] # skip item
if weights[i-1] <= w:
dp[i][w] = max(dp[i][w],
dp[i-1][w - weights[i-1]] + values[i-1])
return dp[n][capacity]
# Example: knapsack([1,3,4,5], [1,4,5,7], 7) โ 9 (items 1+3=weight 4, value 5+4=9? actually 1+3+? let's check: w=[1,3,4],v=[1,4,5] sum w=8 too big. Best: items with w=3,4 โ values 4+5=9)
43. Longest Common Subsequence (LCS)¶
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]
# Example: lcs("abcde", "ace") โ 3 ("ace")
44. Longest Increasing Subsequence (LIS)¶
# O(N^2) DP version
def lis_dp(arr):
if not arr: return 0
n = len(arr)
dp = [1] * n
for i in range(1, n):
for j in range(i):
if arr[j] < arr[i]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
# O(N log N) with binary search (patience sort)
import bisect
def lis_fast(arr):
tails = []
for n in arr:
idx = bisect.bisect_left(tails, n)
if idx == len(tails):
tails.append(n)
else:
tails[idx] = n
return len(tails)
# Example: lis_fast([10,9,2,5,3,7,101,18]) โ 4 ([2,3,7,101])
45. Coin Change (Unbounded Knapsack)¶
def coin_change(coins, amount):
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for a in range(1, amount + 1):
for c in coins:
if c <= a:
dp[a] = min(dp[a], dp[a - c] + 1)
return dp[amount] if dp[amount] != float('inf') else -1
# Example: coin_change([1,2,5], 11) โ 3 (5+5+1)
46. Edit Distance (Levenshtein)¶
def edit_distance(s1, s2):
m, n = len(s1), len(s2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m + 1): dp[i][0] = i
for j in range(n + 1): dp[0][j] = j
for i in range(1, m + 1):
for j in range(1, n + 1):
if s1[i-1] == s2[j-1]:
dp[i][j] = dp[i-1][j-1]
else:
dp[i][j] = 1 + min(
dp[i-1][j], # delete
dp[i][j-1], # insert
dp[i-1][j-1] # replace
)
return dp[m][n]
# Example: edit_distance("horse", "ros") โ 3
I) GRAPHS (Patterns 47-52)¶
47. BFS on Graph¶
from collections import deque
def bfs(graph, start):
visited = {start}
q = deque([start])
order = []
while q:
node = q.popleft()
order.append(node)
for nb in graph[node]:
if nb not in visited:
visited.add(nb)
q.append(nb)
return order
# Example: graph = {1:[2,3], 2:[4], 3:[4], 4:[]}
# bfs(graph, 1) โ [1, 2, 3, 4]
48. DFS on Graph (Recursive + Iterative)¶
# Recursive
def dfs(graph, node, visited=None):
if visited is None: visited = set()
visited.add(node)
order = [node]
for nb in graph[node]:
if nb not in visited:
order += dfs(graph, nb, visited)
return order
# Iterative
def dfs_iter(graph, start):
visited = set()
stack = [start]
order = []
while stack:
node = stack.pop()
if node in visited: continue
visited.add(node)
order.append(node)
for nb in graph[node]:
if nb not in visited:
stack.append(nb)
return order
# Example: graph = {1:[2,3], 2:[4], 3:[4], 4:[]}
# dfs(graph, 1) โ [1, 2, 4, 3]
49. Topological Sort (Kahn's BFS)¶
from collections import deque, defaultdict
def topo_sort(num_nodes, edges):
graph = defaultdict(list)
indegree = [0] * num_nodes
for u, v in edges: # edge u โ v means u must come before v
graph[u].append(v)
indegree[v] += 1
q = deque([i for i in range(num_nodes) if indegree[i] == 0])
order = []
while q:
node = q.popleft()
order.append(node)
for nb in graph[node]:
indegree[nb] -= 1
if indegree[nb] == 0:
q.append(nb)
return order if len(order) == num_nodes else [] # [] = has cycle
# Example (Course Schedule):
# topo_sort(4, [[1,0],[2,0],[3,1],[3,2]]) โ [0,1,2,3] or [0,2,1,3]
50. Union-Find (Disjoint Set Union โ DSU)¶
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
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
# Example: detect cycle in undirected graph
def has_cycle_undirected(n, edges):
uf = UnionFind(n)
for u, v in edges:
if not uf.union(u, v):
return True
return False
51. Dijkstra (Shortest Path, weighted, no negatives)¶
import heapq
def dijkstra(graph, start):
# graph: {node: [(neighbor, weight), ...]}
dist = {node: float('inf') for node in graph}
dist[start] = 0
heap = [(0, start)]
while heap:
d, node = heapq.heappop(heap)
if d > dist[node]: continue
for nb, w in graph[node]:
new_d = d + w
if new_d < dist[nb]:
dist[nb] = new_d
heapq.heappush(heap, (new_d, nb))
return dist
# Example:
# graph = {'A':[('B',1),('C',4)], 'B':[('C',2),('D',5)], 'C':[('D',1)], 'D':[]}
# dijkstra(graph, 'A') โ {'A':0, 'B':1, 'C':3, 'D':4}
52. Number of Islands (DFS on Grid)¶
def num_islands(grid):
if not grid: return 0
rows, cols = len(grid), len(grid[0])
count = 0
def dfs(r, c):
if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != '1':
return
grid[r][c] = '0' # mark visited
dfs(r+1, c); dfs(r-1, c); dfs(r, c+1); dfs(r, c-1)
for r in range(rows):
for c in range(cols):
if grid[r][c] == '1':
count += 1
dfs(r, c)
return count
# Example:
# grid = [['1','1','0','0'],
# ['1','1','0','0'],
# ['0','0','1','0'],
# ['0','0','0','1']]
# num_islands(grid) โ 3
J) BIT MANIPULATION + BINARY SEARCH (Patterns 53-56)¶
53. XOR โ Find Single Unique Number¶
def single_number(arr):
# All numbers appear twice except one. Find it.
result = 0
for n in arr:
result ^= n # XOR cancels duplicates
return result
# Example: single_number([4,1,2,1,2]) โ 4
x ^ x = 0, x ^ 0 = x. Duplicates cancel.
54. Count Set Bits (Hamming Weight)¶
def count_bits(n):
count = 0
while n:
n &= (n - 1) # clears the lowest set bit
count += 1
return count
# Example: count_bits(11) โ 3 (binary: 1011)
# Brian Kernighan's trick โ faster than checking each bit
55. Binary Search (and Variants)¶
# Classic Binary Search
def binary_search(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
# First occurrence of target
def first_occurrence(arr, target):
l, r, res = 0, len(arr) - 1, -1
while l <= r:
m = (l + r) // 2
if arr[m] == target:
res = m; r = m - 1 # keep going left
elif arr[m] < target: l = m + 1
else: r = m - 1
return res
# Last occurrence
def last_occurrence(arr, target):
l, r, res = 0, len(arr) - 1, -1
while l <= r:
m = (l + r) // 2
if arr[m] == target:
res = m; l = m + 1 # keep going right
elif arr[m] < target: l = m + 1
else: r = m - 1
return res
# Example:
# binary_search([1,3,5,7,9], 5) โ 2
# first_occurrence([1,2,2,2,3], 2) โ 1
# last_occurrence([1,2,2,2,3], 2) โ 3
56. Search in Rotated Sorted Array¶
def search_rotated(arr, target):
l, r = 0, len(arr) - 1
while l <= r:
m = (l + r) // 2
if arr[m] == target: return m
# Determine which half is sorted
if arr[l] <= arr[m]: # left half sorted
if arr[l] <= target < arr[m]:
r = m - 1
else:
l = m + 1
else: # right half sorted
if arr[m] < target <= arr[r]:
l = m + 1
else:
r = m - 1
return -1
# Example: search_rotated([4,5,6,7,0,1,2], 0) โ 4
# Example: search_rotated([4,5,6,7,0,1,2], 3) โ -1
QUICK PATTERN-RECOGNITION TABLE¶
| Problem says... | Pattern # | Pattern |
|---|---|---|
| "Sorted array, find pair" | 1 | Two Pointers |
| "Longest/shortest substring" | 3 | Variable Sliding Window |
| "Max sum of K consecutive" | 2 | Fixed Sliding Window |
| "Range sum queries" | 4 | Prefix Sum |
| "Max subarray sum" | 5 | Kadane |
| "Sort 0s, 1s, 2s" | 6 | Dutch Flag |
| "Overlapping intervals" | 7 | Merge Intervals |
| "Numbers 1..N, find missing" | 8 | Cyclic Sort |
| "Rotate array" | 9 | Reverse trick |
| "Group anagrams" | 10 | Hash by signature |
| "First non-repeating" | 11 | Counter |
| "Pair sum (unsorted)" | 12 | HashMap two-sum |
| "Subarray sum = K" | 13 | Prefix + HashMap |
| "Longest consecutive sequence" | 14 | Set lookup |
| "Cache eviction" | 15 | LRU |
| "Cycle in linked list" | 16 | Fast & Slow |
| "Reverse linked list" | 17 | Iterative prev/next |
| "Merge sorted lists" | 18, 35 | Dummy + Heap |
| "Middle of list" | 19 | Slow/Fast |
| "Remove nth from end" | 20 | Two pointers w/ gap |
| "Next greater element" | 21 | Monotonic Stack |
| "Valid brackets" | 22 | Stack |
| "Stack with getMin" | 23 | Parallel min stack |
| "Sliding window max" | 25 | Monotonic Deque |
| "Tree traversal" | 26, 27 | DFS / BFS |
| "Longest path in tree" | 28 | DFS + global max |
| "Common ancestor" | 29 | LCA recursion |
| "Is it a BST?" | 30 | Min/max bounds |
| "Top K / K largest" | 33 | Heap |
| "K closest" | 34 | Heap with distance |
| "Stream median" | 36 | Two heaps |
| "All subsets/permutations" | 37, 38 | Backtracking |
| "Combination sum" | 39 | Backtracking + reuse |
| "Place N items, no conflict" | 40 | Backtracking (N-Queens) |
| "Number of ways to..." | 41-45 | DP |
| "Min cost / max value" | 42, 45 | Knapsack DP |
| "String similarity" | 43, 46 | 2D DP |
| "Increasing sequence" | 44 | LIS |
| "Connected components" | 47, 50 | BFS/DFS or Union-Find |
| "Course schedule / order" | 49 | Topological Sort |
| "Shortest path (weighted)" | 51 | Dijkstra |
| "Grid problems" | 52 | DFS/BFS on grid |
| "Unique among duplicates" | 53 | XOR |
| "Sorted array, search" | 55 | Binary Search |
| "Rotated sorted array" | 56 | Modified Binary Search |
30-DAY PRACTICE PLAN¶
| Days | Patterns | Topic |
|---|---|---|
| 1-3 | 1-5 | Two Pointers, Sliding Window, Prefix Sum, Kadane |
| 4-5 | 6-10 | Dutch Flag, Intervals, Cyclic Sort, Reverse, Anagrams |
| 6-8 | 11-15 | Hashing, LRU Cache |
| 9-11 | 16-20 | Linked Lists |
| 12-14 | 21-25 | Stack & Queue |
| 15-18 | 26-32 | Trees |
| 19-20 | 33-36 | Heaps |
| 21-23 | 37-40 | Backtracking |
| 24-26 | 41-46 | DP |
| 27-29 | 47-52 | Graphs |
| 30 | 53-56 | Bit / Binary Search + Revision |
Rule: For each pattern, solve 2 easy + 1 medium on LeetCode using the template above. Don't peek โ apply the pattern first.