Problem-Solving Approaches in Data Structures and Algorithms

In this blog, we have discussed some popular problem-solving strategies used in data structures and algorithms. Learning when and how to apply them is important for mastering DSA.

An Incremental approach using Single or Nested loops

This is one of the simple ideas where we build the partial solution step by step using a loop.

• Input-centric strategy: At each iteration, we process one input and build the partial solution.
• Output-centric strategy: At each iteration, we add one output to the solution and build the partial solution.

Here are some approaches: Using a single loop and variables, Using nested loops and variables, Incrementing the loop by a constant, Using the loop twice, Using a single loop and prefix array, etc.

Example problems: Insertion Sort, Finding max and min in an array, Valid mountain array, Find equilibrium index of an array, Dutch national flag problem, Sort an array in a waveform.

Problem-solving using Binary Search

When an array has an ordering property similar to a sorted array, we can use the binary search idea to solve searching problems efficiently in O(log n) time. To do this, we modify the standard binary search algorithm based on the conditions given in the problem. The core idea is simple: calculate the middle index and continue searching in either the left or right half of the array.

Example problems: Find Peak Element, Search a sorted 2D matrix, Find the square root of an integer, Search in Rotated Sorted Array

Divide and Conquer Approach

This strategy is about dividing a problem into more than one subproblems, solving each of them, and if necessary, combining their solutions to get a solution to the original problem. We can solve several problems efficiently using this strategy.

Example problems: Merge Sort, Quick Sort, Median of two sorted arrays

Two Pointers Approach

The two-pointer approach helps us optimize time and space complexity in the case of several problems on arrays and linked lists. Here pointers can be pairs of array indices or references to nodes. The goal of this approach is to simultaneously iterate over two different input parts to perform fewer operations.

Pointers moving in the same direction with the same pace: Merging two sorted arrays or linked lists, Finding the intersection of two arrays or linked lists, Checking an array is a subset of another array, etc.

Pointers moving in the same direction at a different pace (Fast and slow pointers): Partition process in the quick sort, Remove duplicates from the sorted array, Find the middle node in a linked list, Detect loop in a linked list, Move all zeroes to the end, Remove nth node from list end, etc.

Pointers moving in the opposite direction: Reversing an array, Check pair sum in an array, Finding triplet with zero-sum, Rainwater trapping problem, Container with most water, etc.

Sliding Window Approach

A sliding window is a contiguous section of an array or string, defined by its left and right boundaries. We perform the required calculations on the elements inside the window, then move one or both boundaries to examine another section. How the boundaries move depends on the conditions of the problem. Sometimes we move one boundary; sometimes we move both.

Sliding window is useful when a problem asks us to find information about a contiguous subarray that meets a given constraint. By updating the result as the window moves, we can avoid recalculating values for every section from scratch. This can reduce a nested-loop solution to a single pass.

Example problems: Longest substring without repeating characters, Count distinct elements in every window, Max continuous series of 1s, Find max consecutive 1's in an array, etc.

Transform and Conquer Approach

This is based on transforming a coding problem into another coding problem based on some particular property that makes the problem easier to solve. Here we solve the problem is solved in two stages:

1. Transformation stage: We transform the original problem into another easier problem to solve.
2. Conquering stage: Now, we solve the transformed problem.

Example problems: Pre-sorting based algorithms (Finding the closest pair of points, checking whether all the elements in a given array are distinct, etc.)

Problem-solving using BFS and DFS Traversal

Most tree and graph problems can be solved using DFS and BFS traversal. If the problem is to search for something closer to the root, we can prefer BFS, and if we need to search in-depth, we can choose DFS.

Sometimes we can use both BFS and DFS traversals when node order is not required. But in some cases, such things are not possible. We need to identify the use case to solve the problems efficiently.

