Back to Study Material Data Structures and Algorithms

Algorithms Overview

An algorithm is a finite sequence of well-defined instructions that takes some input, processes it, and produces an output. Good algorithms are correct, ef...

Algorithms Overview

Core Algorithm Families and When to Use Them

An algorithm is a finite sequence of well-defined instructions that takes some input, processes it, and produces an output. Good algorithms are correct, efficient, and readable. In practice, efficiency is measured in terms of time complexity, how the running time scales with input size, and space complexity, how much memory the algorithm uses.

Algorithm design has several foundational paradigms. Brute force tries every possible solution and picks the best one. It is easy to implement and always correct but often too slow for large inputs. Divide and conquer splits the problem into smaller subproblems, solves each recursively, and combines the results. Merge sort and binary search are classic examples, achieving O(n log n) and O(log n) time respectively.

Greedy algorithms make the locally optimal choice at each step, hoping to reach a global optimum. Dijkstra's shortest-path algorithm and the activity selection problem are solved greedily. Greedy approaches are fast but do not always yield the optimal solution, so correctness must be verified for each specific problem.

Dynamic programming solves problems by breaking them into overlapping subproblems and storing intermediate results to avoid redundant computation. This technique, called memoization when top-down and tabulation when bottom-up, transforms exponential brute-force solutions into polynomial ones. The Fibonacci sequence computed naively is O(2^n); with memoization it becomes O(n).

Backtracking explores possible solutions incrementally and abandons a partial solution as soon as it is determined to violate the constraints. Sudoku solvers and the N-Queens problem use backtracking. The worst-case time is still exponential, but pruning eliminates large portions of the search space in practice.

Graph algorithms form their own category: breadth-first search, depth-first search, Dijkstra, Bellman-Ford, Floyd-Warshall, Prim, and Kruskal each address specific graph problems ranging from shortest paths to minimum spanning trees.

Worked example: to find the maximum subarray sum in an integer array, a brute-force approach checks all subarrays in O(n^2) time. Kadane's algorithm, a greedy/dynamic programming hybrid, solves the same problem in O(n) with O(1) extra space by maintaining a running maximum.

Interview tip: when stuck on a problem, ask yourself whether it has optimal substructure (dynamic programming) or whether a greedy choice can be made safely at each step. These two questions narrow the field of applicable techniques quickly.