Data Structures and Algorithms

Data Structures and Algorithms explore how information is organized, stored, and manipulated efficiently to solve computational problems, covering core structures like arrays, trees, graphs, and hash tables alongside algorithmic techniques like sorting, searching, and recursion. It examines how choosing the right structure and approach directly impacts a program’s speed and efficiency, using concepts like time and space complexity to measure and compare performance. This field blends theoretical analysis with practical implementation, showing how well-designed algorithms and data structures form the foundation of efficient, scalable software. At its core, Data Structures and Algorithms ask how we can organize information and logic to solve problems as efficiently as possible. Where efficient thinking becomes efficient code.

Introduction To Data Structures and Alogorithms

Content Overview

this is code

Data Structures & Algorithms

Complete DSA Roadmap

Stage 1: Linear Data Structures
├── Arrays
├── Strings
├── Linked Lists
├── Stacks
└── Queues

Stage 2: Non-Linear Data Structures
├── Trees
├── Heaps
└── Hashing

Stage 3: Graphs
├── Graph Fundamentals
├── Graph Traversal (BFS, DFS)
├── Shortest Path Algorithms
├── Minimum Spanning Tree
└── Advanced Graph Algorithms

Stage 4: Searching & Sorting
├── Linear Search
├── Binary Search
├── Bubble, Selection, Insertion Sort
├── Merge Sort
├── Quick Sort
└── Heap Sort

Stage 5: Advanced Algorithm Techniques
├── Dynamic Programming
├── Greedy Algorithms
├── Backtracking
├── Bitwise Algorithms
└── Mathematical Algorithms

Stage 6: Advanced Data Structures
├── Trie
├── Disjoint Set (Union-Find)
├── Segment Tree
├── Fenwick Tree
├── Sparse Table
└── Suffix Structures

Stage 7: Algorithm Engineering
├── Optimization Techniques
├── Competitive Programming
├── C++ STL Mastery
└── Algorithm-Based Projects

Stage 8: Advanced Topics
├── Parallel Algorithms
├── Distributed Algorithms
├── Approximation Algorithms
└── Machine Learning Algorithms

PART 1: DATA STRUCTURES

1. Foundations

1.1 What Is Data?

Data is raw, unprocessed information stored in a computer. It is the foundation upon which all programs operate.

In programming, we store data inside variables:

int age = 10;
string name = "Ali";
float marks = 95.5;

Real-World Insight: Real programs do not store just one value. Facebook stores billions of users; Google stores billions of webpages; banks store millions of transactions. This massive scale requires organized ways to store and access data – leading us to Data Structures.

1.2 What Is a Data Structure?

A Data Structure is a specialized way of organizing and storing data in memory so that it can be accessed and used efficiently.

Think of it like organizing physical objects in real life:

Common Data Structures & Real-Life Analogies

1.3 Why Data Structures Matter

Example: Searching in a list of 1 million numbers

1.4 Real-World Applications

2. Linear Data Structures

“Linear” means data is stored in a straight line, one element after another.

Example: 10 → 20 → 30 → 40 → 50

2.1 Arrays

What Is an Array?

An Array is a collection of elements of the same type stored in contiguous (side-by-side, no gaps) memory locations.

Example: [10, 20, 30, 40, 50]

How Arrays Work in Memory

Index:     0     1     2     3     4
        --------------------------------
Value:    10 |  20 |  30 |  40 |  50
        --------------------------------
Address:  100   104   108   112   116

Address Formula:

address = base + (index × size_of_element)

Example: arr[2] address = 100 + (2 × 4) = 108

Why O(1) Access? The CPU uses simple arithmetic (base + offset) to find any element directly – it doesn’t loop through elements. This is only possible because all elements sit side-by-side in memory with equal sizes.

Array Types

Array Complexity Summary

Array Operations in C++

1D Array:

int arr[5] = {1, 2, 3, 4, 5};
cout << arr[2];  // Output: 3

2D Array (Matrix):

int matrix[3][3] = {
    {1, 2, 3},
    {4, 5, 6},
    {7, 8, 9}
};

Dynamic Array:

vector<int> arr;
arr.push_back(10);
arr.push_back(20);

Advanced Array Techniques

1. Prefix Sum – Answer range queries in O(1)

prefix[0] = arr[0];
for (int i = 1; i < n; i++)
    prefix[i] = prefix[i-1] + arr[i];

// Sum from l to r:
sum = prefix[r] - (l > 0 ? prefix[l-1] : 0);

2. Sliding Window – Find max/min in subarrays

int windowSum = 0;
for (int i = 0; i < k; i++) windowSum += arr[i];
int maxSum = windowSum;

for (int i = k; i < n; i++) {
    windowSum += arr[i] - arr[i-k];
    maxSum = max(maxSum, windowSum);
}

3. Kadane’s Algorithm – Maximum subarray sum

int maxSum = arr[0], curr = arr[0];
for (int i = 1; i < n; i++) {
    curr = max(arr[i], curr + arr[i]);
    maxSum = max(maxSum, curr);
}

Time Complexity: O(n)

2.2 Strings

What Is a String?

A String is a sequence of characters stored in contiguous memory, terminated by a null character (\0).

Example: "Hello" → H e l l o \0

C-Style Strings

char name[6] = "Hello";  // Fixed size

Limitations:

• Fixed size
• Manual operations
• Unsafe

C++ Strings (Recommended)

#include <string>
string name = "Hello";

Advantages:

• Dynamic size
• Easy operations
• Memory safe

Common String Operations

String Algorithms

1. Palindrome Check

bool isPalindrome(string s) {
    int l = 0, r = s.length() - 1;
    while (l < r) {
        if (s[l] != s[r]) return false;
        l++; r--;
    }
    return true;
}

2. Naive Pattern Matching

Searches a pattern inside text by checking every position.

Time Complexity: O(n × m)

3. KMP Algorithm

Improves pattern search using a prefix function (LPS array).

Time Complexity: O(n + m)

2.3 Linked Lists

What Is a Linked List?

A Linked List is a linear data structure where elements (nodes) are stored in non-contiguous memory locations, connected by pointers.

Unlike arrays, nodes are scattered in memory – they are connected by pointers, not by physical proximity. This gives O(1) insertion/deletion once you’re at the right position, but O(n) access.

Node Structure

struct Node {
    int data;
    Node* next;  // Pointer to the next node
};

Types of Linked Lists

1. Singly Linked List

Each node stores data and a pointer to the next node.

[10|→] → [20|→] → [30|→] → NULL

Traversal:

Node* temp = head;
while (temp != NULL) {
    cout << temp->data;
    temp = temp->next;
}

2. Doubly Linked List

Each node stores data, a pointer to the next node, and a pointer to the previous node.

NULL ← [10|↔|20|↔|30] → NULL

