DSA Complete Explanation Guide

Searching • Sorting • Data Structures • Graph • Dynamic Programming • Strings

This guide explains every major DSA concept — what it is, how it works, when to use it, real examples, and
complexity. Designed for quick revision and deep understanding.
 1. SEARCHING ALGORITHMS

Searching means finding a specific element in a collection. Choice of algorithm depends on whether data is sorted, size of
data, and access pattern.

1.1 Linear Search

What it is: Check every element one by one from start to end until the target is found.

How it works: Start at index 0. Compare each element with target. Return index if found, else -1.
Example: Array = [5, 3, 8, 1, 9], Find = 8
Step 1: 5 ≠ 8 → Step 2: 3 ≠ 8 → Step 3: 8 = 8 → Found at index 2
When to use: Unsorted data, small arrays, linked lists (no random access).
Time: O(n) worst/avg | O(1) best | Space: O(1)

1.2 Binary Search

What it is: Repeatedly divide a SORTED array in half to narrow down the search range.

How it works:

• Set low=0, high=n-1. Compute mid = (low+high)/2

• If arr[mid] == target → found
• If arr[mid] < target → search right half (low = mid+1)
• If arr[mid] > target → search left half (high = mid-1)
• Repeat until low > high
Example: Sorted Array = [1, 3, 5, 7, 9, 11], Find = 7
mid=5 → arr[2]=5 < 7 → low=3 | mid=(3+5)/2=4 → arr[4]=9 > 7 → high=3 | mid=3 → arr[3]=7 = Found!
When to use: Always use on sorted arrays. Also use for 'search on answer space' problems (find minimum valid answer).

Variants: Lower bound (first occurrence), Upper bound (last occurrence), Rotated sorted array.
Time: O(log n) worst/avg | O(1) best | Space: O(1) iterative, O(log n) recursive

1.3 Jump Search

What it is: Jump ahead by fixed steps of sqrt(n), then do linear search in the block where target lies.

Example: n=9, step=3. Jump to index 0, 3, 6, 9... find the block, then scan linearly.

When to use: Sorted array, when backward traversal is costly (e.g., magnetic tape).
Time: O(sqrt n) | Space: O(1)

1.4 Interpolation Search

What it is: Improvement over binary search for uniformly distributed data. Instead of always picking mid, it guesses the
position using a formula:
pos = low + [(target - arr[low]) * (high - low)] / (arr[high] - arr[low])
When to use: When data is uniformly distributed (phone book, sorted numbers with equal gaps).
Time: O(log log n) avg | O(n) worst | Space: O(1)
1.5 BFS — Breadth First Search
What it is: Explore all neighbors at the current level before going deeper. Uses a Queue.

How it works: Start from source → enqueue it → while queue not empty → dequeue node → visit all unvisited neighbors →
enqueue them.

Use cases: Shortest path in unweighted graph, level-order traversal of tree, finding connected components.
Time: O(V+E) | Space: O(V)

1.6 DFS — Depth First Search

What it is: Go as deep as possible before backtracking. Uses a Stack (or recursion).

How it works: Start from source → visit node → recursively visit unvisited neighbors → backtrack.

Use cases: Cycle detection, topological sort, finding all paths, maze solving, SCC.
Time: O(V+E) | Space: O(V)
 2. SORTING ALGORITHMS

Sorting arranges elements in order. Key properties: Stable (equal elements keep original order), In-place (O(1) extra
space), Comparison-based vs Non-comparison.

2.1 Bubble Sort

What it is: Repeatedly compare adjacent pairs and swap if out of order. Largest element 'bubbles up' each pass.
[5,3,8,1] → Pass1: [3,5,1,8] → Pass2: [3,1,5,8] → Pass3: [1,3,5,8]
Optimization: If no swap in a pass → already sorted → stop early (best case O(n)).
Stable: Yes | Time: O(n) best, O(n^2) avg/worst | Space: O(1)

2.2 Selection Sort

What it is: Find minimum element from unsorted part, place it at the beginning.
[5,3,8,1] → Find min(1) swap with 5 → [1,3,8,5] → Find min(3) → [1,3,8,5] → ...
Note: Always O(n^2) comparisons even if sorted. Minimum number of swaps (O(n)).
Stable: No | Time: O(n^2) all cases | Space: O(1)

2.3 Insertion Sort

What it is: Pick one element at a time and insert it into the correct position in the already-sorted part.
[5,3,8,1] → [3,5,8,1] → [3,5,8,1] → [1,3,5,8]
Best case: Already sorted → O(n). Great for nearly-sorted data and small arrays.
Stable: Yes | Time: O(n) best, O(n^2) avg/worst | Space: O(1)

2.4 Merge Sort

What it is: Divide array into two halves, recursively sort each half, then merge them.

