Problem-Solving in Data Structures and Algorithms
Here's an all-inclusive guide to problem-solving techniques in DSA, ordered from the easiest to the most advanced.
Each section includes clear explanations, when to use, and practical code examples.
Effective problem-solving in DSA requires a structured approach and familiarity with key techniques. This guide covers 20 essential strategies, ordered from basic to advanced, with real-world examples and optimizations.
Where to use these problem-solving techniques:-
- Function optimizations
- Processing large datasets
- Building scalable applications
Here's a high-level overview of the techniques
- Brute Force (Complete Search)
- Two Pointers
- Sliding Window
- Binary Search
- Hashing (Hash Maps & Sets)
- Prefix Sum
- Greedy Algorithms
- Divide and Conquer
- Dynamic Programming (DP)
- Backtracking
- Bit Manipulation
- Monotonic Stack
- Union-Find (Disjoint Set)
- Graph Algorithms (BFS/DFS)
- Dijkstra's Algorithm
- Topological Sorting
- Trie (Prefix Tree)
- KMP Algorithm
- Floyd's Cycle Detection
- Meet-in-the-Middle
Let's dive in.
1. Brute Force (Complete Search)
When to Use: Small input sizes, no obvious optimization.
Approach: Try all possible solutions and pick the best.
Example: Check all subarrays for maximum sum.
def max_subarray_brute(arr):
max_sum = float('-inf')
for i in range(len(arr)):
curr_sum = 0
for j in range(i, len(arr)):
curr_sum += arr[j]
max_sum = max(max_sum, curr_sum)
return max_sum
Time Complexity**: O(n²)
2. Two Pointers
When to Use: Sorted arrays/strings, remove redundant iterations in arrays, pair/triplet problems e.g searching.
Approach: Use two pointers to traverse efficiently.
How It Works:
- Place one pointer at the beginning and another at the end, adjusting them based on the problem’s condition.
Example: Find two numbers summing to a target.
def two_sum_sorted(arr, target):
left, right = 0, len(arr) - 1
while left < right:
curr_sum = arr[left] + arr[right]
if curr_sum == target:
return [left, right]
elif curr_sum < target:
left += 1
else:
right -= 1
return []
Time Complexity: O(n)
3. Sliding Window
When to Use: Subarray/substring problems with fixed/variable size.
Approach: Maintain a window and slide it conditionally.
How It Works:
- Instead of recalculating values from scratch, maintain a "window" that moves dynamically, adding new elements and removing old ones as needed.
Example: Maximum sum of subarray of size `k`.
def max_sum_subarray(arr, k):
window_sum = sum(arr[:k])
max_sum = window_sum
for i in range(k, len(arr)):
window_sum += arr[i] - arr[i - k]
max_sum = max(max_sum, window_sum)
return max_sum
Time Complexity: O(n)
4. Binary Search
When to Use: Sorted data, logarithmic time searches.
Approach: Divide search space in half repeatedly.
Example: Find an element in a sorted array.
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
Time Complexity: O(log n)
5. Hashing (Hash Maps & Sets)
When to Use: Frequency counting, duplicates, lookups.
Approach: Store elements for O(1) access.
Example: Find two numbers summing to a target.
def two_sum(nums, target):
seen = {}
for i, num in enumerate(nums):
if target - num in seen:
return [seen[target - num], i]
seen[num] = i
return []
Time Complexity: O(n)
6. Prefix Sum
When to Use: Range sum queries, subarray problems.
Approach: Precompute cumulative sums.
Example: Sum of subarray from index `i` to `j`.
def prefix_sum(arr):
prefix = [0] * (len(arr) + 1)
for i in range(len(arr)):
prefix[i + 1] = prefix[i] + arr[i]
return prefix
def range_sum(prefix, i, j):
return prefix[j + 1] - prefix[i]
Time Complexity: O(1) per query after O(n) preprocess.
7. Greedy Algorithms
When to Use: Locally optimal choices lead to global optimum.
Approach: Make the best choice at each step.
Example: Activity selection.
def activity_selection(activities):
activities.sort(key=lambda x: x[1])
selected = [activities[0]]
for i in range(1, len(activities)):
if activities[i][0] >= selected[-1][1]:
selected.append(activities[i])
return selected
Time Complexity: O(n log n)
8. Divide and Conquer
When to Use: Problems divisible into independent subproblems.
Approach: Recursively break down, solve, and combine.
How It Works:
1. Divide: Split the problem into smaller parts.
2. Conquer: Solve the subproblems recursively.
3. Combine: Merge the results into a final solution.
Example: Merge Sort.
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
def merge(left, right):
"""Merges two sorted arrays into one."""
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] < right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
while i < len(left):
result.append(left[i])
i +=1
while i < len(right):
result.append(right[i])
i+=1
return result
Time Complexity: O(n log n)
9. Dynamic Programming (DP)
When to Use: Overlapping subproblems, optimal substructure.
Approach: Memoization (top-down) or tabulation (bottom-up).
Example: Fibonacci with memoization.
from functools import lru_cache
@lru_cache(maxsize=None)
def fib(n):
if n <= 1:
return n
return fib(n - 1) + fib(n - 2)
Time Complexity: O(n)
10. Backtracking
When to Use: Exhaustive search (permutations, combinations).
Approach: Try choices, backtrack if invalid.
Example: N-Queens.
def solve_n_queens(n):
def backtrack(row, cols, diags, anti_diags, board):
if row == n:
solutions.append(["".join(r) for r in board])
return
for col in range(n):
if col in cols or (row - col) in diags or (row + col) in anti_diags:
continue
board[row][col] = 'Q'
backtrack(row + 1, cols | {col}, diags | {row - col}, anti_diags | {row + col}, board)
board[row][col] = '.'
solutions = []
backtrack(0, set(), set(), set(), [['.'] * n for _ in range(n)])
return solutions
Time Complexity: O(n!)
11. Bit Manipulation
When to Use: Optimize space/time with bitwise ops.
Example: Find the single non-repeating number.
def single_number(nums):
result = 0
for num in nums:
result ^= num
return result
Time Complexity: O(n)
12. Monotonic Stack
When to Use: Next greater/smaller element problems.
Example: Next Greater Element.
def next_greater_element(nums):
stack = []
result = [-1] * len(nums)
for i in range(len(nums)):
while stack and nums[i] > nums[stack[-1]]:
result[stack.pop()] = nums[i]
stack.append(i)
return result
Time Complexity: O(n)
13. Union-Find (Disjoint Set)
When to Use: Dynamic connectivity, cycle detection.
Example: Detect cycles in a graph.
class UnionFind:
def __init__(self, size):
self.parent = list(range(size))
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
self.parent[self.find(x)] = self.find(y)
Time Complexity: O(α(n)) (near-constant)
14. Graph Algorithms (BFS/DFS)
When to Use: Shortest path (unweighted), connectivity.
Example: BFS for shortest path.
from collections import deque
def bfs_shortest_path(graph, start, end):
queue = deque([(start, [start])])
visited = set()
while queue:
node, path = queue.popleft()
if node == end:
return path
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append((neighbor, path + [neighbor]))
return []
Time Complexity: O(V + E)
15. Dijkstra's Algorithm
When to Use: Shortest path in weighted graphs (no negative edges).
Example: Priority queue-based implementation.
import heapq
def dijkstra(graph, start):
heap = [(0, start)]
distances = {node: float('inf') for node in graph}
distances[start] = 0
while heap:
dist, node = heapq.heappop(heap)
if dist > distances[node]:
continue
for neighbor, weight in graph[node].items():
new_dist = dist + weight
if new_dist < distances[neighbor]:
distances[neighbor] = new_dist
heapq.heappush(heap, (new_dist, neighbor))
return distances
Time Complexity: O((V + E) log V)
16. Topological Sorting
When to Use: DAGs, task scheduling.
Example: Kahn's Algorithm.
from collections import deque
def topological_sort(graph, num_nodes):
in_degree = {i: 0 for i in range(num_nodes)}
for node in graph:
for neighbor in graph[node]:
in_degree[neighbor] += 1
queue = deque([node for node in in_degree if in_degree[node] == 0])
order = []
while queue:
node = queue.popleft()
order.append(node)
for neighbor in graph.get(node, []):
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
return order if len(order) == num_nodes else []
Time Complexity: O(V + E)
17. Trie (Prefix Tree)
When to Use: String search, autocomplete.
Example: Trie implementation.
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 char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.is_end = True
Time Complexity: O(L) per insertion/search (L = word length).
18. KMP Algorithm
When to Use: Efficient string matching.
Example: Pattern search in text.
def kmp_search(text, pattern):
def build_lps(p):
lps = [0] * len(p)
j = 0
for i in range(1, len(p)):
while j > 0 and p[i] != p[j]:
j = lps[j - 1]
if p[i] == p[j]:
j += 1
lps[i] = j
return lps
lps = build_lps(pattern)
i = j = 0
while i < len(text):
if text[i] == pattern[j]:
i += 1
j += 1
if j == len(pattern):
return i - j
else:
if j != 0:
j = lps[j - 1]
else:
i += 1
return -1
Time Complexity: O(n + m)
19. Floyd's Cycle Detection
When to Use: Detect cycles in linked lists.
Example: Fast/slow pointers.
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
Time Complexity: O(n)
20. Meet-in-the-Middle
When to Use: Split large problems into halves (e.g., subset sum).
Example: Subset sum for large `n`.
def subset_sum(arr, target):
def generate_subsets(arr):
subsets = []
n = len(arr)
for mask in range(1 << n):
total = 0
for i in range(n):
if mask & (1 << i):
total += arr[i]
subsets.append(total)
return subsets
left, right = arr[:len(arr)//2], arr[len(arr)//2:]
left_sums = generate_subsets(left)
right_sums = generate_subsets(right)
right_sums.sort()
for sum_left in left_sums:
remaining = target - sum_left
if remaining in right_sums:
return True
return False
Time Complexity: O(2^(n/2))
Conclusion
The ability to identify and apply the right problem-solving technique is what separates great programmers from the rest.
Master these problem-solving techniques to dominate coding interviews and competitive programming. Start with brute force and two pointers, then progress to DP and graph algorithms.
Next Steps:
- - Practice on LeetCode / Codeforces / CodeSignal / Codility, or HackerRank.
- - Implement each technique from scratch.
- - Join coding contests to test your skills!
Ready to level up? Start coding now!