Structure:

struct Node {
    int data;
    Node* prev;
    Node* next;
};

3. Circular Linked List

The last node points back to the first node.

[10] → [20] → [30]
 ↑             ↓
 └─────────────┘

Linked List Operations

1. Insert at Beginning

Node* newNode = new Node{data, head};
head = newNode;

2. Insert at End

Node* temp = head;
while (temp->next != NULL)
    temp = temp->next;
temp->next = new Node{data, NULL};

3. Delete a Node

Node* temp = head;
while (temp->next != target) {
    temp = temp->next;
}
temp->next = target->next;
delete target;

4. Reverse a Linked List

Node* prev = NULL;
Node* curr = head;
while (curr != NULL) {
    Node* next = curr->next;
    curr->next = prev;
    prev = curr;
    curr = next;
}
head = prev;

5. Detect Cycle (Floyd’s Algorithm)

Node* slow = head;
Node* fast = head;
while (fast != NULL && fast->next != NULL) {
    slow = slow->next;
    fast = fast->next->next;
    if (slow == fast) return true;  // Cycle detected
}
return false;

Complexity Comparison: Array vs Linked List

2.4 Stacks

What Is a Stack?

A Stack is a linear data structure that follows the LIFO (Last In, First Out) principle. The last element added is the first element removed.

Real-Life Analogy: A stack of plates – you can only add to or remove from the top.

    30  ← top (last in, first out)
    20
    10

Stack Operations

Stack Implementation in C++ (STL)

#include <stack>

stack<int> s;

s.push(10);    // Stack: [10]
s.push(20);    // Stack: [10, 20]
s.push(30);    // Stack: [10, 20, 30]

cout << s.top();  // Output: 30

s.pop();       // Stack: [10, 20]
cout << s.top();  // Output: 20

Stack Implementation Using Array

class Stack {
    int arr[100];
    int topIndex;

public:
    Stack() { topIndex = -1; }

    void push(int x) {
        if (topIndex >= 99) return;  // Overflow
        arr[++topIndex] = x;
    }

    void pop() {
        if (topIndex < 0) return;    // Underflow
        topIndex--;
    }

    int top() {
        return arr[topIndex];
    }

    bool empty() {
        return topIndex == -1;
    }
};

Stack Applications

Example: Balanced Parentheses

Problem: Check if the string ((())) is balanced.

Algorithm:

1. Push ( onto stack
2. Pop when ) is encountered
3. If stack is empty at the end → balanced

bool isBalanced(string s) {
    stack<char> st;
    for (char c : s) {
        if (c == '(' || c == '[' || c == '{')
            st.push(c);
        else {
            if (st.empty()) return false;
            if (c == ')' && st.top() != '(') return false;
            if (c == ']' && st.top() != '[') return false;
            if (c == '}' && st.top() != '{') return false;
            st.pop();
        }
    }
    return st.empty();
}

2.5 Queues

What Is a Queue?

A Queue is a linear data structure that follows the FIFO (First In, First Out) principle. The first element added is the first element removed.

Real-Life Analogy: A line of people at a ticket counter – the first person in line is the first person served.

front → [10] → [20] → [30] ← rear

Queue Operations

Queue Implementation in C++ (STL)

#include <queue>

queue<int> q;

q.push(10);    // Queue: [10]
q.push(20);    // Queue: [10, 20]
q.push(30);    // Queue: [10, 20, 30]

cout << q.front();  // Output: 10

q.pop();       // Queue: [20, 30]
cout << q.front();  // Output: 20

Priority Queue

A Priority Queue is a special queue where elements are removed based on priority (highest priority first).

Default: Max-heap (largest element highest priority)

#include <queue>

priority_queue<int> pq;

pq.push(10);
pq.push(50);
pq.push(30);

cout << pq.top();  // Output: 50
pq.pop();          // Removes 50
cout << pq.top();  // Output: 30

Min-heap:

priority_queue<int, vector<int>, greater<int>> pq;

Queue Applications

Example: Queue Implementation Using Array

class Queue {
    int arr[100];
    int frontIdx, rearIdx;

public:
    Queue() { frontIdx = 0; rearIdx = -1; }

    void push(int x) {
        arr[++rearIdx] = x;
    }

    void pop() {
        frontIdx++;
    }

    int front() {
        return arr[frontIdx];
    }

    bool empty() {
        return frontIdx > rearIdx;
    }
};

3. Non-Linear Data Structures

“Non-Linear” means data is not stored in a straight line. Instead, data forms hierarchical or network relationships.

Linear Structure:

10 → 20 → 30 → 40

Non-Linear Structure:

       10
      /  \
    20    30
   /  \
 40   50

3.1 Trees

What Is a Tree?

A Tree is a hierarchical data structure consisting of nodes connected by edges. Each node has a parent-child relationship with other nodes.

Real-Life Example: Family tree

       Grandfather
       /        \
   Father      Uncle
   /    \
Child1  Child2

Computer Science Example:

        10        ← Root node
       /  \
     20   30      ← Internal nodes
    /  \
  40   50         ← Leaf nodes

Important Tree Terminology

Binary Tree

A Binary Tree is a tree where each node has at most two children (left and right).

        10
       /  \
     20    30
    /
  40

Node Structure in C++:

struct Node {
    int data;
    Node* left;
    Node* right;
};

Creating a Node:

Node* root = new Node();
root->data = 10;
root->left = NULL;
root->right = NULL;

Tree Traversals

Traversal means visiting every node in a specific order.

Example Tree:

        10
       /  \
     20    30
    /  \
  40   50

1. Inorder Traversal (Left → Root → Right)

40, 20, 50, 10, 30

void inorder(Node* root) {
    if (root == NULL) return;
    inorder(root->left);
    cout << root->data << " ";
    inorder(root->right);
}

2. Preorder Traversal (Root → Left → Right)

10, 20, 40, 50, 30

void preorder(Node* root) {
    if (root == NULL) return;
    cout << root->data << " ";
    preorder(root->left);
    preorder(root->right);
}

3. Postorder Traversal (Left → Right → Root)

40, 50, 20, 30, 10

void postorder(Node* root) {
    if (root == NULL) return;
    postorder(root->left);
    postorder(root->right);
    cout << root->data << " ";
}

4. Level Order Traversal (BFS)

10, 20, 30, 40, 50

void levelOrder(Node* root) {
    queue<Node*> q;
    q.push(root);

    while (!q.empty()) {
        Node* node = q.front();
        q.pop();
        cout << node->data << " ";

        if (node->left) q.push(node->left);
        if (node->right) q.push(node->right);
    }
}

Height of a Tree

Height = Longest path from root to a leaf node

int height(Node* root) {
    if (root == NULL) return 0;
    return 1 + max(height(root->left), height(root->right));
}