• Divide: Split array into halves until single elements

• Conquer: Each single element is trivially sorted
• Merge: Combine two sorted halves into one sorted array (compare front elements)
[5,3,8,1] → [5,3] [8,1] → [5][3] [8][1] → [3,5] [1,8] → [1,3,5,8]
Key advantage: Guaranteed O(n log n). Best for linked lists. Used in external sorting.
Stable: Yes | Time: O(n log n) all | Space: O(n)

2.5 Quick Sort

What it is: Pick a pivot, partition array so all elements < pivot are left, > pivot are right. Recurse.

• Choose pivot (last element, first, or random)

• Partition: rearrange so left side < pivot, right side > pivot
• Recursively sort left and right halves
Pivot=5: [5,3,8,1] → [3,1,5,8] → sort [3,1] and [8] → [1,3,5,8]
Worst case: Already sorted array with bad pivot (always smallest/largest) → O(n^2). Use randomized pivot to avoid.
Stable: No | Time: O(n log n) avg, O(n^2) worst | Space: O(log n) stack
2.6 Heap Sort
What it is: Build a Max Heap from array. Repeatedly extract max element to end of array.

• Build Max Heap: O(n)

• Extract max (root), swap with last, reduce heap size, heapify: O(log n) per extraction
Stable: No | Time: O(n log n) all | Space: O(1) — best in-place among O(n log n) sorts

2.7 Counting / Radix / Bucket Sort

Counting Sort: Count frequency of each element. Only for integers in a known range [0..k]. Build prefix sum, place
elements in output array. Stable.

Radix Sort: Sort digit by digit from least significant to most significant using Counting Sort as sub-routine. Works for
integers and strings.

Bucket Sort: Distribute elements into buckets (ranges), sort each bucket (usually Insertion Sort), concatenate. Best for
uniformly distributed floats in [0,1].
All three: Time O(n+k) or O(nk) | Non-comparison based — break O(n log n) barrier!
 3. DATA STRUCTURES

3.1 Array
Contiguous block of memory storing elements of the same type. Random access in O(1) via index.

• Static Array: Fixed size. Insertion/deletion costly — must shift elements.

• Dynamic Array (ArrayList/Vector): Doubles in size when full. Amortized O(1) insert at end.
• Key operations: Access O(1), Search O(n), Insert/Delete at end O(1)*, at middle O(n)
Techniques: Two Pointers, Sliding Window, Prefix Sum, Kadane's Algorithm.

3.2 Linked List

Chain of nodes where each node stores data + pointer to next node. No random access.

• Singly Linked List: Each node points to next. Traversal forward only.
• Doubly Linked List: Each node points to next AND previous. Can traverse both ways.
• Circular Linked List: Last node points back to head. Useful for round-robin.
When to use: Frequent insertions/deletions at known positions. Implementing stacks, queues, LRU cache.
Access O(n) | Insert/Delete at head O(1) | Insert/Delete at position O(n) find + O(1) change

3.3 Stack (LIFO — Last In First Out)

Elements added and removed from the same end (top). Like a pile of plates.

• push(x): Add to top — O(1)

• pop(): Remove from top — O(1)
• peek()/top(): View top without removing — O(1)
Use cases: Function call stack, undo operations, balanced parentheses, infix→postfix, DFS.

3.4 Queue (FIFO — First In First Out)

Elements added at rear, removed from front. Like a line at a counter.

• enqueue(x): Add at rear — O(1)

• dequeue(): Remove from front — O(1)
• Deque (Double-ended queue): Insert/delete at both ends — O(1)
• Priority Queue: Element with highest priority dequeued first. Implemented using Heap.
Use cases: BFS, task scheduling, sliding window maximum (Deque).

3.5 Hash Table (HashMap / HashSet)

Uses a hash function to map keys to array indices. Average O(1) for insert, delete, search.

• Hash function: converts key to index. Good hash = uniform distribution.

• Collision handling: Chaining (linked list at each bucket) or Open Addressing (probe for next empty slot).
• Load factor: n/m (elements/buckets). Keep < 0.75 for good performance.
Use cases: Frequency counting, two-sum problem, anagram detection, caching.
Avg: O(1) all ops | Worst (all collide): O(n) | Space: O(n)
3.6 Trees
Binary Tree: Each node has at most 2 children (left, right). Traversals: Inorder (LNR), Preorder (NLR), Postorder (LRN),
Level-order (BFS).

BST (Binary Search Tree): Left child < parent < right child. Search/Insert/Delete O(log n) avg but O(n) if skewed.

AVL Tree: Self-balancing BST. Height difference between left/right subtrees (balance factor) ≤ 1. Rotations maintain
balance. O(log n) guaranteed.

Red-Black Tree: Self-balancing BST with color property. Less strict than AVL → faster inserts. Used in Java TreeMap,
C++ std::map.

