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!