Binary Search Tree (BST)

A BST is a binary tree with the property:

• All nodes in the left subtree have values less than the root
• All nodes in the right subtree have values greater than the root

Example:

        50
       /  \
     30    70
    / \    / \
  20  40 60  80

Search in BST:

Node* search(Node* root, int key) {
    if (root == NULL || root->data == key)
        return root;

    if (key < root->data)
        return search(root->left, key);

    return search(root->right, key);
}

Time Complexity: O(log n)

Insert in BST:

Node* insert(Node* root, int val) {
    if (root == NULL)
        return new Node{val, NULL, NULL};

    if (val < root->data)
        root->left = insert(root->left, val);
    else
        root->right = insert(root->right, val);

    return root;
}

Find Minimum:

Node* findMin(Node* root) {
    while (root->left != NULL)
        root = root->left;
    return root;
}

Advanced Trees

1. AVL Tree

• Self-balancing BST
• Condition: |height(left) - height(right)| ≤ 1
• Rotations restore balance

2. Red-Black Tree

• Used in C++ map and set
• Rules: Root black, no two red nodes together
• Self-balancing automatically

3. Segment Tree

• Used for range queries (sum, min, max)
• Time: Query O(log n), Update O(log n)

4. Fenwick Tree (Binary Indexed Tree)

• Used for prefix sums
• Time: Query O(log n), Update O(log n)

5. Trie (Prefix Tree)

• Used for string storage and search
• Time: Insert/Search O(m) where m = string length

3.2 Heaps

What Is a Heap?

A Heap is a special tree-based data structure that satisfies the heap property:

Max Heap Example:

        50
       /  \
     30    40
    / \
  10  20

Min Heap Example:

        10
       /  \
     20    30
    / \
  40  50

Heap as an Array

Heaps are usually stored in arrays for efficiency.

Array Representation:

Index:  0   1   2   3   4
Value: 10  20  30  40  50

Index Relations:

• Left child: 2 × i + 1
• Right child: 2 × i + 2
• Parent: (i - 1) / 2

Heapify

Heapify is the process of fixing the heap property after insertion or deletion.

Example: After deleting root, swap down to maintain heap property.

C++ Priority Queue (Heap Implementation)

#include <queue>

// Max Heap (default)
priority_queue<int> pq;
pq.push(10);
pq.push(30);
pq.push(20);
cout << pq.top();  // Output: 30

// Min Heap
priority_queue<int, vector<int>, greater<int>> minPq;

Heap Applications

Heap Sort

Algorithm:

1. Build max heap
2. Swap root with last element
3. Heapify reduced heap
4. Repeat

Time Complexity: O(n log n)

3.3 Hashing

What Is Hashing?

Hashing is a technique that maps data to a fixed-size value (hash code) using a hash function, enabling O(1) average-time lookups.

Key → Index Mapping:

key → hash function → index

Example:

key = 25
hash function: index = key % 10
index = 25 % 10 = 5

Hash Table Structure

Index   Value
0
1
2
3
4
5   → 25
6
7
8
9

Collision Problem

Collision: Two different keys map to the same index.

15 % 10 = 5
25 % 10 = 5

Both keys map to index 5.

Collision Resolution Techniques

1. Separate Chaining

Each index stores a linked list of all keys.

Index 5 → 15 → 25 → 35

2. Open Addressing

Find the next empty slot (linear probing, quadratic probing, double hashing).

index = 5 (taken)
index = 6 (taken)
index = 7 (empty) → insert here

C++ Hash Tables

1. unordered_map (Key-Value Pair)

#include <unordered_map>

unordered_map<int, string> m;

m[1] = "Ali";
m[2] = "Sara";

cout << m[1];  // Output: Ali
cout << m[2];  // Output: Sara

2. unordered_set (Unique Values)

#include <unordered_set>

unordered_set<int> s;

s.insert(10);
s.insert(20);
s.insert(10);  // Duplicate ignored

// Contains: {10, 20}

Hashing Applications

Example: Frequency Counting

unordered_map<int, int> freq;

for (int x : arr)
    freq[x]++;

Time Complexity: O(n)

4. Graphs

4.1 What Is a Graph?

A Graph is a data structure used to represent connections between objects. It consists of:

• Vertices (Nodes): Objects or entities
• Edges (Connections): Relationships between objects

Example Graph:

A ----- B
|       |
|       |
C ----- D

Vertices: A, B, C, D
Edges: Connections between them

Real-Life Examples

1. Social Network:

Ali ---- Ahmed
  |        |
Sara ---- Usman

Users are vertices, friendships are edges.

2. Road Map:

CityA ---- CityB
   |         |
CityC ---- CityD

Cities are vertices, roads are edges.

Types of Graphs

1. Undirected Graph

• Edges have no direction
• A ---- B means A connects to B and B connects to A

2. Directed Graph (Digraph)

• Edges have direction
• A → B means A connects to B, but B does not connect to A
• Used in: Web links, task dependencies

3. Weighted Graph

• Edges have cost or weight

A --5-- B
|       |
3       2
|       |
C --4-- D

• Used in: Google Maps, network routing

4.2 Graph Representation

Computers store graphs using three main methods.

1. Adjacency Matrix

A 2D matrix where matrix[i][j] = 1 means an edge exists.

Graph:

A -- B
|
C

Matrix:

    A B C
A   0 1 1
B   1 0 0
C   1 0 0

int graph[3][3] = {
    {0, 1, 1},
    {1, 0, 0},
    {1, 0, 0}
};

Advantage: O(1) edge checking
Disadvantage: O(V²) memory

2. Adjacency List

Each node stores a list of its neighbors.

Graph:

A -- B
|
C

List:

A → B → C
B → A
C → A

vector<int> adj[5];

adj[0].push_back(1);  // A → B
adj[0].push_back(2);  // A → C

Advantage: O(V + E) memory
Disadvantage: O(degree) edge checking

3. Edge List

Store all edges as pairs.

vector<pair<int, int>> edges;
edges.push_back({0, 1});  // A-B
edges.push_back({0, 2});  // A-C

Used in: Kruskal’s algorithm

Complexity Comparison

4.3 Graph Traversal

Traversal means visiting every vertex in the graph.

Breadth First Search (BFS)

BFS explores level by level (like a wave).

Graph:

      A
     / \
    B   C
   /
  D

Traversal: A → B → C → D

Algorithm:

1. Start from source node
2. Visit neighbors
3. Add neighbors to queue
4. Repeat until queue empty

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

vector<int> adj[10];
bool visited[10];

void bfs(int start) {
    queue<int> q;
    q.push(start);
    visited[start] = true;

    while (!q.empty()) {
        int node = q.front();
        q.pop();

        cout << node << " ";

        for (int neighbor : adj[node]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                q.push(neighbor);
            }
        }
    }
}

