Stop grinding random problems. Learn these patterns and you'll recognize the solution path within minutes of reading a new problem.
Read the problem statement. Ask these questions in order. The first match is your starting point (not a guaranteed answer — you still need to think).
Use when you have a sorted array/list and need to find pairs, triplets, or subarrays satisfying some condition.
def two_sum_sorted(arr, target):
left, right = 0, len(arr) - 1
while left < right:
s = arr[left] + arr[right]
if s == target: return [left, right]
elif s < target: left += 1 # need bigger sum
else: right -= 1 # need smaller sum
return []
# [1, 3, 5, 7, 11], target=10 → left=1(3), right=3(7) → [1,3]Use when you need to find a contiguous subarray/substring that satisfies some constraint (length, sum, unique characters).
def longest_k_distinct(s, k):
counts = {}
left = best = 0
for right in range(len(s)):
counts[s[right]] = counts.get(s[right], 0) + 1
while len(counts) > k: # too many distinct chars
counts[s[left]] -= 1
if counts[s[left]] == 0: del counts[s[left]]
left += 1 # shrink window
best = max(best, right - left + 1)
return best
# "araaci", k=2 → "araa" → 4Use for cycle detection in linked lists or arrays, or finding the middle element in one pass.
def has_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next # 1 step
fast = fast.next.next # 2 steps
if slow == fast: # they met → cycle!
return True
return False # fast hit end → no cycleUse when the search space is sorted or monotonic and you can eliminate half of it with each step.
def min_eating_speed(piles, h):
# Can Koko eat all bananas at speed `k` within `h` hours?
def can_finish(k):
return sum((p + k - 1) // k for p in piles) <= h
lo, hi = 1, max(piles)
while lo < hi:
mid = (lo + hi) // 2
if can_finish(mid): hi = mid # try slower
else: lo = mid + 1 # need faster
return lo
# piles=[3,6,7,11], h=8 → speed=4Use for shortest path in unweighted graphs, level-order tree traversal, or anything where you need to explore all nodes at distance k before k+1.
from collections import deque
def shortest_path(grid):
rows, cols = len(grid), len(grid[0])
q = deque([(0, 0, 0)]) # row, col, distance
seen = {(0, 0)}
while q:
r, c, dist = q.popleft()
if r == rows-1 and c == cols-1: return dist
for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
nr, nc = r+dr, c+dc
if 0<=nrUse when you need to explore all possible paths/combinations/permutations, or when the problem has a recursive structure.
def subsets(nums):
result = []
def backtrack(start, current):
result.append(current[:]) # snapshot
for i in range(start, len(nums)):
current.append(nums[i]) # choose
backtrack(i + 1, current) # explore
current.pop() # un-choose
backtrack(0, [])
return result
# [1,2,3] → [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]Use when the problem has overlapping subproblems and optimal substructure — meaning the answer builds on answers to smaller versions of the same problem.
def coin_change(coins, amount):
dp = [float('inf')] * (amount + 1)
dp[0] = 0 # base: 0 coins to make $0
for a in range(1, amount + 1):
for coin in coins:
if coin <= a:
dp[a] = min(dp[a], dp[a - coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -1
# coins=[1,3,4], amount=6 → dp[6]=2 (3+3)Use when making the locally optimal choice at each step leads to the globally optimal solution. Often involves sorting first.
def max_meetings(intervals):
intervals.sort(key=lambda x: x[1]) # sort by END time
count = 0
last_end = -1
for start, end in intervals:
if start >= last_end: # no overlap
count += 1
last_end = end # greedily pick earliest-ending
return count
# [(0,3),(1,2),(3,5),(4,6)] → sorted by end: [(1,2),(0,3),(3,5),(4,6)] → pick 3Use when you need O(1) lookups, frequency counting, or finding complements/pairs.
def two_sum(nums, target):
seen = {} # value → index
for i, num in enumerate(nums):
complement = target - num
if complement in seen:
return [seen[complement], i]
seen[num] = i
# [2,7,11,15], target=9 → seen={2:0}, then 9-7=2 found → [0,1]Use when you need to find the next/previous greater/smaller element for each position, or anything involving "looking back" at a decreasing/increasing sequence.
def daily_temperatures(temps):
result = [0] * len(temps)
stack = [] # indices of days waiting for warmer
for i, t in enumerate(temps):
while stack and temps[stack[-1]] < t:
prev = stack.pop()
result[prev] = i - prev # days until warmer
stack.append(i)
return result
# [73,74,75,71,69,72,76,73] → [1,1,4,2,1,1,0,0]Use when you need the k largest/smallest/most frequent elements, or when you need to maintain a running median or sorted order in a stream.
import heapq
def kth_largest(nums, k):
heap = nums[:k]
heapq.heapify(heap) # min-heap of size k
for num in nums[k:]:
if num > heap[0]:
heapq.heapreplace(heap, num) # push+pop
return heap[0] # smallest of the k largest
# [3,2,1,5,6,4], k=2 → heap maintains [5,6] → return 5Use when you need to group/merge elements and quickly check if two elements are in the same group. Think connected components.
def find_redundant(edges):
parent = list(range(len(edges) + 1))
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]] # path compression
x = parent[x]
return x
for u, v in edges:
pu, pv = find(u), find(v)
if pu == pv: return [u, v] # already connected → redundant!
parent[pu] = pv # unionUse when dealing with string prefixes, autocomplete, or when you need efficient prefix matching across many strings.
startswith() in a loop, you probably want a 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 ch in word:
if ch not in node.children:
node.children[ch] = TrieNode()
node = node.children[ch]
node.is_end = True
def starts_with(self, prefix):
node = self.root
for ch in prefix:
if ch not in node.children: return False
node = node.children[ch]
return True # all prefix chars foundUse when the input is a list of intervals/ranges and you need to merge, insert, or find overlaps.
def merge_intervals(intervals):
intervals.sort()
merged = [intervals[0]]
for start, end in intervals[1:]:
if start <= merged[-1][1]: # overlaps
merged[-1][1] = max(merged[-1][1], end)
else:
merged.append([start, end])
return merged
# [[1,3],[2,6],[8,10],[15,18]] → [[1,6],[8,10],[15,18]]Use when you have dependencies between tasks and need to find a valid ordering, or detect if ordering is impossible (cycle).
from collections import deque, defaultdict
def can_finish(num_courses, prereqs):
graph = defaultdict(list)
in_degree = [0] * num_courses
for course, pre in prereqs:
graph[pre].append(course)
in_degree[course] += 1
q = deque(i for i in range(num_courses) if in_degree[i] == 0)
taken = 0
while q:
node = q.popleft()
taken += 1
for neighbor in graph[node]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
q.append(neighbor)
return taken == num_courses # took all courses?Use when you need to compute range sums quickly or find subarrays with a specific sum.
def subarray_sum(nums, k):
prefix_counts = {0: 1} # empty prefix has sum 0
running_sum = count = 0
for num in nums:
running_sum += num
# If (running_sum - k) was a previous prefix sum,
# the subarray between them sums to k
count += prefix_counts.get(running_sum - k, 0)
prefix_counts[running_sum] = prefix_counts.get(running_sum, 0) + 1
return count
# [1,1,1], k=2 → subarrays [1,1] at index 0-1 and 1-2 → 2Use when you need to work with binary representations, find unique elements, or when O(1) space is required for set-like operations.
a ^ a = 0 and a ^ 0 = a. If every element appears twice except one, XOR them all — the duplicates cancel out. Also: n & (n-1) removes the lowest set bit (useful for counting bits, power-of-two checks).
def single_number(nums):
result = 0
for num in nums:
result ^= num # duplicates cancel: a ^ a = 0
return result
# [4, 1, 2, 1, 2] → 4^1^2^1^2 = 4^(1^1)^(2^2) = 4^0^0 = 4Use when you need to find the maximum or minimum in a sliding window efficiently.
from collections import deque
def max_sliding_window(nums, k):
dq = deque() # indices, front = max
result = []
for i, num in enumerate(nums):
while dq and nums[dq[-1]] <= num:
dq.pop() # remove smaller — they'll never be max
dq.append(i)
if dq[0] <= i - k:
dq.popleft() # remove if outside window
if i >= k - 1:
result.append(nums[dq[0]]) # front = window max
return result
# [1,3,-1,-3,5,3,6,7], k=3 → [3,3,5,5,6,7]Use when you need to partition nodes into two groups where no two adjacent nodes share a group, or detect if such partitioning is possible.
from collections import deque
def is_bipartite(graph):
color = {}
for start in range(len(graph)):
if start in color: continue
q = deque([start])
color[start] = 0
while q:
node = q.popleft()
for neighbor in graph[node]:
if neighbor not in color:
color[neighbor] = 1 - color[node] # opposite color
q.append(neighbor)
elif color[neighbor] == color[node]:
return False # same color = not bipartite
return TrueUse when the input is a 2D grid and you need to explore regions, find paths, or count connected areas.
def num_islands(grid):
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: return
if 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) # sink the island
return count| When You See... | Think... | Complexity |
|---|---|---|
| "Sorted array" + "find pair" | Two Pointers | O(n) |
| "Contiguous subarray" + constraint | Sliding Window | O(n) |
| "Linked list" + "cycle" or "middle" | Fast & Slow Pointers | O(n) |
| "Sorted" + "search" + "O(log n)" | Binary Search | O(log n) |
| "Shortest path" (unweighted) | BFS | O(V+E) |
| "All combinations/permutations" | DFS / Backtracking | O(2ⁿ or n!) |
| "Minimum cost" + "number of ways" | Dynamic Programming | varies |
| "Schedule" + "intervals" | Greedy (sort by end time) | O(n log n) |
| "Frequency" + "O(1) lookup" | Hash Map | O(n) |
| "Next greater element" | Monotonic Stack | O(n) |
| "K largest" + "stream" | Heap | O(n log k) |
| "Connected components" | Union-Find or BFS/DFS | O(V+E) |
| "Prefix matching" + "dictionary" | Trie | O(word len) |
| "Merge overlapping" | Intervals (sort by start) | O(n log n) |
| "Order dependencies" | Topological Sort | O(V+E) |
| "Subarray sum equals K" | Prefix Sum + Hash Map | O(n) |
| "Single number" + "XOR" | Bit Manipulation | O(n) |
| "Max in sliding window" | Monotonic Deque | O(n) |
| "Two groups" + "no adjacent conflict" | Bipartite / Graph Coloring | O(V+E) |
| "Grid/matrix" + "explore regions" | Matrix BFS/DFS | O(m·n) |