Trie (Prefix Tree): Tree for storing strings. Each edge = one character. Perfect for autocomplete, spell-check, IP routing.

Segment Tree: Binary tree for range queries (sum, min, max) on array. Build O(n), Query O(log n), Update O(log n).

Fenwick Tree (BIT): Simpler than Segment Tree for prefix sum queries. Uses bit manipulation.

3.7 Heap
Complete binary tree satisfying heap property.

• Min Heap: Parent <= children. Root = minimum element.

• Max Heap: Parent >= children. Root = maximum element.
• Insert: Add at end, bubble up — O(log n)
• Extract min/max: Remove root, place last element at root, bubble down — O(log n)
• Peek min/max: O(1) — just look at root
Use cases: Priority Queue, Heap Sort, Dijkstra's algorithm, K largest/smallest elements, median of stream.
 4. GRAPH ALGORITHMS

A graph G = (V, E) has vertices (nodes) and edges (connections). Directed (one-way edges) vs Undirected. Weighted vs
Unweighted. Represented as Adjacency Matrix O(V^2) space or Adjacency List O(V+E) space.

4.1 Dijkstra's Algorithm — Shortest Path (Non-negative weights)

How it works: Use a Min Heap (Priority Queue). Start from source with distance 0. Greedily pick unvisited node with
smallest distance. Relax all its neighbors.

• dist[source]=0, all others = infinity

• Push (0, source) into min-heap
• While heap not empty: pop (d, u). For each neighbor v: if d + weight(u,v) < dist[v] → update and push
Why it fails with negative weights: Greedy assumption breaks — a later path might be shorter.
Time: O((V+E) log V) | Space: O(V)

4.2 Bellman-Ford — Shortest Path (Negative weights allowed)

How it works: Relax ALL edges V-1 times. If still relaxing on V-th iteration → negative cycle.
Relaxation: if dist[u] + w(u,v) < dist[v] then dist[v] = dist[u] + w(u,v)
When to use: Graphs with negative weights, detecting negative cycles.
Time: O(VE) | Space: O(V) — Slower than Dijkstra but handles negatives

4.3 Floyd-Warshall — All Pairs Shortest Path

Finds shortest path between EVERY pair of vertices using DP.
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) for all intermediate k
When to use: Dense graphs, need all-pairs distances, detect negative cycles (diagonal < 0).
Time: O(V^3) | Space: O(V^2)

4.4 Minimum Spanning Tree (Prim's & Kruskal's)

MST: Subset of edges connecting all vertices with minimum total weight, no cycles.

Prim's Algorithm: Greedy. Start from any vertex. Always add the cheapest edge connecting visited to unvisited vertex.
Use Min Heap. Best for dense graphs.

Kruskal's Algorithm: Sort all edges by weight. Add edge if it doesn't form cycle (use Union-Find). Best for sparse graphs.

Union-Find (Disjoint Set): Tracks which vertices are connected. find() and union() in near O(1) with path compression.
Prim: O((V+E) log V) | Kruskal: O(E log E) | Space: O(V)

4.5 Topological Sort

Linear ordering of vertices in a DAG (Directed Acyclic Graph) such that for every edge u→v, u comes before v.

Kahn's Algorithm (BFS): Compute in-degree of all nodes. Add nodes with in-degree 0 to queue. Process each, reduce
neighbor in-degrees. If count != V → cycle exists.

DFS approach: Run DFS, add node to stack after all its descendants are processed. Reverse stack = topological order.

Use cases: Task scheduling, course prerequisites, build systems, dependency resolution.
Time: O(V+E) | Space: O(V)
 5. DYNAMIC PROGRAMMING (DP)

DP = Break problem into overlapping subproblems + store results (memoization/tabulation) to avoid recomputation.

Two approaches:

• Top-Down (Memoization): Recursive + cache results in a map/array. Natural to write.

• Bottom-Up (Tabulation): Fill table iteratively from base cases. Usually faster (no recursion overhead).
When to use DP: Optimal substructure (optimal solution built from optimal sub-solutions) + Overlapping subproblems.

5.1 0/1 Knapsack

Problem: N items with weight w[i] and value v[i]. Bag capacity W. Maximize value without exceeding capacity. Each item
used at most once.
dp[i][w] = max value using first i items with capacity w
dp[i][w] = max(dp[i-1][w], v[i] + dp[i-1][w - w[i]]) if w[i] <= w
Unbounded Knapsack: Items can be reused. dp[w] = max(dp[w], v[i] + dp[w - w[i]]) (1D array, iterate forward).
Time: O(n*W) | Space: O(n*W), optimized to O(W) with 1D table

5.2 Longest Common Subsequence (LCS)