Time Complexity: O(V + E)

Depth First Search (DFS)

DFS explores as deep as possible before backtracking.

Graph:

      A
     / \
    B   C
   /
  D

Traversal: A → B → D → C

Algorithm:

1. Start from source node
2. Recursively visit unvisited neighbors
3. Backtrack when no unvisited neighbors remain

void dfs(int node) {
    visited[node] = true;
    cout << node << " ";

    for (int neighbor : adj[node]) {
        if (!visited[neighbor])
            dfs(neighbor);
    }
}

Time Complexity: O(V + E)

BFS vs DFS Comparison

4.4 Connected Components

A connected component is a group of nodes where every node can reach every other node.

Example:

A -- B -- C

D -- E

Components:

• {A, B, C}
• {D, E}

void findComponents() {
    int component = 0;

    for (int i = 0; i < V; i++) {
        if (!visited[i]) {
            component++;
            dfs(i);  // Mark all nodes in this component
        }
    }
}

4.5 Cycle Detection

A cycle exists when a path starts and ends at the same node.

Example with Cycle:

A → B → C
↑       ↓
└───────┘

Cycle Detection in Undirected Graph:

bool hasCycle(int node, int parent) {
    visited[node] = true;

    for (int neighbor : adj[node]) {
        if (!visited[neighbor]) {
            if (hasCycle(neighbor, node))
                return true;
        }
        else if (neighbor != parent) {
            return true;  // Back edge found
        }
    }
    return false;
}

Cycle Detection in Directed Graph:

// Track recursion stack
bool dfsCycle(int node) {
    visited[node] = true;
    recStack[node] = true;

    for (int neighbor : adj[node]) {
        if (!visited[neighbor]) {
            if (dfsCycle(neighbor)) return true;
        }
        else if (recStack[neighbor]) {
            return true;  // Back edge in recursion
        }
    }

    recStack[node] = false;
    return false;
}

4.6 Shortest Path Algorithms

Dijkstra’s Algorithm

Finds the shortest path from a source to all nodes in a weighted graph (no negative edges).

Algorithm:

1. Start from source node (distance = 0)
2. Always pick unvisited node with smallest distance
3. Update distances to neighbors
4. Repeat until all nodes visited

#include <queue>
#include <vector>

vector<int> dijkstra(int source, int V) {
    vector<int> dist(V, INT_MAX);
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;

    dist[source] = 0;
    pq.push({0, source});

    while (!pq.empty()) {
        int d = pq.top().first;
        int node = pq.top().second;
        pq.pop();

        if (d > dist[node]) continue;

        for (auto edge : adj[node]) {
            int neighbor = edge.first;
            int weight = edge.second;

            if (dist[node] + weight < dist[neighbor]) {
                dist[neighbor] = dist[node] + weight;
                pq.push({dist[neighbor], neighbor});
            }
        }
    }

    return dist;
}

Time Complexity: O(E log V)

Applications:

• Google Maps
• Network routing
• GPS navigation

Bellman-Ford Algorithm

Handles negative weights and detects negative cycles.

void bellmanFord(int source, int V, vector<Edge>& edges) {
    vector<int> dist(V, INT_MAX);
    dist[source] = 0;

    // Relax edges V-1 times
    for (int i = 1; i < V; i++) {
        for (Edge edge : edges) {
            if (dist[edge.u] + edge.w < dist[edge.v])
                dist[edge.v] = dist[edge.u] + edge.w;
        }
    }

    // Detect negative cycles
    for (Edge edge : edges) {
        if (dist[edge.u] + edge.w < dist[edge.v]) {
            cout << "Negative cycle detected";
            return;
        }
    }
}

Time Complexity: O(V × E)

Floyd-Warshall Algorithm

Finds shortest paths between all pairs of nodes.

void floydWarshall(int V) {
    int dist[V][V];

    // Initialize matrix
    for (int i = 0; i < V; i++)
        for (int j = 0; j < V; j++)
            dist[i][j] = (i == j) ? 0 : INF;

    // Run Floyd-Warshall
    for (int k = 0; k < V; k++)
        for (int i = 0; i < V; i++)
            for (int j = 0; j < V; j++)
                if (dist[i][k] + dist[k][j] < dist[i][j])
                    dist[i][j] = dist[i][k] + dist[k][j];
}

Time Complexity: O(V³)

4.7 Minimum Spanning Tree (MST)

A Minimum Spanning Tree connects all nodes with the minimum total edge weight.

Example Graph:

A --1-- B
|       |
3       2
|       |
C --4-- D

MST edges: A-B (1), B-D (2), A-C (3) = Total: 6

Prim’s Algorithm

Builds MST by expanding the tree from a starting node.

int prim(int V) {
    vector<int> key(V, INT_MAX);
    vector<bool> inMST(V, false);
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;

    key[0] = 0;
    pq.push({0, 0});

    int totalWeight = 0;

    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();

        if (inMST[u]) continue;
        inMST[u] = true;
        totalWeight += key[u];

        for (auto edge : adj[u]) {
            int v = edge.first;
            int weight = edge.second;

            if (!inMST[v] && weight < key[v]) {
                key[v] = weight;
                pq.push({key[v], v});
            }
        }
    }

    return totalWeight;
}

Kruskal’s Algorithm

Builds MST by adding smallest edges without creating cycles.

int find(int x) {
    if (parent[x] != x)
        parent[x] = find(parent[x]);
    return parent[x];
}

void unionSet(int a, int b) {
    parent[find(a)] = find(b);
}

int kruskal(int V, vector<Edge>& edges) {
    sort(edges.begin(), edges.end());

    for (int i = 0; i < V; i++)
        parent[i] = i;

    int totalWeight = 0;

    for (Edge edge : edges) {
        if (find(edge.u) != find(edge.v)) {
            unionSet(edge.u, edge.v);
            totalWeight += edge.weight;
        }
    }

    return totalWeight;
}

4.8 Advanced Graph Algorithms

Topological Sort

Orders tasks based on dependencies. Used when tasks have prerequisites.

Example: A must happen before B, B before C

Graph: A → B → C

Topological Order: A, B, C

void topologicalSort() {
    queue<int> q;
    vector<int> inDegree(V, 0);

    // Count incoming edges
    for (int i = 0; i < V; i++)
        for (int neighbor : adj[i])
            inDegree[neighbor]++;

    // Add nodes with 0 in-degree
    for (int i = 0; i < V; i++)
        if (inDegree[i] == 0)
            q.push(i);

    while (!q.empty()) {
        int node = q.front();
        q.pop();
        cout << node << " ";

        for (int neighbor : adj[node]) {
            inDegree[neighbor]--;
            if (inDegree[neighbor] == 0)
                q.push(neighbor);
        }
    }
}

