Preparing for coding interviews can be daunting, especially when you’re faced with a wide range of problems that test your problem-solving abilities. However, understanding and mastering common coding patterns can significantly increase your chances of success. In this guide, weâ€™ll walk through **15 must-know coding patterns** that frequently appear in coding interviews, along with pseudocode and practical examples to help you grasp each concept.

## ðŸŒŸ 1. Prefix Sum

**Pattern Overview:**

Prefix Sum is used to precompute cumulative sums of an array to enable efficient range sum queries.

**Pseudocode:**

python`def prefix_sum(array): prefix = [0] * len(array) # Initialize a list to store prefix sums prefix[0] = array[0] # The first element is the same as in the original array for i in range(1, len(array)): prefix[i] = prefix[i - 1] + array[i] # Add the current element to the previous prefix sum return prefix # Return the list of prefix sums`

**Practical Example:** Given an array arr = [1, 2, 3, 4, 5], compute the range sum from index 1 to 3.

**Implementation:**

`python`

**arr = [1, 2, 3, 4, 5] prefix = prefix_sum(arr) range_sum = prefix[3] – prefix[0] # Result is 9**

## ðŸŒŸ 2. Two Pointers

**Pattern Overview:**

Two Pointers technique involves using two indices to traverse data structures to solve problems efficiently.

**Pseudocode:**

python`def two_pointers(arr, target): left, right = 0, len(arr) - 1 # Initialize the two pointers while left < right: current_sum = arr[left] + arr[right] # Calculate the sum of the elements at the pointers if current_sum == target: return (left, right) # Return the indices if the target sum is found elif current_sum < target: left += 1 # Move the left pointer to the right if the current sum is less than the target else: right -= 1`

`Â `

**Practical Example:** Find two numbers in a sorted array arr = [1, 2, 3, 4, 6] that add up to 6.

**Implementation:**

`python`

**arr = [1, 2, 3, 4, 6] result = two_pointers(arr, 6) # Result is (1, 3)**

## ðŸŒŸ 3. Sliding Window

**Pattern Overview:**

Sliding Window is used to maintain a window of elements in an array or string and slide it across to find subarrays or substrings that meet specific conditions.

**Pseudocode:**

python`def sliding_window(arr, k): max_sum = 0 window_sum = sum(arr[:k]) for i in range(len(arr) - k): window_sum = window_sum - arr[i] + arr[i + k] max_sum = max(max_sum, window_sum) return max_sum`

**Practical Example:** Find the maximum sum of any contiguous subarray of size k = 3 in arr = [2, 1, 5, 1, 3, 2].

**Implementation:**

`python`

**arr = [2, 1, 5, 1, 3, 2] result = sliding_window(arr, 3) # Result is 9**

## ðŸŒŸ 4. Fast & Slow Pointers

**Pattern Overview:**

Fast and Slow Pointers are used to detect cycles in linked lists or arrays, or to find the middle of a list.

**Pseudocode:**

python`def has_cycle(head): slow, fast = head, head # Initialize two pointers, slow and fast while fast and fast.next: slow = slow.next # Move slow pointer one step fast = fast.next.next # Move fast pointer two steps if slow == fast: return True # A cycle is detected if slow and fast pointers meet return False # No cycle detected if the loop exits`

`Â `

**Practical Example:** Detect if a linked list has a cycle.

**Implementation:**

`python`

**# Assume ListNode is a class for linked list nodes cycle_detected = has_cycle(head) # Result is True/False**

## ðŸŒŸ 5. LinkedList In-Place Reversal

**Pattern Overview:**

This pattern reverses a linked list or its parts in-place without using extra space.

**Pseudocode:**

python`def reverse_linked_list(head): prev, current = None, head # Initialize previous node as None and current node as head while current: next_node = current.next # Save the next node current.next = prev # Reverse the current node's pointer prev = current # Move prev and current one step forward current = next_node return prev # prev is the new head of the reversed linked list`

`Â `

**Practical Example:** Reverse a linked list with nodes 1 -> 2 -> 3 -> 4 -> 5.

**Implementation:**

`python`

**# Assume ListNode is a class for linked list nodes new_head = reverse_linked_list(head) # List is now 5 -> 4 -> 3 -> 2 -> 1**

## ðŸŒŸ 6. Monotonic Stack