Find longest sequence present in both strings (not necessarily contiguous).
dp[i][j] = LCS of s1[0..i-1] and s2[0..j-1]
If s1[i]==s2[j]: dp[i][j] = dp[i-1][j-1] + 1 else: dp[i][j] = max(dp[i-1][j], dp[i][j-1])
Related: Longest Common Substring (must be contiguous), Edit Distance.
Time: O(m*n) | Space: O(m*n)

5.3 Longest Increasing Subsequence (LIS)

Find longest subsequence where each element is strictly greater than previous.

DP approach: dp[i] = LIS ending at index i. For each i, look back at all j < i where arr[j] < arr[i]. Time O(n^2).

Optimized: Use binary search + patience sorting. Maintain tails array. O(n log n).
Time: O(n log n) optimized | Space: O(n)

5.4 Edit Distance (Levenshtein Distance)

Minimum operations (insert, delete, replace) to convert string s1 into s2.
If s1[i]==s2[j]: dp[i][j] = dp[i-1][j-1] (no operation needed)
Else: dp[i][j] = 1 + min(dp[i-1][j], // delete from s1
dp[i][j-1], // insert into s1
dp[i-1][j-1]) // replace
Use cases: Spell checkers, DNA sequence alignment, autocorrect.
Time: O(m*n) | Space: O(m*n)

5.5 Coin Change

Given coins and target amount, find minimum number of coins to make the amount.
dp[0]=0. For each amount a from 1 to target:
dp[a] = min(dp[a - coin] + 1) for each coin <= a
Variation: Count number of ways (combinations) → add dp[a - coin] instead of min.
Time: O(n * amount) | Space: O(amount)
 6. STRING ALGORITHMS

6.1 KMP — Knuth Morris Pratt

Pattern matching in O(n+m) without re-scanning. Key idea: build a failure function (lps array) that tells how much to skip on
mismatch.

• lps[i] = length of longest proper prefix of pattern[0..i] that is also a suffix

• On mismatch at position j in pattern, jump to lps[j-1] instead of starting over
Example: Pattern='AAACAAAA'. lps=[0,1,2,0,1,2,3,3]. Avoids redundant comparisons.
Time: O(n+m) | Space: O(m) for lps array

6.2 Rabin-Karp
Uses rolling hash. Compute hash of pattern and each window of text. If hashes match, verify character by character.

Rolling hash: Remove leftmost character, add new rightmost character in O(1) using modular arithmetic.

Best for: Multiple pattern search (compute hash of each pattern, use a set).
Time: O(n+m) avg | O(nm) worst (hash collisions) | Space: O(1)

6.3 Z-Algorithm
Builds Z-array where Z[i] = length of longest substring starting at i that matches a prefix of the string.

Pattern search: Concatenate pattern + '$' + text. Find positions where Z[i] = len(pattern).
Time: O(n+m) | Space: O(n+m)

6.4 Manacher's Algorithm

Finds longest palindromic substring in O(n). Uses the insight that palindromes mirror around center.

Trick: Insert '#' between characters (and at ends) to handle both odd and even length palindromes uniformly.

Example: 'aba' → '#a#b#a#', then find max radius around each center.
Time: O(n) | Space: O(n) — vs O(n^2) naive expand-around-center

6.5 Trie (Prefix Tree) for Strings

Each node represents a character. Path from root to node = prefix. Mark end-of-word nodes. Supports insert, search, and
prefix-search all in O(m) where m = word length.

Use cases: Autocomplete, spell checker, IP routing (longest prefix match), word break problem, boggle solver.
Space: O(n * m * alphabet_size) — more than hash map but allows prefix operations

Quick Complexity Reference

Algorithm/DS Best Average Worst Space

Linear Search O(1) O(n) O(n) O(1)

Binary Search O(1) O(log n) O(log n) O(1)

Bubble Sort O(n) O(n^2) O(n^2) O(1)

Insertion Sort O(n) O(n^2) O(n^2) O(1)

Merge Sort O(n log n) O(n log n) O(n log n) O(n)

Quick Sort O(n log n) O(n log n) O(n^2) O(log n)

Heap Sort O(n log n) O(n log n) O(n log n) O(1)

 Algorithm/DS Best Average Worst Space

Hash Table O(1) O(1) O(n) O(n)

BST O(log n) O(log n) O(n) O(n)

AVL / Red-Black O(log n) O(log n) O(log n) O(n)

Heap (peek) O(1) O(1) O(1) O(n)

Dijkstra - O((V+E)logV) O((V+E)logV) O(V)

Bellman-Ford - O(VE) O(VE) O(V)

BFS / DFS - O(V+E) O(V+E) O(V)

KMP - O(n+m) O(n+m) O(m)

DSA Complete Explanation Guide • Adarsh @ SMVITM • All the best for your exams!