Applications:

• Build systems (make)
• Course scheduling
• Dependency resolution

Strongly Connected Components (SCC)

A group where every node can reach every other node.

Example: A ↔ B ↔ C

Algorithms:

1. Kosaraju’s Algorithm (2 DFS passes)
2. Tarjan’s Algorithm (1 DFS pass)

Articulation Points

Nodes that disconnect the graph if removed.

A -- B -- C
     |
     D

Removing B disconnects A, C, D → B is an articulation point.

Eulerian Path

A path that visits every edge exactly once.

Condition: Exactly 0 or 2 nodes have odd degree.

Example: A → B → C → A

Hamiltonian Path

A path that visits every vertex exactly once.

Example: A → B → C → D

5. Advanced Data Structures

5.1 Trie (Prefix Tree)

A Trie is a tree used to store strings efficiently for prefix-based operations.

Example Words: cat, car, cart, dog

        root
        /  \
       c    d
       |    |
       a    o
      / \    |
     t   r   g
          |
          t

Each path from root forms a word prefix.

Node Structure:

struct TrieNode {
    TrieNode* child[26];
    bool isEnd;
};

Insert Operation:

void insert(string word) {
    TrieNode* node = root;

    for (char c : word) {
        int index = c - 'a';
        if (node->child[index] == NULL)
            node->child[index] = new TrieNode();
        node = node->child[index];
    }

    node->isEnd = true;
}

Search Operation:

bool search(string word) {
    TrieNode* node = root;

    for (char c : word) {
        int index = c - 'a';
        if (node->child[index] == NULL)
            return false;
        node = node->child[index];
    }

    return node->isEnd;
}

Applications:

• Autocomplete
• Spell checking
• Search engines
• Dictionary systems

Time Complexity: O(m) where m = string length

5.2 Disjoint Set (Union-Find)

Used to track connected components efficiently.

Operations:

• find(x): Find the set containing x
• union(x, y): Merge the sets containing x and y

int parent[100];

int find(int x) {
    if (parent[x] != x)
        parent[x] = find(parent[x]);  // Path compression
    return parent[x];
}

void unite(int a, int b) {
    parent[find(a)] = find(b);
}

Time Complexity: Almost O(1) (Ackermann inverse)

Applications:

• Kruskal’s MST algorithm
• Network connectivity
• Social network analysis
• Dynamic connectivity

5.3 Segment Tree

A Segment Tree is used for range queries and updates on arrays.

Example Array: [2, 4, 5, 7, 8, 9]

Segment Tree Structure:

              35
           /       \
         11         24
        /  \       /  \
       6    5    15    9

Operations:

• Range Sum Query: O(log n)
• Range Minimum Query: O(log n)
• Update: O(log n)

int tree[4 * n];

void build(int node, int l, int r) {
    if (l == r) {
        tree[node] = arr[l];
        return;
    }

    int mid = (l + r) / 2;
    build(node * 2, l, mid);
    build(node * 2 + 1, mid + 1, r);

    tree[node] = tree[node * 2] + tree[node * 2 + 1];
}

int query(int node, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) return tree[node];
    if (r < ql || qr < l) return 0;

    int mid = (l + r) / 2;
    return query(node * 2, l, mid, ql, qr) +
           query(node * 2 + 1, mid + 1, r, ql, qr);
}

Applications:

• Range sum queries
• Range minimum/maximum
• Lazy propagation
• Competitive programming

5.4 Fenwick Tree (Binary Indexed Tree)

A simpler alternative to segment trees for prefix sums.

int BIT[n + 1];

void update(int idx, int val) {
    while (idx <= n) {
        BIT[idx] += val;
        idx += idx & -idx;
    }
}

int query(int idx) {
    int sum = 0;
    while (idx > 0) {
        sum += BIT[idx];
        idx -= idx & -idx;
    }
    return sum;
}

// Range sum: query(r) - query(l-1)

Time Complexity: O(log n) for both update and query

5.5 Sparse Table

Used for static range queries (array does NOT change).

Query Time: O(1)

Preprocessing: O(n log n)

int st[n][LOG];

void build() {
    for (int i = 0; i < n; i++)
        st[i][0] = arr[i];

    for (int j = 1; (1 << j) <= n; j++) {
        for (int i = 0; i + (1 << j) <= n; i++) {
            st[i][j] = min(st[i][j-1], st[i + (1 << (j-1))][j-1]);
        }
    }
}

int query(int l, int r) {
    int j = log2(r - l + 1);
    return min(st[l][j], st[r - (1 << j) + 1][j]);
}

Applications:

• Range minimum queries
• Range maximum queries
• GCD queries

5.6 Suffix Structures

Used for advanced string processing.

Example String: banana

Suffixes:

banana
anana
nana
ana
na
a

Applications:

• Pattern matching
• DNA sequence analysis
• Search engines
• Text compression

5.7 Advanced Graph Structures

Key Algorithms:

PART 2: ALGORITHMS & ANALYSIS

1. Algorithm Analysis (DAA)

1.1 What Is Algorithm Analysis?

Algorithm Analysis is the study of how to design algorithms and measure their efficiency.

Design → Creating an algorithm to solve a problem
Analysis → Measuring how fast and memory-efficient it is

Key Metrics

1.2 Asymptotic Notations

Asymptotic notation describes the growth rate of an algorithm’s running time.

Big-O is the most important for practical analysis.

Common Complexities

Complexity Hierarchy

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)

Algorithm Analysis Example

for (int i = 0; i < n; i++) {
    cout << i;  // O(1) operation
}

Time Complexity: O(n) – Linear

Nested Loops

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        cout << i << j;  // O(1) operation
    }
}

Time Complexity: O(n²) – Quadratic

1.3 Recursion Analysis

Recursion occurs when a function calls itself.

Example: Factorial

int factorial(int n) {
    if (n == 0) return 1;
    return n * factorial(n - 1);
}

Call Stack:

factorial(4)
→ 4 * factorial(3)
→ 3 * factorial(2)
→ 2 * factorial(1)
→ 1

Time Complexity: O(n)

Recurrence Relations

A recurrence relation defines a function in terms of its smaller inputs.

Example: Fibonacci

F(n) = F(n-1) + F(n-2)

Master Theorem

Used to solve divide-and-conquer recurrences.

General Form:

T(n) = aT(n/b) + f(n)

Example: Merge Sort

T(n) = 2T(n/2) + n

Result: O(n log n)

Master Theorem Cases

2. Searching Algorithms

2.1 Linear Search

Checks every element one by one.

Example: [10, 20, 30, 40, 50], find 30

Steps:

1. 10 → no
2. 20 → no
3. 30 → found