**Pattern Overview:**

A Monotonic Stack maintains a stack where the elements are in a monotonic order, either increasing or decreasing.

**Pseudocode:**

python`def next_greater_elements(nums): stack = [] result = [-1] * len(nums) # Initialize the result list with -1 for each element for i in range(len(nums)): while stack and nums[stack[-1]] < nums[i]: result[stack.pop()] = nums[i] # Update result with the next greater element stack.append(i) # Push the current index onto the stack return result`

`Â `

**Practical Example:** Find the next greater element for each element in arr = [2, 1, 2, 4, 3].

**Implementation:**

`python`

**arr = [2, 1, 2, 4, 3] result = next_greater_elements(arr) # Result is [4, 2, 4, -1, -1]**

## ðŸŒŸ 7. Top â€˜Kâ€™ Elements

**Pattern Overview:**

This pattern uses a heap to track the top ‘K’ elements in a dataset.

**Pseudocode:**

python`import heapq def top_k_elements(nums, k): return heapq.nlargest(k, nums)`

`Â `

**Practical Example:** Find the top 3 largest elements in arr = [3, 2, 1, 5, 6, 4].

**Implementation:**

`python`

**arr = [3, 2, 1, 5, 6, 4] result = top_k_elements(arr, 3) # Result is [6, 5, 4]**

## ðŸŒŸ 8. Overlapping Intervals

**Pattern Overview:**

This pattern handles problems that involve overlapping intervals by sorting and merging intervals.

**Pseudocode:**

python`def merge_intervals(intervals): # Sort the intervals based on the starting time intervals.sort(key=lambda x: x[0]) merged = [] # Initialize the list to store merged intervals for interval in intervals: # If merged is empty or there is no overlap with the last interval, append the current interval if not merged or merged[-1][1] < interval[0]: merged.append(interval) else: # If there is an overlap, merge the intervals by updating the end time merged[-1][1] = max(merged[-1][1], interval[1]) return merged`

**Â **

**Practical Example:** Merge overlapping intervals in intervals = [[1, 3], [2, 6], [8, 10], [15, 18]].

**Implementation:**

`python`

**intervals = [[1, 3], [2, 6], [8, 10], [15, 18]] result = merge_intervals(intervals) # Result is [[1, 6], [8, 10], [15, 18]]**

## ðŸŒŸ 9. Modified Binary Search

### Â **Pattern Overview:**

This pattern involves modifying the standard binary search to handle problems with variations like searching in rotated arrays.

**Pseudocode:**

python`def search_rotated_array(nums, target): left, right = 0, len(nums) - 1 while left <= right: mid = (left + right) // 2 # If the target is found, return its index if nums[mid] == target: return mid # Determine which side is properly sorted if nums[left] <= nums[mid]: # Left side is sorted if nums[left] <= target < nums[mid]: # Target is in the left side right = mid - 1 else: # Target is in the right side left = mid + 1 else: # Right side is sorted if nums[mid] < target <= nums[right]: # Target is in the right side left = mid + 1 else: # Target is in the left side right = mid - 1 # If the target is not found, return -1 return -1`

`Â `

**Practical Example:** Search for the target 5 in a rotated array arr = [4, 5, 6, 7, 0, 1, 2].

**Implementation:**

`python`

**arr = [4, 5, 6, 7, 0, 1, 2] index = search_rotated_array(arr, 5) # Result is 1**

## ðŸŒŸ 10. Binary Tree Traversal

**Pattern Overview:**

Binary Tree Traversal involves visiting nodes in a binary tree in a specific order (inorder, preorder, postorder).

**Pseudocode (Inorder Traversal):**

python`def inorder_traversal(root): result = [] def dfs(node): if node: dfs(node.left) # Traverse the left subtree result.append(node.val) # Visit the node dfs(node.right) # Traverse the right subtree dfs(root) return result`

`Â `

**Practical Example:** Perform an inorder traversal on a binary tree.

**Implementation:**

`python`

**# Assume TreeNode is a class for tree nodes result = inorder_traversal(root) # Result is nodes visited in inorder sequence**

## ðŸŒŸ 11. Depth-First Search (DFS)

**Pattern Overview:**

DFS explores all nodes in a depthward motion before exploring breadthwise, useful for traversing or searching tree/graph structures.

**Pseudocode:**

