DSA PREREQUISITES & COMPLEXITY ANALYSIS

Below is a complete, structured note set for the Data Structures and Algorithms (DSA) syllabus typically covered in undergraduate CS programs (e.g., GATE, university exams, interviews).
The notes are divided into modules with key concepts, formulas, time/space complexities, code snippets (C++/Python), and practice tips.

---

MODULE 0 – PREREQUISITES & COMPLEXITY ANALYSIS

Topic	Notes
Time Complexity	Big-O, Ω, Θ. Drop lower-order terms & constants.
Space Complexity	Extra memory (excluding input).
Amortized Analysis	Aggregate method, potential method.
Master Theorem	T(n) = aT(n/b) + f(n) → compare f(n) with n^log_b(a)
Common Orders	O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ)

# Example: Binary Search
def binary_search(arr, x):
    l, r = 0, len(arr)-1
    while l <= r:
        m = (l + r) // 2
        if arr[m] == x: return m
        elif arr[m] < x: l = m + 1
        else: r = m - 1
    return -1
# T(n) = O(log n)

---

MODULE 1 – ARRAYS & STRINGS

Sub-topic	Key Points
Static vs Dynamic Arrays	Fixed size vs resizable (vector in C++, list in Python).
Two-Pointer Technique	Sorting + two pointers → O(n).
Sliding Window	Fixed/variable size window for subarray problems.
String Algorithms	KMP, Rabin-Karp, Z-algorithm.

Important Problems

Problem	Approach	Complexity
Trapping Rain Water	Two pointers / precompute left-max, right-max	O(n)
Longest Substring Without Repeating	Sliding window + set	O(n)
Merge Intervals	Sort by start → merge overlapping	O(n log n)

// C++: Merge Intervals
vector<vector<int>> merge(vector<vector<int>>& intervals) {
    sort(intervals.begin(), intervals.end());
    vector<vector<int>> res;
    for (auto& i : intervals) {
        if (res.empty() || res.back()[1] < i[0])
            res.push_back(i);
        else
            res.back()[1] = max(res.back()[1], i[1]);
    }
    return res;
}

---

MODULE 2 – LINKED LISTS

Type	Operations	Notes
Singly	Insert, delete, reverse	Use dummy node for edge cases
Doubly	Two-way traversal
Circular	Josephus, buffer

Key Techniques

• Fast & Slow Pointers → Detect cycle, find middle.
• Reverse List → Iterative (3 pointers) or recursive.
• Merge k Sorted Lists → Min-heap or divide-conquer.

# Detect Cycle (Floyd’s Tortoise-Hare)
def hasCycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast: return True
    return False

---

MODULE 3 – STACKS & QUEUES

Structure	Use Cases	Implementation
Stack	DFS, parentheses, next greater	Array / LinkedList
Queue	BFS, sliding window max	Deque (Python)
Monotonic Stack/Queue	Next greater, stock span

// Monotonic Stack: Next Greater Element
vector<int> nextGreater(vector<int>& arr) {
    int n = arr.size();
    vector<int> res(n, -1);
    stack<int> s;
    for (int i = 0; i < n; i++) {
        while (!s.empty() && arr[s.top()] < arr[i]) {
            res[s.top()] = arr[i];
            s.pop();
        }
        s.push(i);
    }
    return res;
}

---

MODULE 4 – TREES & BINARY TREES

Tree Traversals

Type	Order	Code (Recursive)
Inorder	LNR	left → root → right
Preorder	NLR	root → left → right
Postorder	LRN	left → right → root
Level Order	BFS	Queue

# Iterative Inorder
def inorder(root):
    stack, res = [], []
    curr = root
    while stack or curr:
        while curr:
            stack.append(curr)
            curr = curr.left
        curr = stack.pop()
        res.append(curr.val)
        curr = curr.right
    return res

Binary Search Tree (BST)

• Insert, Search, Delete: O(h)
• Inorder = Sorted order
• Self-balancing: AVL, Red-Black

Important Problems

Problem	Technique
LCA	Recursion / path comparison
Diameter	Height recursion
Serialize/Deserialize	Preorder string
Vertical Order	HashMap<x-coord, list>

---

MODULE 5 – HEAPS (Priority Queues)

Type	Insert	Extract
Min-Heap	O(log n)	O(log n)
Max-Heap	Same	Same

Applications

• Kth largest/smallest → heapq.nlargest/k
• Merge k sorted → min-heap
• Median in stream → two heaps

# Kth Largest Element
import heapq
def findKthLargest(nums, k):
    return heapq.nlargest(k, nums)[-1]

---

MODULE 6 – HASHING

Technique	Collision Resolution
Chaining	LinkedList per bucket
Open Addressing	Linear/Quadratic probing