int linearSearch(int arr[], int n, int key) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == key)
            return i;
    }
    return -1;
}

Time Complexity: O(n)
Best Case: O(1)
Space Complexity: O(1)

2.2 Binary Search

Works only on sorted arrays. Divides the search space in half each step.

Example: [10, 20, 30, 40, 50], find 30

Steps:

1. Middle = 30 → found

Example: [10, 20, 30, 40, 50], find 20

Steps:

1. Middle = 30 > 20 → search left
2. Middle = 20 → found

int binarySearch(int arr[], int l, int r, int key) {
    while (l <= r) {
        int mid = (l + r) / 2;

        if (arr[mid] == key)
            return mid;

        else if (arr[mid] < key)
            l = mid + 1;

        else
            r = mid - 1;
    }

    return -1;
}

Time Complexity: O(log n)
Space Complexity: O(1) (iterative)

2.3 Ternary Search

Divides the array into three parts.

int ternarySearch(int arr[], int l, int r, int key) {
    while (l <= r) {
        int mid1 = l + (r - l) / 3;
        int mid2 = r - (r - l) / 3;

        if (arr[mid1] == key) return mid1;
        if (arr[mid2] == key) return mid2;

        if (key < arr[mid1])
            r = mid1 - 1;
        else if (key > arr[mid2])
            l = mid2 + 1;
        else {
            l = mid1 + 1;
            r = mid2 - 1;
        }
    }
    return -1;
}

Time Complexity: O(log₃ n)
Application: Optimization problems

3. Sorting Algorithms

3.1 Sorting Fundamentals

Sorting means arranging data in a specific order (ascending or descending).

Example:

[40, 10, 30, 20]
Sorted: [10, 20, 30, 40]

Applications:

• Databases
• Search engines
• Data analysis

3.2 Bubble Sort

Largest element bubbles to the end.

Example: [5, 3, 8, 2]

Pass 1:

[5, 3, 8, 2] → [3, 5, 8, 2] → [3, 5, 8, 2] → [3, 5, 2, 8]

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1])
                swap(arr[j], arr[j + 1]);
        }
    }
}

3.3 Selection Sort

Selects the smallest element and places it at the beginning.

Example: [5, 3, 8, 2]

Pass 1: Find 2, swap with 5 → [2, 3, 8, 5]
Pass 2: Find 3, already in place → [2, 3, 8, 5]

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int min = i;

        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[min])
                min = j;
        }

        swap(arr[i], arr[min]);
    }
}

3.4 Insertion Sort

Inserts each element into its correct position in the sorted portion.

Example: [5, 3, 8, 2]

Pass 1: [5] → insert 3 → [3, 5, 8, 2]
Pass 2: [3, 5] → insert 8 → [3, 5, 8, 2]

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;

        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }

        arr[j + 1] = key;
    }
}

3.5 Merge Sort

Divide and conquer algorithm.

Steps:

1. Divide array into halves
2. Sort each half recursively
3. Merge sorted halves

Example: [8, 3, 5, 2]

Divide: [8, 3] and [5, 2]
Sort: [3, 8] and [2, 5]
Merge: [2, 3, 5, 8]

void merge(int arr[], int l, int m, int r) {
    int n1 = m - l + 1;
    int n2 = r - m;

    int L[n1], R[n2];

    for (int i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (int j = 0; j < n2; j++)
        R[j] = arr[m + 1 + j];

    int i = 0, j = 0, k = l;

    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    while (i < n1) {
        arr[k] = L[i];
        i++; k++;
    }

    while (j < n2) {
        arr[k] = R[j];
        j++; k++;
    }
}

void mergeSort(int arr[], int l, int r) {
    if (l < r) {
        int m = (l + r) / 2;
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);
        merge(arr, l, m, r);
    }
}

3.6 Quick Sort

Choose a pivot and partition the array.

Steps:

1. Choose pivot (last element)
2. Partition: elements < pivot to left, > pivot to right
3. Recursively sort left and right

Example: [8, 3, 5, 2], pivot = 2

Partition: [3, 5, 2, 8] → pivot=5

int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = low - 1;

    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }

    swap(arr[i + 1], arr[high]);
    return i + 1;
}

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

3.7 Heap Sort

Uses heap data structure.

Steps:

1. Build max heap
2. Swap root with last element
3. Heapify reduced heap
4. Repeat

void heapify(int arr[], int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < n && arr[left] > arr[largest])
        largest = left;

    if (right < n && arr[right] > arr[largest])
        largest = right;

    if (largest != i) {
        swap(arr[i], arr[largest]);
        heapify(arr, n, largest);
    }
}

void heapSort(int arr[], int n) {
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);

    for (int i = n - 1; i > 0; i--) {
        swap(arr[0], arr[i]);
        heapify(arr, i, 0);
    }
}

3.8 Counting Sort

Works for small integer ranges.

Example: [4, 2, 2, 8, 3]

Step 1: Count frequencies
Step 2: Calculate positions
Step 3: Place elements

void countingSort(int arr[], int n) {
    int max = *max_element(arr, arr + n);
    int min = *min_element(arr, arr + n);
    int range = max - min + 1;

    vector<int> count(range);
    vector<int> output(n);

    for (int i = 0; i < n; i++)
        count[arr[i] - min]++;

    for (int i = 1; i < range; i++)
        count[i] += count[i - 1];

    for (int i = n - 1; i >= 0; i--) {
        output[count[arr[i] - min] - 1] = arr[i];
        count[arr[i] - min]--;
    }

    for (int i = 0; i < n; i++)
        arr[i] = output[i];
}

Time Complexity: O(n + k)
Space Complexity: O(k)

3.9 Radix Sort

Sorts numbers digit by digit.

Example: [170, 45, 75, 90]

Step 1: Sort by units digit
Step 2: Sort by tens digit
Step 3: Sort by hundreds digit

void countingSortByDigit(int arr[], int n, int exp) {
    vector<int> output(n);
    vector<int> count(10, 0);

    for (int i = 0; i < n; i++)
        count[(arr[i] / exp) % 10]++;

    for (int i = 1; i < 10; i++)
        count[i] += count[i - 1];

    for (int i = n - 1; i >= 0; i--) {
        output[count[(arr[i] / exp) % 10] - 1] = arr[i];
        count[(arr[i] / exp) % 10]--;
    }

    for (int i = 0; i < n; i++)
        arr[i] = output[i];
}

void radixSort(int arr[], int n) {
    int max = *max_element(arr, arr + n);

    for (int exp = 1; max / exp > 0; exp *= 10)
        countingSortByDigit(arr, n, exp);
}

Time Complexity: O(nk) where k = number of digits

3.10 Sorting Algorithm Comparison

4. Advanced Algorithm Techniques

4.1 Dynamic Programming

What Is Dynamic Programming?