• Preorder: Process each node before its children. It is useful when an operation needs to handle a parent before its subtrees like copying or serializing a tree.
• Inorder: In a binary search tree, this visits keys in sorted order (nondecreasing order if duplicate keys are allowed). So we can use inorder to solve several BST problems.
• Postorder: Process each node after its children. It is useful when handling a node depends on results from its subtrees like deleting a tree.
• Breadth-first search (BFS): Visit nodes level by level. It is useful when a problem asks for detail about specific levels like finding node at the minimum depth.

When solving tree and graph problems, we may need extra information to guide the algorithm. We can provide it through function parameters or helper functions, store it in parent pointers or node fields, or keep it in data structures such as stacks, queues and priority queues.

Example problems: Find min depth of a binary tree, Merge two binary trees, Find the height of a binary tree, Find the absolute minimum difference in a BST, The kth largest element in a BST, Course scheduling problem, bipartite graph, Find the left view of a binary tree, etc.

Problem-solving using the Data Structures

Data structure is one of the powerful tools of problem-solving in algorithms. It helps us perform critical operations efficiently and improves the time complexity of the solution. Here are some key insights:

• Many problems require an efficient way to perform the search, insert and delete operations. We can perform all these operations using the hash table in O(1) time average. It's a time-memory tradeoff, where we use extra space to store elements in the hash table to improve performance.
• Sometimes we store data in the stack or queue to solve several problems. 
• Suppose there is a requirement to continuously insert or remove maximum or minimum element. In that case, we can use a priority queue to solve the problem efficiently.
• Sometimes, we store data in Trie, AVL Tree, Segment Tree, etc., to to solve several problems.

Example problems: Next greater element, Valid Parentheses, Largest rectangle in a histogram, Sliding window maximum, kth smallest element in an array, Top k frequent elements, Longest common prefix, Range sum query, Longest consecutive sequence, Check equal array, LFU cache, LRU cache, Counting sort

Dynamic Programming

Dynamic programming is one of the most popular techniques for solving optimisation and counting problems. In such problems, rather than solving overlapping subproblems repeatedly, we solve each smaller subproblems only once and store the results in memory.

Example problems: Finding nth Fibonacci, Longest Common Subsequence, Climbing Stairs Problem, Maximum Subarray Sum, Minimum number of Jumps to reach End, Minimum Coin Change

Greedy Approach

This solves an optimisation problem by expanding a partially constructed solution until we reach the complete solution. We take a greedy choice at each step and add it to the partially constructed solution.

• At each step, the greedy approach chooses the best available alternative, with the hope that a sequence of locally optimal choices will produce an optimal solution to the entire problem.
• This approach works in some cases but fails in others. Designing a greedy algorithm is usually not difficult; the harder task is proving that it produces an optimal solution.

Example problems: Fractional Knapsack, Dijkstra algorithm, The activity selection problem.

Exhaustive Search

This strategy explores all possibilities of solutions until we found solution to the problem. For example: Find all permutations of a string, Print all subsets, etc.

Backtracking

Backtracking builds a solution one choice at a time and checks each partial solution against the constraints given in the problem.

• If a partial solution is valid, the algorithm tries a valid choice for the next step.
• If no valid choice remains, the algorithm backtracks: it undoes the most recent choice and tries another option at that step. So this process avoids exploring branches that cannot lead to a valid solution.

In simple terms, backtracking is about undoing incorrect choices. The fewer choices the algorithm needs to undo, the faster it can find a solution. In the worst case, a backtracking algorithm may generate every possible solution, like an exhaustive search, but this does not always happen.

Example problems: N-queen problem, Find all k combinations, Combination sum, Sudoku solver, etc.

Problem-solving using Bit manipulation and Numbers theory

Some coding problems are mathematical by nature, while others require us to identify hidden mathematical properties. Number theory and bit manipulation can be helpful in both cases.

Understanding the input bit pattern and processing data at the bit level can help us design efficient solutions. Computers perform bitwise operations in constant time, and bit manipulation can sometimes eliminate extra loops and significantly improve performance.

Example problems: Reverse bits, Add binary string, Check the power of two, Find the missing number, etc.

Hope you enjoyed the blog. Later we will write a separate blog on each problem-solving approach. Enjoy learning, Enjoy algorithms!