15 Essential LeetCode Patterns
15 Essential LeetCode Patterns
1. Prefix Sum
Concept: Precompute cumulative sums to answer range sum queries in O(1) time.
When to use:
- Range sum queries
- Subarray sum problems
- Finding equilibrium index
How it works:
Array: [1, 2, 3, 4, 5, 6]
Prefix Sum: [1, 3, 6, 10, 15, 21]
Sum of range [i, j] = prefix[j] - prefix[i-1]
Code:
1def build_prefix_sum(nums):
2 prefix = [0] * len(nums)
3 prefix[0] = nums[0]
4 for i in range(1, len(nums)):
5 prefix[i] = prefix[i-1] + nums[i]
6 return prefix
7
8def range_sum(prefix, left, right):
9 if left == 0:
10 return prefix[right]
11 return prefix[right] - prefix[left - 1]
Complexity: O(n) preprocessing, O(1) query
2. Two Pointers
Concept: Use two pointers moving toward each other or in the same direction.
When to use:
- Sorted array problems
- Palindrome checking
- Pair finding (two sum in sorted array)
- Removing duplicates
Patterns:
- Opposite ends moving inward
- Same direction (fast/slow)
Code:
1def two_sum_sorted(nums, target):
2 left, right = 0, len(nums) - 1
3
4 while left < right:
5 current_sum = nums[left] + nums[right]
6 if current_sum == target:
7 return [left, right]
8 elif current_sum < target:
9 left += 1
10 else:
11 right -= 1
12 return [-1, -1]
Complexity: O(n) time, O(1) space
3. Sliding Window
Concept: Maintain a window that slides through the array/string.
When to use:
- Subarray/substring problems
- Maximum/minimum in fixed window
- Longest/shortest with constraint
Types:
- Fixed size window
- Variable size window
Code:
1# Fixed window - max sum of k consecutive elements
2def max_sum_k_elements(nums, k):
3 window_sum = sum(nums[:k])
4 max_sum = window_sum
5
6 for i in range(k, len(nums)):
7 window_sum = window_sum - nums[i - k] + nums[i]
8 max_sum = max(max_sum, window_sum)
9
10 return max_sum
11
12# Variable window - longest substring without repeating chars
13def length_of_longest_substring(s):
14 char_set = set()
15 left = 0
16 max_length = 0
17
18 for right in range(len(s)):
19 while s[right] in char_set:
20 char_set.remove(s[left])
21 left += 1
22 char_set.add(s[right])
23 max_length = max(max_length, right - left + 1)
24
25 return max_length
Complexity: O(n) time, O(k) space
4. Fast & Slow Pointers
Concept: Two pointers moving at different speeds (tortoise and hare).
When to use:
- Cycle detection in linked list
- Finding middle of linked list
- Finding cycle start point
- Happy number problem
Code:
1class ListNode:
2 def __init__(self, val=0, next=None):
3 self.val = val
4 self.next = next
5
6def has_cycle(head):
7 if not head:
8 return False
9
10 slow = fast = head
11
12 while fast and fast.next:
13 slow = slow.next
14 fast = fast.next.next
15 if slow == fast:
16 return True
17
18 return False
19
20def find_middle(head):
21 slow = fast = head
22
23 while fast and fast.next:
24 slow = slow.next
25 fast = fast.next.next
26
27 return slow
Complexity: O(n) time, O(1) space
5. LinkedList In-place Reversal
Concept: Reverse links in a linked list without extra space.
When to use:
- Reverse entire linked list
- Reverse sublist
- Reverse k-group nodes
Code:
1def reverse_list(head):
2 prev = None
3 current = head
4
5 while current:
6 next_node = current.next
7 current.next = prev
8 prev = current
9 current = next_node
10
11 return prev
12
13def reverse_between(head, left, right):
14 if not head or left == right:
15 return head
16
17 dummy = ListNode(0)
18 dummy.next = head
19 prev = dummy
20
21 # Move to position before left
22 for _ in range(left - 1):
23 prev = prev.next
24
25 # Reverse sublist
26 current = prev.next
27 for _ in range(right - left):
28 next_node = current.next
29 current.next = next_node.next
30 next_node.next = prev.next
31 prev.next = next_node
32
33 return dummy.next
Complexity: O(n) time, O(1) space
6. Monotonic Stack
Concept: Maintain a stack where elements are in increasing or decreasing order.
When to use:
- Next greater/smaller element
- Stock span problem
- Histogram area problems
- Temperature problems
Code:
1def next_greater_elements(nums):
2 result = [-1] * len(nums)
3 stack = [] # stores indices
4
5 for i in range(len(nums)):
6 while stack and nums[i] > nums[stack[-1]]:
7 index = stack.pop()
8 result[index] = nums[i]
9 stack.append(i)
10
11 return result
12
13def daily_temperatures(temperatures):
14 result = [0] * len(temperatures)
15 stack = []
16
17 for i in range(len(temperatures)):
18 while stack and temperatures[i] > temperatures[stack[-1]]:
19 prev_index = stack.pop()
20 result[prev_index] = i - prev_index
21 stack.append(i)
22
23 return result
Complexity: O(n) time, O(n) space
7. Top ‘K’ Elements
Concept: Use a heap (min-heap or max-heap) to track K largest/smallest elements.
When to use:
- K largest/smallest elements
- K most frequent elements
- Kth largest element
Code:
1import heapq
2
3def find_k_largest(nums, k):
4 # Use min heap of size k
5 min_heap = []
6
7 for num in nums:
8 heapq.heappush(min_heap, num)
9 if len(min_heap) > k:
10 heapq.heappop(min_heap)
11
12 return list(min_heap)
13
14def top_k_frequent(nums, k):
15 from collections import Counter
16
17 count = Counter(nums)
18 # Use max heap (negate values for min heap)
19 return [item for item, _ in count.most_common(k)]
Complexity: O(n log k) time, O(k) space
8. Overlapping Intervals
Concept: Sort intervals and merge/process overlapping ones.
When to use:
- Merge intervals
- Insert interval
- Meeting rooms
- Minimum platforms needed
Code:
1def merge_intervals(intervals):
2 if not intervals:
3 return []
4
5 intervals.sort(key=lambda x: x[0])
6 merged = [intervals[0]]
7
8 for current in intervals[1:]:
9 last = merged[-1]
10 if current[0] <= last[1]:
11 # Overlapping - merge
12 merged[-1] = [last[0], max(last[1], current[1])]
13 else:
14 # Non-overlapping
15 merged.append(current)
16
17 return merged
18
19def can_attend_meetings(intervals):
20 intervals.sort(key=lambda x: x[0])
21
22 for i in range(1, len(intervals)):
23 if intervals[i][0] < intervals[i-1][1]:
24 return False
25
26 return True
Complexity: O(n log n) time, O(n) space
9. Modified Binary Search
Concept: Adapt binary search for rotated arrays, peak finding, or search space problems.
When to use:
- Rotated sorted array
- Find peak element
- Search in infinite array
- Minimum in rotated array
Code:
1def search_rotated(nums, target):
2 left, right = 0, len(nums) - 1
3
4 while left <= right:
5 mid = (left + right) // 2
6
7 if nums[mid] == target:
8 return mid
9
10 # Left half is sorted
11 if nums[left] <= nums[mid]:
12 if nums[left] <= target < nums[mid]:
13 right = mid - 1
14 else:
15 left = mid + 1
16 # Right half is sorted
17 else:
18 if nums[mid] < target <= nums[right]:
19 left = mid + 1
20 else:
21 right = mid - 1
22
23 return -1
24
25def find_peak_element(nums):
26 left, right = 0, len(nums) - 1
27
28 while left < right:
29 mid = (left + right) // 2
30 if nums[mid] > nums[mid + 1]:
31 right = mid
32 else:
33 left = mid + 1
34
35 return left
Complexity: O(log n) time, O(1) space
10. Binary Tree Traversal
Concept: Visit nodes in specific order: PreOrder, InOrder, PostOrder.
Orders:
- PreOrder: Root → Left → Right
- InOrder: Left → Root → Right
- PostOrder: Left → Right → Root
Code:
1class TreeNode:
2 def __init__(self, val=0, left=None, right=None):
3 self.val = val
4 self.left = left
5 self.right = right
6
7# Recursive
8def preorder_traversal(root):
9 result = []
10 def traverse(node):
11 if not node:
12 return
13 result.append(node.val) # Root
14 traverse(node.left) # Left
15 traverse(node.right) # Right
16 traverse(root)
17 return result
18
19def inorder_traversal(root):
20 result = []
21 def traverse(node):
22 if not node:
23 return
24 traverse(node.left) # Left
25 result.append(node.val) # Root
26 traverse(node.right) # Right
27 traverse(root)
28 return result
29
30# Iterative
31def preorder_iterative(root):
32 if not root:
33 return []
34
35 result = []
36 stack = [root]
37
38 while stack:
39 node = stack.pop()
40 result.append(node.val)
41 if node.right:
42 stack.append(node.right)
43 if node.left:
44 stack.append(node.left)
45
46 return result
Complexity: O(n) time, O(h) space for recursion
11. Depth-First Search (DFS)
Concept: Explore as deep as possible before backtracking.
When to use:
- Path finding
- Connected components
- Topological sort
- Cycle detection
Code:
1# Graph DFS
2def dfs_graph(graph, start, visited=None):
3 if visited is None:
4 visited = set()
5
6 visited.add(start)
7 result = [start]
8
9 for neighbor in graph[start]:
10 if neighbor not in visited:
11 result.extend(dfs_graph(graph, neighbor, visited))
12
13 return result
14
15# Tree DFS - max depth
16def max_depth(root):
17 if not root:
18 return 0
19 return 1 + max(max_depth(root.left), max_depth(root.right))
20
21# Tree DFS - path sum
22def has_path_sum(root, target_sum):
23 if not root:
24 return False
25
26 if not root.left and not root.right:
27 return root.val == target_sum
28
29 remaining = target_sum - root.val
30 return (has_path_sum(root.left, remaining) or
31 has_path_sum(root.right, remaining))
Complexity: O(V + E) for graph, O(n) for tree
12. Breadth-First Search (BFS)
Concept: Explore level by level using a queue.
When to use:
- Shortest path (unweighted)
- Level-order traversal
- Minimum depth
- All nodes at distance K
Code:
1from collections import deque
2
3# Tree BFS - level order
4def level_order(root):
5 if not root:
6 return []
7
8 result = []
9 queue = deque([root])
10
11 while queue:
12 level_size = len(queue)
13 current_level = []
14
15 for _ in range(level_size):
16 node = queue.popleft()
17 current_level.append(node.val)
18
19 if node.left:
20 queue.append(node.left)
21 if node.right:
22 queue.append(node.right)
23
24 result.append(current_level)
25
26 return result
27
28# Graph BFS - shortest path
29def shortest_path(graph, start, end):
30 queue = deque([(start, 0)])
31 visited = {start}
32
33 while queue:
34 node, distance = queue.popleft()
35 if node == end:
36 return distance
37
38 for neighbor in graph[node]:
39 if neighbor not in visited:
40 visited.add(neighbor)
41 queue.append((neighbor, distance + 1))
42
43 return -1
Complexity: O(V + E) time, O(V) space
13. Matrix Traversal
Concept: Navigate a 2D grid using DFS, BFS, or directional patterns.
When to use:
- Island problems
- Flood fill
- Word search
- Shortest path in grid
Code:
1# DFS - Number of islands
2def num_islands(grid):
3 if not grid:
4 return 0
5
6 def dfs(i, j):
7 if (i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]) or
8 grid[i][j] == '0'):
9 return
10
11 grid[i][j] = '0' # Mark as visited
12 dfs(i+1, j)
13 dfs(i-1, j)
14 dfs(i, j+1)
15 dfs(i, j-1)
16
17 count = 0
18 for i in range(len(grid)):
19 for j in range(len(grid[0])):
20 if grid[i][j] == '1':
21 dfs(i, j)
22 count += 1
23
24 return count
25
26# BFS - Shortest path
27def shortest_path_binary_matrix(grid):
28 if grid[0][0] == 1:
29 return -1
30
31 n = len(grid)
32 queue = deque([(0, 0, 1)]) # (row, col, distance)
33 grid[0][0] = 1 # Mark visited
34
35 directions = [(-1,-1), (-1,0), (-1,1), (0,-1), (0,1), (1,-1), (1,0), (1,1)]
36
37 while queue:
38 row, col, dist = queue.popleft()
39 if row == n-1 and col == n-1:
40 return dist
41
42 for dr, dc in directions:
43 new_row, new_col = row + dr, col + dc
44 if (0 <= new_row < n and 0 <= new_col < n and
45 grid[new_row][new_col] == 0):
46 queue.append((new_row, new_col, dist + 1))
47 grid[new_row][new_col] = 1
48
49 return -1
Complexity: O(m × n) time, O(m × n) space
14. Backtracking
Concept: Build solutions incrementally and abandon (backtrack) when constraints are violated.
When to use:
- Permutations/combinations
- N-Queens
- Sudoku
- Word search
- Subset problems
Code:
1# Permutations
2def permute(nums):
3 result = []
4
5 def backtrack(path, remaining):
6 if not remaining:
7 result.append(path[:])
8 return
9
10 for i in range(len(remaining)):
11 path.append(remaining[i])
12 backtrack(path, remaining[:i] + remaining[i+1:])
13 path.pop() # Backtrack
14
15 backtrack([], nums)
16 return result
17
18# Subsets
19def subsets(nums):
20 result = []
21
22 def backtrack(start, path):
23 result.append(path[:])
24
25 for i in range(start, len(nums)):
26 path.append(nums[i])
27 backtrack(i + 1, path)
28 path.pop() # Backtrack
29
30 backtrack(0, [])
31 return result
32
33# N-Queens
34def solve_n_queens(n):
35 result = []
36 board = [['.'] * n for _ in range(n)]
37
38 def is_valid(row, col):
39 # Check column
40 for i in range(row):
41 if board[i][col] == 'Q':
42 return False
43
44 # Check diagonals
45 i, j = row - 1, col - 1
46 while i >= 0 and j >= 0:
47 if board[i][j] == 'Q':
48 return False
49 i -= 1
50 j -= 1
51
52 i, j = row - 1, col + 1
53 while i >= 0 and j < n:
54 if board[i][j] == 'Q':
55 return False
56 i -= 1
57 j += 1
58
59 return True
60
61 def backtrack(row):
62 if row == n:
63 result.append([''.join(row) for row in board])
64 return
65
66 for col in range(n):
67 if is_valid(row, col):
68 board[row][col] = 'Q'
69 backtrack(row + 1)
70 board[row][col] = '.' # Backtrack
71
72 backtrack(0)
73 return result
Complexity: Varies (often exponential)
15. Dynamic Programming Patterns
Concept: Break problem into overlapping subproblems and store results to avoid recomputation.
Common Patterns:
- 0/1 Knapsack
- Unbounded Knapsack
- Fibonacci variants
- Longest Common Subsequence
- Longest Increasing Subsequence
Code:
1# Fibonacci - Classic DP
2def fibonacci(n):
3 if n <= 1:
4 return n
5
6 dp = [0] * (n + 1)
7 dp[1] = 1
8
9 for i in range(2, n + 1):
10 dp[i] = dp[i-1] + dp[i-2]
11
12 return dp[n]
13
14# 0/1 Knapsack
15def knapsack(weights, values, capacity):
16 n = len(weights)
17 dp = [[0] * (capacity + 1) for _ in range(n + 1)]
18
19 for i in range(1, n + 1):
20 for w in range(capacity + 1):
21 if weights[i-1] <= w:
22 dp[i][w] = max(
23 values[i-1] + dp[i-1][w - weights[i-1]],
24 dp[i-1][w]
25 )
26 else:
27 dp[i][w] = dp[i-1][w]
28
29 return dp[n][capacity]
30
31# Longest Common Subsequence
32def lcs(text1, text2):
33 m, n = len(text1), len(text2)
34 dp = [[0] * (n + 1) for _ in range(m + 1)]
35
36 for i in range(1, m + 1):
37 for j in range(1, n + 1):
38 if text1[i-1] == text2[j-1]:
39 dp[i][j] = dp[i-1][j-1] + 1
40 else:
41 dp[i][j] = max(dp[i-1][j], dp[i][j-1])
42
43 return dp[m][n]
44
45# Coin Change
46def coin_change(coins, amount):
47 dp = [float('inf')] * (amount + 1)
48 dp[0] = 0
49
50 for coin in coins:
51 for i in range(coin, amount + 1):
52 dp[i] = min(dp[i], dp[i - coin] + 1)
53
54 return dp[amount] if dp[amount] != float('inf') else -1
Complexity: Usually O(n²) or O(n × m) time, O(n) or O(n × m) space
Pattern Recognition Guide
Array/String:
- Prefix Sum, Two Pointers, Sliding Window, Monotonic Stack
Linked List:
- Two Pointers (Fast/Slow), In-place Reversal
Trees:
- DFS, BFS, Tree Traversal
Graphs:
- DFS, BFS, Backtracking
Optimization:
- Dynamic Programming, Top K Elements
Intervals:
- Overlapping Intervals, Sweep Line
Search:
- Binary Search, Modified Binary Search