Dynamic Programming is an algorithmic technique used when a problem has:

1. Overlapping Subproblems – The same subproblem appears many times
2. Optimal Substructure – The optimal solution can be constructed from optimal solutions of subproblems

Idea: Solve smaller problems, store results, reuse them – avoids recomputing the same work.

Two Approaches

1. Memoization (Top-Down DP)

• Store results in a cache (array/table)
• Compute recursively, but check cache first

2. Tabulation (Bottom-Up DP)

• Build solution iteratively
• Fill a table from smallest to largest

Example: Fibonacci

Normal Recursion:

int fib(int n) {
    if (n <= 1) return n;
    return fib(n-1) + fib(n-2);
}

Time Complexity: O(2ⁿ) – Very slow

Memoization:

int dp[100];

int fib(int n) {
    if (n <= 1) return n;
    if (dp[n] != -1) return dp[n];
    return dp[n] = fib(n-1) + fib(n-2);
}

Time Complexity: O(n)

Tabulation:

int fib(int n) {
    int dp[n+1];
    dp[0] = 0;
    dp[1] = 1;

    for (int i = 2; i <= n; i++)
        dp[i] = dp[i-1] + dp[i-2];

    return dp[n];
}

Time Complexity: O(n)

DP Dimensions

Classic DP Problems

1. Knapsack Problem

Problem: Given items with weight and value, choose items to maximize value within weight capacity.

Example:

• Weight = [2, 3, 4]
• Value = [3, 4, 5]
• Capacity = 5

DP Relation:

dp[i][w] = max value using first i items and weight w

int knapsack(int W, int wt[], int val[], int n) {
    int dp[n+1][W+1];

    for (int i = 0; i <= n; i++) {
        for (int w = 0; w <= W; w++) {
            if (i == 0 || w == 0)
                dp[i][w] = 0;
            else 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];
}

2. Coin Change

Problem: Find the number of ways to make an amount using given coins.

int coinChange(int coins[], int m, int amount) {
    int dp[amount+1];
    dp[0] = 1;

    for (int i = 0; i < m; i++) {
        for (int j = coins[i]; j <= amount; j++) {
            dp[j] += dp[j - coins[i]];
        }
    }

    return dp[amount];
}

3. Longest Increasing Subsequence (LIS)

Example: [10, 9, 2, 5, 3, 7, 101]

LIS: [2, 3, 7, 101] → Length: 4

int LIS(int arr[], int n) {
    vector<int> dp(n, 1);

    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (arr[i] > arr[j])
                dp[i] = max(dp[i], dp[j] + 1);
        }
    }

    return *max_element(dp.begin(), dp.end());
}

Time Complexity: O(n²)
Optimized (Binary Search): O(n log n)

4. Longest Common Subsequence (LCS)

Example:

• String1 = “ABCD”
• String2 = “ACBD”
• LCS = “ABD”

int LCS(string a, string b) {
    int n = a.length(), m = b.length();
    int dp[n+1][m+1];

    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            if (i == 0 || j == 0)
                dp[i][j] = 0;
            else if (a[i-1] == b[j-1])
                dp[i][j] = 1 + dp[i-1][j-1];
            else
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
        }
    }

    return dp[n][m];
}

5. Matrix Chain Multiplication

Problem: Find the optimal parenthesization to minimize multiplication cost.

int matrixChain(int p[], int n) {
    int dp[n][n];

    for (int i = 1; i < n; i++)
        dp[i][i] = 0;

    for (int len = 2; len < n; len++) {
        for (int i = 1; i < n - len + 1; i++) {
            int j = i + len - 1;
            dp[i][j] = INT_MAX;

            for (int k = i; k < j; k++) {
                int cost = dp[i][k] + dp[k+1][j] + p[i-1] * p[k] * p[j];
                dp[i][j] = min(dp[i][j], cost);
            }
        }
    }

    return dp[1][n-1];
}

4.2 Greedy Algorithms

What Is a Greedy Algorithm?

A greedy algorithm makes the best local choice at each step, hoping it leads to the global optimum.

Key Idea: Choose the optimal step now; trust it will lead to the best overall solution.

Properties for Greedy

Classic Greedy Problems

1. Activity Selection Problem

Problem: Select the maximum number of non-overlapping activities.

Example:

Start: [1, 3, 0, 5, 8]
End:   [2, 4, 6, 7, 9]

Greedy Rule: Choose activity with earliest finish time.

struct Activity { int start, end; };

void activitySelection(Activity arr[], int n) {
    sort(arr, arr+n, [](Activity a, Activity b) {
        return a.end < b.end;
    });

    int count = 1;
    int lastEnd = arr[0].end;

    for (int i = 1; i < n; i++) {
        if (arr[i].start >= lastEnd) {
            count++;
            lastEnd = arr[i].end;
        }
    }

    return count;
}

Time Complexity: O(n log n)

2. Fractional Knapsack

Unlike normal knapsack, we can take fractions of items.

Greedy Rule: Choose items by highest value/weight ratio.

struct Item { int value, weight; };

double fractionalKnapsack(Item arr[], int n, int W) {
    sort(arr, arr+n, [](Item a, Item b) {
        return (double)a.value/a.weight > (double)b.value/b.weight;
    });

    double totalValue = 0;

    for (int i = 0; i < n; i++) {
        if (arr[i].weight <= W) {
            W -= arr[i].weight;
            totalValue += arr[i].value;
        } else {
            totalValue += arr[i].value * ((double)W / arr[i].weight);
            break;
        }
    }

    return totalValue;
}

3. Huffman Coding

Used in data compression (ZIP, MP3, JPEG).

Idea: Characters with higher frequency get shorter codes.

Example Tree:

      *
     / \
   a   *
      / \
     b   c

struct Node {
    char data;
    int freq;
    Node *left, *right;
};

struct Compare {
    bool operator()(Node* a, Node* b) {
        return a->freq > b->freq;
    }
};

Node* buildHuffmanTree(char data[], int freq[], int n) {
    priority_queue<Node*, vector<Node*>, Compare> pq;

    for (int i = 0; i < n; i++)
        pq.push(new Node(data[i], freq[i]));

    while (pq.size() > 1) {
        Node* left = pq.top(); pq.pop();
        Node* right = pq.top(); pq.pop();

        Node* parent = new Node('\0', left->freq + right->freq);
        parent->left = left;
        parent->right = right;

        pq.push(parent);
    }

    return pq.top();
}

4. Dijkstra’s Algorithm (covered in Graph section)

4.3 Backtracking

What Is Backtracking?

Backtracking is a systematic way to try all possibilities and abandon invalid paths.

Idea: Choose → Explore → Undo

Used in: Combinatorial search, constraint satisfaction problems.

Classic Backtracking Problems