Design Problems

• LRU Cache → dict + doubly linked list
• Two Sum → hashmap

// LRU Cache (C++)
class LRUCache {
    int cap;
    list<pair<int,int>> dll;  // {key, val}
    unordered_map<int, list<pair<int,int>>::iterator> mp;
public:
    LRUCache(int capacity) : cap(capacity) {}
    int get(int key) {
        if (mp.find(key) == mp.end()) return -1;
        dll.splice(dll.begin(), dll, mp[key]);
        mp[key] = dll.begin();
        return dll.begin()->second;
    }
    void put(int key, int value) {
        if (get(key) != -1) {
            dll.begin()->second = value;
            return;
        }
        if (dll.size() == cap) {
            int del = dll.back().first;
            dll.pop_back();
            mp.erase(del);
        }
        dll.push_front({key, value});
        mp[key] = dll.begin();
    }
};

---

MODULE 7 – GRAPHS

Representations

Type	Space	Use
Adjacency List	O(V+E)	Most cases
Adjacency Matrix	O(V²)	Dense graphs

Algorithms

Algorithm	Use	Complexity
BFS	Shortest path (unweighted)	O(V+E)
DFS	Cycle, topo, SCC	O(V+E)
Dijkstra	Shortest path (non-negative)	O((V+E)log V)
Bellman-Ford	Negative weights	O(VE)
Floyd-Warshall	All-pairs	O(V³)
Kruskal	MST	O(E log E)
Prim	MST	O(E log V)
Topological Sort	Kahn’s / DFS	O(V+E)

# Dijkstra (Python)
import heapq
def dijkstra(graph, start):
    pq = [(0, start)]
    dist = {node: float('inf') for node in graph}
    dist[start] = 0
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]: continue
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(pq, (dist[v], v))
    return dist

---

MODULE 8 – DYNAMIC PROGRAMMING

Types

Type	Example
0/1 Knapsack	Standard
Unbounded Knapsack	Coin change
LCS, LIS	Sequence
Matrix Chain	Optimal parenthesization
DP on Grids	Min path, unique paths

State Definition Tips

• dp[i][j] → answer for first i/j elements
• Recurrence: dp[i] = min/max over choices

# 0/1 Knapsack
def knapsack(W, wt, val):
    n = len(val)
    dp = [[0]*(W+1) for _ in range(n+1)]
    for i in range(1, n+1):
        for w in range(1, W+1):
            if wt[i-1] <= w:
                dp[i][w] = max(val[i-1] + dp[i-1][w-wt[i-1]], dp[i-1][w])
            else:
                dp[i][w] = dp[i-1][w]
    return dp[n][W]

---

MODULE 9 – GREEDY ALGORITHMS

Problem	Greedy Choice
Activity Selection	Earliest finish
Huffman Coding	Min-frequency merge
Fractional Knapsack	Value/weight ratio

---

MODULE 10 – ADVANCED TOPICS

Topic	Key Idea
Trie	Prefix tree → autocomplete, spell check
Segment Tree	Range queries (sum, min, max)
Fenwick Tree (BIT)	Prefix sums, point updates
Disjoint Set (Union-Find)	Path compression + union by rank

// Union-Find
vector<int> parent, rank;
void make_set(int v) {
    parent[v] = v; rank[v] = 0;
}
int find_set(int v) {
    if (v == parent[v]) return v;
    return parent[v] = find_set(parent[v]);
}
void union_sets(int a, int b) {
    a = find_set(a); b = find_set(b);
    if (a != b) {
        if (rank[a] < rank[b]) swap(a,b);
        parent[b] = a;
        if (rank[a] == rank[b]) rank[a]++;
    }
}

---

PRACTICE ROADMAP

Platform	Focus
LeetCode	Tagged: Easy → Medium → Hard
Codeforces	Div 2 A/B for speed
HackerRank	30 Days of Code
GATE PYQs	Previous 10 years

---

CHEAT SHEET (One-Page)

Arrays      : Two-pointer, Sliding Window, Prefix Sum
LL          : Fast-Slow, Reverse, Dummy Node
Stack       : Monotonic, Parentheses
Tree        : Inorder=Sorted, LCA=Paths, Diameter=Height
Heap        : Kth, Merge K, Median Stream
Hash        : Two Sum, LRU, Subarray Sum
Graph       : BFS=SP, DFS=Topo, Dijkstra=PriorityQ
DP          : 0/1 vs Unbounded, LCS, Grid
Greedy      : Activity, Huffman, Fractional
Advanced    : Trie, Segment Tree, BIT, DSU

---

Save this as PDF/notes for revision.
Practice 2 problems daily from each module.
Revise complexity + code template before interviews.

Let me know if you want PDF version, problem list per module, or video explanations.