DSA Patterns in Python - Complete
Reference
1. Two Pointers Pattern
When to Use:
• Sorted arrays or need to find pairs/triplets
• Problems involving comparison from both ends
• Partition problems
• Removing duplicates in-place
Core Concept:
Use two pointers starting at different positions (usually start/end or both at start) and
move them based on conditions.
Code Pattern:
# Opposite Direction (start and end)
def two_pointers_opposite(arr):
left, right = 0, len(arr) - 1
while left < right:
# Process current pair
if condition_met:
return result
elif need_larger_sum:
left += 1
else:
right -= 1
return result
# Same Direction (both from start)
def two_pointers_same(arr):
slow = fast = 0
while fast < len(arr):
if condition:
slow += 1
fast += 1
return slow
Example: Two Sum II (sorted array)
def twoSum(numbers, target):
left, right = 0, len(numbers) - 1
while left < right:
current_sum = numbers[left] + numbers[right]
if current_sum == target:
return [left + 1, right + 1]
elif current_sum < target:
left += 1
else:
right -= 1
return []
Example: Remove Duplicates (in-place)
def removeDuplicates(nums):
if not nums:
return 0
slow = 0
for fast in range(1, len(nums)):
if nums[fast] != nums[slow]:
slow += 1
nums[slow] = nums[fast]
return slow + 1
Key Points:
• Time: O(n), Space: O(1)
• Works best on sorted arrays
• Opposite direction: comparison problems
• Same direction: in-place modification
2. Sliding Window Pattern
When to Use:
• Contiguous subarray/substring problems
• Keywords: "subarray", "substring", "consecutive"
• Finding min/max length with a condition
Core Concept:
Maintain a window [left, right] and expand/shrink it based on conditions.
Code Pattern:
# Fixed Window Size
def fixed_window(arr, k):
window_sum = sum(arr[:k])
max_sum = window_sum
for i in range(k, len(arr)):
window_sum = window_sum - arr[i-k] + arr[i]
max_sum = max(max_sum, window_sum)
return max_sum
# Variable Window Size
def variable_window(arr, target):
left = 0
current_sum = 0
result = float('inf')
for right in range(len(arr)):
current_sum += arr[right]
while current_sum >= target:
result = min(result, right - left + 1)
current_sum -= arr[left]
left += 1
return result if result != float('inf') else 0
Example: Longest Substring Without Repeating
def lengthOfLongestSubstring(s):
char_set = set()
left = 0
max_length = 0
for right in range(len(s)):
while s[right] in char_set:
char_set.remove(s[left])
left += 1
char_set.add(s[right])
max_length = max(max_length, right - left + 1)
return max_length
Key Points:
• Time: O(n), Space: O(k)
• Fixed window: add/remove straightforward
• Variable: use while to shrink
• Often combined with hashmap
3. Fast & Slow Pointers (Floyd's)
When to Use:
• Cycle detection in linked lists
• Finding middle of linked list
• Palindrome linked list check
Core Concept:
Fast moves 2x speed. If cycle exists, they meet. When fast reaches end, slow is at middle.
Code Pattern:
# Cycle Detection
def hasCycle(head):
slow = fast = head
while fast and [Link]:
slow = [Link]
fast = [Link]
if slow == fast:
return True
return False
# Find Middle
def findMiddle(head):
slow = fast = head
while fast and [Link]:
slow = [Link]
fast = [Link]
return slow
Example: Find Cycle Start
def detectCycle(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
Key Points:
• Time: O(n), Space: O(1)
• Fast moves 2x, slow moves 1x
• Cycle start: reset slow to head after meeting
4. Prefix/Suffix Sum Pattern
When to Use:
• Subarray sum queries
• Product of array except self
• Range sum/product queries
Core Concept:
Precompute cumulative sums/products. Query any range in O(1).
Code Pattern:
# Build Prefix Sum
def build_prefix_sum(arr):
prefix = [0] * (len(arr) + 1)
for i in range(len(arr)):
prefix[i + 1] = prefix[i] + arr[i]
return prefix
# Range sum [left, right]
def range_sum(prefix, left, right):
return prefix[right + 1] - prefix[left]
# Product Except Self
def productExceptSelf(nums):
n = len(nums)
result = [1] * n
prefix = 1
for i in range(n):
result[i] = prefix
prefix *= nums[i]
suffix = 1
for i in range(n - 1, -1, -1):
result[i] *= suffix
suffix *= nums[i]
return result
Example: Subarray Sum Equals K
def subarraySum(nums, k):
prefix_sum = 0
sum_count = {0: 1}
result = 0
for num in nums:
prefix_sum += num
if prefix_sum - k in sum_count:
result += sum_count[prefix_sum - k]
sum_count[prefix_sum] = sum_count.get(prefix_sum, 0) + 1
return result
Key Points:
• Time: O(n) build, O(1) query
• Space: O(n)
• Range sum = prefix[right+1] - prefix[left]
• Use hashmap for subarray sum problems
5. Binary Search Pattern
When to Use:
• Sorted array search
• Find boundary/threshold
• "Find min/max where condition holds"
Core Concept:
Eliminate half the search space each iteration.
Code Pattern:
# Basic Binary Search
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = left + (right - left) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
# Find Boundary
def find_boundary(arr, target, find_first=True):
left, right = 0, len(arr) - 1
result = -1
while left <= right:
mid = left + (right - left) // 2
if arr[mid] == target:
result = mid
if find_first:
right = mid - 1
else:
left = mid + 1
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return result
Example: Search in Rotated Sorted Array
def search(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] == target:
return mid
if nums[left] <= nums[mid]:
if nums[left] <= target < nums[mid]:
right = mid - 1
else:
left = mid + 1
else:
if nums[mid] < target <= nums[right]:
left = mid + 1
else:
right = mid - 1
return -1
Key Points:
• Time: O(log n), Space: O(1)
• Use left + (right - left) // 2
• <= for exact, < for boundary
• Rotated: check which half is sorted
6. Stack Pattern (Monotonic)
When to Use:
• Next/previous greater/smaller element
• Histogram/rectangle problems
• Valid parentheses
Core Concept:
Stack maintains increasing/decreasing order. Pop when new element breaks monotonicity.
Code Pattern:
# Next Greater Element
def nextGreaterElement(nums):
result = [-1] * len(nums)
stack = []
for i in range(len(nums)):
while stack and nums[stack[-1]] < nums[i]:
idx = [Link]()
result[idx] = nums[i]
[Link](i)
return result
# Valid Parentheses
def isValid(s):
stack = []
pairs = {'(': ')', '{': '}', '[': ']'}
for char in s:
if char in pairs:
[Link](char)
elif not stack or pairs[[Link]()] != char:
return False
return len(stack) == 0
Example: Daily Temperatures
def dailyTemperatures(temperatures):
result = [0] * len(temperatures)
stack = []
for i, temp in enumerate(temperatures):
while stack and temperatures[stack[-1]] < temp:
idx = [Link]()
result[idx] = i - idx
[Link](i)
return result
Key Points:
• Time: O(n), each element pushed/popped once
• Store indices for distance calculations
• Increasing stack: pop if stack[-1] > current
• Decreasing stack: pop if stack[-1] < current
7. HashMap/HashSet Pattern
When to Use:
• Count frequencies
• O(1) existence check
• Two sum problems
• Anagram/pattern matching
Core Concept:
Trade space for time. O(1) lookup instead of O(n) scan.
Code Pattern:
# Frequency Counter
def frequencyCounter(arr):
freq = {}
for num in arr:
freq[num] = [Link](num, 0) + 1
return freq
# Two Sum
def twoSum(nums, target):
seen = {}
for i, num in enumerate(nums):
complement = target - num
if complement in seen:
return [seen[complement], i]
seen[num] = i
return []
Example: Group Anagrams
def groupAnagrams(strs):
anagrams = {}
for s in strs:
key = ''.join(sorted(s))
if key not in anagrams:
anagrams[key] = []
anagrams[key].append(s)
return list([Link]())
Key Points:
• Time: O(1) average lookup
• Space: O(n)
• dict for frequency/mapping
• set for existence checks
8. BFS (Breadth-First Search)
When to Use:
• Shortest path (unweighted)
• Level-order traversal
• Minimum steps problems
Core Concept:
Use queue (FIFO). Process level by level. Guarantees shortest path.
Code Pattern:
from collections import deque
# Graph BFS
def bfs(graph, start, target):
queue = deque([start])
visited = {start}
distance = 0
while queue:
for _ in range(len(queue)):
node = [Link]()
if node == target:
return distance
for neighbor in graph[node]:
if neighbor not in visited:
[Link](neighbor)
[Link](neighbor)
distance += 1
return -1
# Tree Level Order
def levelOrder(root):
if not root:
return []
result = []
queue = deque([root])
while queue:
level = []
for _ in range(len(queue)):
node = [Link]()
[Link]([Link])
if [Link]:
[Link]([Link])
if [Link]:
[Link]([Link])
[Link](level)
return result
Key Points:
• Time: O(V + E), Space: O(V)
• Use deque for O(1) operations
• Process level by level
• Guarantees shortest path in unweighted graphs
9. DFS (Depth-First Search)
When to Use:
• Explore all paths
• Connected components
• Cycle detection
• Backtracking problems
Core Concept:
Go deep first before backtracking. Use recursion or stack.
Code Pattern:
# Recursive DFS
def dfs_recursive(graph, node, visited):
if node in visited:
return
[Link](node)
for neighbor in graph[node]:
dfs_recursive(graph, neighbor, visited)
# Iterative DFS
def dfs_iterative(graph, start):
stack = [start]
visited = set()
while stack:
node = [Link]()
if node in visited:
continue
[Link](node)
for neighbor in graph[node]:
if neighbor not in visited:
[Link](neighbor)
Example: Number of Islands
def numIslands(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'
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':
dfs(r, c)
count += 1
return count
Key Points:
• Time: O(V + E), Space: O(V)
• Recursive: cleaner for trees
• Iterative: better for deep graphs
• Mark visited to avoid loops
10. Backtracking Pattern
When to Use:
• Generate permutations/combinations
• Solve puzzles (Sudoku, N-Queens)
• Find all valid solutions
Core Concept:
Build solution incrementally. Undo choice when invalid (backtrack).
Code Pattern:
# Template
def backtrack(path, choices):
if is_solution(path):
[Link]([Link]())
return
for choice in choices:
if is_valid(choice):
[Link](choice)
backtrack(path, remaining_choices)
[Link]()
# Permutations
def permute(nums):
result = []
def backtrack(path):
if len(path) == len(nums):
[Link]([Link]())
return
for num in nums:
if num not in path:
[Link](num)
backtrack(path)
[Link]()
backtrack([])
return result
Example: Combination Sum
def combinationSum(candidates, target):
result = []
def backtrack(start, path, total):
if total == target:
[Link]([Link]())
return
if total > target:
return
for i in range(start, len(candidates)):
[Link](candidates[i])
backtrack(i, path, total + candidates[i])
[Link]()
backtrack(0, [], 0)
return result
Key Points:
• Time: O(2^n) or O(n!)
• Always copy path when adding to result
• Undo choice after recursion
• Prune early if invalid
Pattern Quick Reference
Pattern Time Space Triggers
Two Pointers O(n) O(1) sorted, pairs,
duplicates
Sliding Window O(n) O(k) subarray, substring
Fast & Slow O(n) O(1) cycle, middle, linked
list
Prefix/Suffix O(n) O(n) range sum, product
Binary Search O(log n) O(1) sorted, boundary
Stack O(n) O(n) next greater,
parentheses
HashMap O(n) O(n) frequency, two sum
BFS O(V+E) O(V) shortest path, level
order
DFS O(V+E) O(V) all paths, connected
Backtracking O(2^n) O(n) permutations, all
solutions
Pattern Selection Tips
1. Sorted array → Binary Search or Two Pointers
2. Contiguous subarray → Sliding Window
3. Tree/Graph → BFS (shortest) or DFS (all paths)
4. All combinations → Backtracking
5. Frequency → HashMap
6. Next greater/smaller → Stack
7. Range queries → Prefix Sum
8. Linked list cycle → Fast & Slow