Data Structures and Algorithms

Problem-solving techniques in DSA

1 month ago ; F(visit_count) + Value(1) views
Share this

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:  

 

Ready to level up? Start coding now! 

Become a member
Get the latest news right in your inbox. We never spam!

Read next

How to Check If Two Words Are Anagrams in Python

How to Check if Two Words are Anagrams in Python Clarity and precision are essential in sol… Read More

3 days, 2 hours ago . 252 views