1. N-Queens Problem

Problem: Place N queens on an N×N chessboard so that no two queens attack each other.

Example (4×4):

Q . . .
. . Q .
. Q . .
. . . Q

bool isSafe(int board[][], int row, int col, int N) {
    // Check column
    for (int i = 0; i < row; i++)
        if (board[i][col]) return false;

    // Check upper left diagonal
    for (int i = row, j = col; i >= 0 && j >= 0; i--, j--)
        if (board[i][j]) return false;

    // Check upper right diagonal
    for (int i = row, j = col; i >= 0 && j < N; i--, j++)
        if (board[i][j]) return false;

    return true;
}

bool solveNQueens(int board[][], int row, int N) {
    if (row == N) return true;

    for (int col = 0; col < N; col++) {
        if (isSafe(board, row, col, N)) {
            board[row][col] = 1;

            if (solveNQueens(board, row + 1, N))
                return true;

            board[row][col] = 0;  // Backtrack
        }
    }

    return false;
}

2. Sudoku Solver

Problem: Fill a 9×9 Sudoku grid.

bool isValid(vector<vector<char>>& board, int row, int col, char c) {
    for (int i = 0; i < 9; i++) {
        if (board[i][col] == c) return false;
        if (board[row][i] == c) return false;
        if (board[3*(row/3) + i/3][3*(col/3) + i%3] == c) return false;
    }
    return true;
}

bool solveSudoku(vector<vector<char>>& board) {
    for (int row = 0; row < 9; row++) {
        for (int col = 0; col < 9; col++) {
            if (board[row][col] == '.') {
                for (char c = '1'; c <= '9'; c++) {
                    if (isValid(board, row, col, c)) {
                        board[row][col] = c;

                        if (solveSudoku(board))
                            return true;

                        board[row][col] = '.';  // Backtrack
                    }
                }
                return false;
            }
        }
    }
    return true;
}

3. Generate Permutations

void permutations(vector<int>& arr, int start, vector<vector<int>>& result) {
    if (start == arr.size()) {
        result.push_back(arr);
        return;
    }

    for (int i = start; i < arr.size(); i++) {
        swap(arr[start], arr[i]);
        permutations(arr, start + 1, result);
        swap(arr[start], arr[i]);  // Backtrack
    }
}

4. Generate Subsets

void subsets(vector<int>& arr, int index, vector<int>& current, vector<vector<int>>& result) {
    result.push_back(current);

    for (int i = index; i < arr.size(); i++) {
        current.push_back(arr[i]);
        subsets(arr, i + 1, current, result);
        current.pop_back();  // Backtrack
    }
}

4.4 Bitwise Algorithms

What Are Bitwise Algorithms?

Bitwise algorithms operate directly on the binary representation of numbers.

Important Operators

XOR Properties

a ^ a = 0
a ^ 0 = a
a ^ b = b ^ a  (commutative)
a ^ (b ^ c) = (a ^ b) ^ c  (associative)

Classic Bitwise Problems

1. Find the Single Number

Problem: In an array where every number appears twice except one, find the single number.

Example: [2, 3, 2, 4, 3] → Answer: 4

int singleNumber(vector<int>& nums) {
    int ans = 0;
    for (int x : nums)
        ans ^= x;
    return ans;
}

Time Complexity: O(n)

2. Count Set Bits

Problem: Count the number of 1s in binary representation.

Example: 13 = 1101 → Set bits: 3

int countBits(int n) {
    int count = 0;
    while (n) {
        count += n & 1;
        n >>= 1;
    }
    return count;
}

// Brian Kernighan's Algorithm (faster)
int countBits(int n) {
    int count = 0;
    while (n) {
        n &= (n - 1);  // Removes the rightmost set bit
        count++;
    }
    return count;
}

3. Subset Generation Using Bitmask

Example: Generate all subsets of [1, 2, 3]

void generateSubsets(vector<int>& arr) {
    int n = arr.size();

    for (int mask = 0; mask < (1 << n); mask++) {
        cout << "{ ";
        for (int i = 0; i < n; i++) {
            if (mask & (1 << i))
                cout << arr[i] << " ";
        }
        cout << "}" << endl;
    }
}

4. Check Power of Two

bool isPowerOfTwo(int n) {
    return n > 0 && (n & (n - 1)) == 0;
}

5. Bitmask DP

Used in problems where states are represented as bits.

Example: Traveling Salesman Problem

int dp[1 << n][n];

int tsp(int mask, int pos) {
    if (mask == (1 << n) - 1) return dist[pos][0];

    if (dp[mask][pos] != -1) return dp[mask][pos];

    int ans = INT_MAX;

    for (int city = 0; city < n; city++) {
        if (!(mask & (1 << city))) {
            ans = min(ans, dist[pos][city] + tsp(mask | (1 << city), city));
        }
    }

    return dp[mask][pos] = ans;
}

4.5 Mathematical & Number-Theoretic Algorithms

1. GCD (Greatest Common Divisor)

Largest number dividing two numbers.

Euclidean Algorithm:

int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

Time Complexity: O(log n)

2. LCM (Least Common Multiple)

int lcm(int a, int b) {
    return (a / gcd(a, b)) * b;
}

3. Prime Numbers

Prime numbers are divisible only by 1 and themselves.

Examples: 2, 3, 5, 7, 11, 13

Primality Test (O(√n)):

bool isPrime(int n) {
    if (n < 2) return false;
    if (n == 2) return true;

    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) return false;
    }

    return true;
}

4. Sieve of Eratosthenes

Efficient algorithm to find all primes up to N.

vector<bool> sieve(int n) {
    vector<bool> isPrime(n + 1, true);
    isPrime[0] = isPrime[1] = false;

    for (int i = 2; i * i <= n; i++) {
        if (isPrime[i]) {
            for (int j = i * i; j <= n; j += i) {
                isPrime[j] = false;
            }
        }
    }

    return isPrime;
}

Time Complexity: O(n log log n)

5. Modular Exponentiation

Compute a^b mod m efficiently.

long long modPow(long long a, long long b, long long m) {
    long long result = 1;
    a %= m;

    while (b > 0) {
        if (b & 1)  // If b is odd
            result = (result * a) % m;

        a = (a * a) % m;
        b >>= 1;
    }

    return result;
}

Time Complexity: O(log b)

6. Combinatorics

nCr = n! / (r! × (n-r)!)

long long nCr(int n, int r) {
    if (r > n - r) r = n - r;

    long long result = 1;

    for (int i = 0; i < r; i++) {
        result = result * (n - i) / (i + 1);
    }

    return result;
}

7. Advanced Mathematical Algorithms

5. Algorithm Engineering

5.1 Optimization Techniques

1. Time Optimization

2. Space Optimization

3. C++ STL Mastery