python`def dfs(graph, start): visited = set() # Initialize an empty set to keep track of visited nodes def dfs_helper(node): if node not in visited: visited.add(node) # Mark the current node as visited for neighbor in graph[node]: # Explore all the neighbors dfs_helper(neighbor) # Recursively visit each neighbor dfs_helper(start) # Start the DFS from the initial node return visited # Return the set of visited nodes`

`Â `

**Practical Example:** Perform a DFS on a graph starting from node A.

**Implementation:**

`python`

**graph = {‘A’: [‘B’, ‘C’], ‘B’: [‘D’], ‘C’: [‘E’], ‘D’: [], ‘E’: []} visited_nodes = dfs(graph, ‘A’) # Result is {‘A’, ‘B’, ‘D’, ‘C’, ‘E’}**

## ðŸŒŸ 12. Breadth-First Search (BFS)

**Pattern Overview:**

BFS uses a queue to explore all neighbors at the present depth level before moving on to nodes at the next depth level.

**Pseudocode:**

python`from collections import deque def bfs(graph, start): visited, queue = set(), deque([start]) # Initialize visited set and queue with the start node while queue: node = queue.popleft() # Dequeue a node from the front of the queue if node not in visited: visited.add(node) # Mark the node as visited queue.extend(graph[node] - visited) # Add all unvisited neighbors to the queue return visited # Return the set of visited nodes`

`Â `

**Practical Example:** Perform a BFS on a graph starting from node A.

**Implementation:**

`python`

**graph = {‘A’: set([‘B’, ‘C’]), ‘B’: set([‘D’]), ‘C’: set([‘E’]), ‘D’: set(), ‘E’: set()} visited_nodes = bfs(graph, ‘A’) # Result is {‘A’, ‘B’, ‘C’, ‘D’, ‘E’}**

## ðŸŒŸ 13. Matrix Traversal

**Pattern Overview:**

Matrix Traversal involves navigating through a matrix in a specific direction/order, such as row-wise, column-wise, or diagonally.

**Pseudocode:**

python`def traverse_matrix(matrix): for row in matrix: for element in row: print(element, end=' ')`

`Â `

**def traverse_matrix(matrix): for row in matrix: for element in row: print(element, end=’ ‘)**

**Practical Example:** Traverse a 2D matrix row by row.

**Implementation:**

`python`

**matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] traverse_matrix(matrix) # Prints: 1 2 3 4 5 6 7 8 9**

## ðŸŒŸ 14. Backtracking

**Pattern Overview:**

Backtracking involves recursively exploring all potential solutions and abandoning paths that don’t meet the required conditions.

**Pseudocode:**

python`def backtrack(path, options): if end_condition: # Base case: check if the end condition is met results.append(path[:]) # Add a copy of the current path to results return for option in options: path.append(option) # Choose an option by adding it to the current path backtrack(path, options) # Explore further with the updated path path.pop() # Undo the choice (backtrack) to explore other options`

`Â `

**Practical Example:** Generate all permutations of [1, 2, 3].

**Implementation:**

python`def permute(nums): result = [] def backtrack(path, options): if not options: # If no more options are available, add the path to the result result.append(path[:]) # Add a copy of the current path to the result return for i in range(len(options)): # Choose the current element and add it to the path path.append(options[i]) # Explore with the current element removed from the options backtrack(path, options[:i] + options[i+1:]) # Backtrack by removing the last element added to the path path.pop() backtrack([], nums) return result # Example usage result = permute([1, 2, 3]) # Result is [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]`

`Â `

### Â

## ðŸŒŸ 15. Dynamic Programming (DP)

**Pattern Overview:**

Dynamic Programming breaks problems into overlapping subproblems, storing solutions to subproblems and reusing them to solve larger problems.

**Pseudocode:**

`python`

**def fib(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]**

**Practical Example:** Calculate the 10th Fibonacci number using DP.

**Implementation:**

python`def fib(n): if n <= 1: return n dp = [0] * (n + 1) # Initialize a list to store Fibonacci numbers up to n dp[1] = 1 # The first Fibonacci number is 1 for i in range(2, n + 1): dp[i] = dp[i - 1] + dp[i - 2] # Calculate the i-th Fibonacci number return dp[n] # Return the n-th Fibonacci number`

`Â `

**result = fib(10) # Result is 55**