Overview
Data Structures and Algorithms (DSA) is the backbone of computer science and software engineering. Every efficient program - from a search engine to a GPS system - is built on the right choice of data structure and algorithm. Mastering DSA helps you write faster code, pass technical interviews, and reason clearly about how your programs behave.
Complexity Analysis
Section titled “Complexity Analysis”Before diving into specific data structures and algorithms, it is essential to understand how we measure efficiency.
- Big O Notation - Describes how the runtime or memory usage of an algorithm grows as the input grows
- Time Complexity - How long an algorithm takes to run
- Space Complexity - How much memory an algorithm uses
- Best, Average, and Worst Case - Understanding the different scenarios for an algorithm’s performance
- Common complexities: O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ), O(n!)
graph LR
O1["O(1)
Constant"]
OLN["O(log n)
Logarithmic"]
ON["O(n)
Linear"]
ONLN["O(n log n)
Linearithmic"]
ON2["O(n²)
Quadratic"]
O2N["O(2ⁿ)
Exponential"]
O1 -->|slower| OLN -->|slower| ON -->|slower| ONLN -->|slower| ON2 -->|slower| O2N
Arrays and Strings
Section titled “Arrays and Strings”Arrays are the most fundamental data structure. Almost every other structure is built on top of them.
- Static vs dynamic arrays - fixed vs resizable storage
- Indexing and slicing - accessing elements by position
- Two-pointer technique - solving problems with two indices moving toward each other
- Sliding window - efficiently processing subarrays or substrings
- Prefix sums - precomputing cumulative values for fast range queries
- String manipulation - reversing, searching, comparing, and transforming strings
- Common patterns: anagram detection, palindrome checks, substring search
Linked Lists
Section titled “Linked Lists”Linked lists store elements in nodes, where each node points to the next. They are flexible but slower to access than arrays.
- Singly linked lists - each node points to the next node
- Doubly linked lists - each node points to both the next and the previous node
- Circular linked lists - the last node points back to the first
- Operations: insertion, deletion, traversal, reversal
- Fast and slow pointer technique (Floyd’s cycle detection)
- Common problems: detecting cycles, finding the middle, merging two sorted lists
Stacks and Queues
Section titled “Stacks and Queues”Stacks and queues are linear data structures that control how elements are added and removed.
- Stack - Last In, First Out (LIFO); like a stack of plates
- Push (add), pop (remove), peek (look at top without removing)
- Use cases: undo/redo, call stack, bracket matching, depth-first search
- Queue - First In, First Out (FIFO); like a line of people
- Enqueue (add), dequeue (remove)
- Use cases: BFS, job scheduling, print queues
- Deque (double-ended queue) - add and remove from both ends
- Priority Queue - elements leave in order of priority, not insertion order
- Implementing a stack using an array or linked list
- Implementing a queue using two stacks
Hashing
Section titled “Hashing”Hashing maps data of any size to a fixed-size value, enabling very fast lookups.
- Hash functions - converting a key to an index
- Hash maps (dictionaries) - key-value storage with average O(1) lookup
- Hash sets - storing unique elements with fast membership testing
- Collision resolution:
- Chaining - storing multiple elements at the same index using a linked list
- Open addressing - probing for the next available slot (linear, quadratic, double hashing)
- Load factor and rehashing - when and how to resize a hash table
- Common use cases: counting frequencies, detecting duplicates, caching (memoization)
Trees are hierarchical data structures with a root node and child nodes branching below it.
- Binary Trees - each node has at most two children
- Tree traversals: Inorder (left, root, right), Preorder (root, left, right), Postorder (left, right, root)
- Level-order traversal (BFS on a tree)
- Binary Search Trees (BST) - left child is smaller, right child is larger; O(log n) search on average
- Balanced Trees - AVL trees and Red-Black trees; keep height O(log n) to avoid degrading to O(n)
- Heaps - complete binary trees where the parent is always larger (max-heap) or smaller (min-heap) than its children
- Used to implement priority queues
- Heap sort
- Tries (Prefix Trees) - storing strings character by character for fast prefix lookups
- Segment Trees - range queries and point updates in O(log n)
- Fenwick Trees (Binary Indexed Trees) - efficient prefix sum queries
Graphs
Section titled “Graphs”Graphs model relationships between entities. They are one of the most powerful and flexible data structures.
- Representations:
- Adjacency list - each node stores a list of its neighbours (efficient for sparse graphs)
- Adjacency matrix - a 2D grid marking which nodes are connected (efficient for dense graphs)
- Types of graphs: directed, undirected, weighted, unweighted, cyclic, acyclic (DAG)
- Traversals:
- Breadth-First Search (BFS) - explore level by level; shortest path in unweighted graphs
- Depth-First Search (DFS) - explore as deep as possible before backtracking
- Shortest Path Algorithms:
- Dijkstra’s Algorithm - single-source shortest path for non-negative weights
- Bellman-Ford - handles negative weights; detects negative cycles
- Floyd-Warshall - all-pairs shortest paths
- Minimum Spanning Tree:
- Kruskal’s Algorithm - build MST by adding the cheapest edge that does not form a cycle
- Prim’s Algorithm - build MST by growing one node at a time
- Topological Sort - ordering nodes of a DAG so all edges go forward
- Union-Find (Disjoint Set Union) - efficiently grouping and merging sets; used in cycle detection
Sorting Algorithms
Section titled “Sorting Algorithms”Sorting is one of the most studied problems in computer science. Each algorithm has different trade-offs.
| Algorithm | Best Case | Average Case | Worst Case | Space | Stable |
|---|---|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | No |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) | No |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) | No |
| Counting Sort | O(n + k) | O(n + k) | O(n + k) | O(k) | Yes |
| Radix Sort | O(nk) | O(nk) | O(nk) | O(n+k) | Yes |
- Stable sort - preserves the relative order of equal elements
- In-place sort - sorts without using extra memory proportional to input size
- When to use which: merge sort for stability, quick sort for average performance, counting sort for small integer ranges
Searching Algorithms
Section titled “Searching Algorithms”- Linear Search - check every element one by one; O(n); works on unsorted data
- Binary Search - repeatedly halve the search space; O(log n); requires sorted data
- Iterative and recursive implementations
- Binary search on the answer - using binary search to find a value that satisfies a condition
- Ternary Search - divide into thirds; used for unimodal functions
Recursion and Backtracking
Section titled “Recursion and Backtracking”- Recursion - a function that calls itself to solve a smaller version of the same problem
- Base case and recursive case
- Call stack and stack overflow
- Converting recursion to iteration using an explicit stack
- Backtracking - try a solution, and if it fails, undo and try a different path
- Use cases: generating permutations and combinations, solving mazes, N-Queens problem, Sudoku solver
- Pruning - cutting off branches that cannot lead to a valid solution early
Dynamic Programming
Section titled “Dynamic Programming”Dynamic programming (DP) solves problems by breaking them into overlapping subproblems and storing the results to avoid recomputation.
- Memoization (Top-Down) - recursion with caching of results
- Tabulation (Bottom-Up) - build the answer iteratively using a table
- Identifying DP problems - optimal substructure and overlapping subproblems
- Common DP patterns:
- 1D DP: Fibonacci, climbing stairs, house robber
- 2D DP: longest common subsequence, edit distance, coin change
- Knapsack problems: 0/1 knapsack, unbounded knapsack
- Interval DP: matrix chain multiplication, burst balloons
- DP on trees and graphs
Greedy Algorithms
Section titled “Greedy Algorithms”Greedy algorithms make the locally optimal choice at each step with the hope of finding the global optimum.
- When greedy works - problems with the greedy choice property and optimal substructure
- Classic greedy problems:
- Activity selection (interval scheduling)
- Huffman coding - building an optimal prefix-free encoding
- Fractional knapsack
- Dijkstra’s shortest path
- Minimum spanning trees (Kruskal and Prim)
- Greedy vs DP - knowing when each approach applies
Bit Manipulation
Section titled “Bit Manipulation”Bit manipulation works directly on binary representations for fast, low-memory operations.
- Bitwise operators: AND (
&), OR (|), XOR (^), NOT (~), left shift (<<), right shift (>>) - Common tricks:
- Check if a number is even or odd:
n & 1 - Check if a number is a power of two:
n & (n - 1) == 0 - Set, clear, and toggle specific bits
- XOR to find the unique element in a list of duplicates
- Check if a number is even or odd:
- Bitmasks - representing subsets of elements compactly as integers
- Applications in DP with bitmask (travelling salesman, subset enumeration)
Common Problem Patterns
Section titled “Common Problem Patterns”Recognising patterns helps you solve unfamiliar problems faster:
- Two Pointers - one from each end, or both moving in the same direction
- Sliding Window - a subarray or substring that grows and shrinks
- Fast and Slow Pointers - detecting cycles or finding midpoints in linked lists
- Divide and Conquer - split the problem, solve each half, combine results
- BFS / DFS - for all graph and tree traversal problems
- Monotonic Stack / Queue - tracking the next greater or smaller element
- Union-Find - grouping elements into connected components
- Binary Search on Answer - when the answer has a monotonic property
- Prefix Sums - precomputing cumulative values for fast range queries
- Heap (Priority Queue) - always processing the minimum or maximum element next
DSA is a skill that improves with practice. Work through problems consistently, understand the reasoning behind each algorithm, and focus on recognising patterns rather than memorising solutions.