Data Structures & Algorithms — Complete BSCS-Level Guide

1. Foundations of Data Structures and Algorithms

What is a Data Structure? A way to organize and store data in memory so it can be accessed and
modified efficiently.

What is an Algorithm? A step-by-step procedure to solve a problem or perform a computation.

Why both together?

"Program = Data Structure + Algorithm" — Niklaus Wirth

Abstract Data Type (ADT):

 Defines what operations are available, not how they're implemented

 Example: Stack ADT says "push, pop, peek" — you decide if it's array-based or linked-list-
based

Asymptotic Analysis — Big O Notation:

The most critical concept for any DS&A exam.

Notation Name Example

O(1) Constant Array index access
O(log n) Logarithmic Binary search
O(n) Linear Linear scan
O(n log n) Linearithmic Merge sort
O(n²) Quadratic Bubble sort, nested loops
O(2ⁿ) Exponential Naive recursive fibonacci
O(n!) Factorial Brute-force permutations

Growth order (slowest to fastest):

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

Three cases:

 Best case (Ω) – minimum operations (e.g., element found at index 0)

 Average case (Θ) – expected operations
 Worst case (O) – maximum operations (what we usually care about)

Space Complexity = extra memory used by algorithm

 In-place algorithm: O(1) extra space (bubble sort)

 Merge sort: O(n) extra space
How to calculate Big O:

# Rule 1: Drop constants

O(2n) → O(n)

# Rule 2: Drop lower-order terms

O(n² + n) → O(n²)

# Rule 3: Sequential blocks add

for i in range(n): # O(n)
pass
for j in range(n): # O(n)
pass
# Total: O(n) + O(n) = O(2n) → O(n)

# Rule 4: Nested loops multiply

for i in range(n): # O(n)
for j in range(n): # O(n)
pass
# Total: O(n × n) = O(n²)

# Rule 5: Halving = log n

while n > 1:
n = n // 2
# O(log n)

Recursion & Recurrence Relations:

T(n) = T(n-1) + O(1) → O(n) [linear recursion]

T(n) = T(n/2) + O(1) → O(log n) [binary search]
T(n) = 2T(n/2) + O(n) → O(n log n) [merge sort]
T(n) = T(n-1) + O(n) → O(n²) [insertion sort]

2. Linear Data Structures

Data arranged sequentially, each element connected to the previous and next.

Array

Fixed-size, contiguous memory block.

Index: [0] [1] [2] [3] [4]

Value: [10] [20] [30] [40] [50]
Address: 100 104 108 112 116 (each int = 4 bytes)
Operation Complexity Why
Access arr[i] O(1) Direct address calculation
Search (unsorted) O(n) Must scan all
Search (sorted) O(log n) Binary search possible
Insert at end O(1) Just place it
Insert at middle O(n) Must shift elements
Delete at middle O(n) Must shift elements
2D Array (Matrix):

int matrix[3][4];
// Element at row i, col j:
// Address = base + (i * cols + j) * elementSize
// Row-major order (C/C++/Java) — rows stored contiguously
// Col-major order (Fortran/MATLAB)

Linked List

Dynamic size, nodes connected via pointers. NOT contiguous in memory.

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

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

class LinkedList {
Node* head;
public:
void insertFront(int val) {
Node* newNode = new Node{val, head};
head = newNode;
}
void insertEnd(int val) {
Node* newNode = new Node{val, nullptr};
if (!head) { head = newNode; return; }
Node* temp = head;
while (temp->next) temp = temp->next;
temp->next = newNode;
}
void deleteNode(int val) {
if (!head) return;
if (head->data == val) { head = head->next; return; }
Node* temp = head;
while (temp->next && temp->next->data != val)
temp = temp->next;
if (temp->next) temp->next = temp->next->next;
}
};

Types:

Type Structure Extra pointer

Singly Linked A→B→C→NULL None
Doubly Linked NULL←A⇄ B⇄ C→NULL prev pointer
Circular Linked A→B→C→A Last points to head
Circular Doubly Full bidirectional circle Both directions
Operation Singly LL Array
Access by index O(n) ❌ O(1) ✅
Insert at front O(1) ✅ O(n) ❌
 Operation Singly LL Array
Insert at end O(n) / O(1) with tail O(1) amortized
Delete O(n) to find, O(1) to remove O(n) to shift
Memory Extra pointer overhead Compact

Classic LL problems to know:

 Detect cycle: Floyd's algorithm (slow/fast pointers)

 Reverse a linked list
 Find middle node (slow/fast pointers)
 Merge two sorted lists

// Reverse linked list

Node* reverse(Node* head) {
Node *prev = nullptr, *curr = head, *next = nullptr;
while (curr) {
next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
return prev;
}

Stack

LIFO — Last In, First Out.

TOP
| 30 | ← push/pop here
| 20 |
| 10 |
|_______|

Operations: all O(1)

 push(x) – add to top

 pop() – remove from top
 peek()/top() – see top without removing
 isEmpty() – check if empty

// Array-based stack
class Stack {
int arr[100], top = -1;
public:
void push(int x) { arr[++top] = x; }
int pop() { return arr[top--]; }
int peek() { return arr[top]; }
bool isEmpty() { return top == -1; }
};
Real-world uses:

 Function call stack (how recursion works internally)

 Undo/redo in editors
 Browser back button
 Expression evaluation (infix → postfix)
 Balanced parentheses checking

Balanced parentheses check:

def is_balanced(s):
stack = []
pairs = {')':'(', ']':'[', '}':'{'}
for ch in s:
if ch in '([{':
[Link](ch)
elif ch in ')]}':
if not stack or stack[-1] != pairs[ch]:
return False
[Link]()
return len(stack) == 0

Queue

FIFO — First In, First Out.

REAR → [40][30][20][10] → FRONT

enqueue dequeue

Operations: all O(1)

 enqueue(x) – add to rear

 dequeue() – remove from front
 front() – see front element
 isEmpty()

Types:

Type Description
Simple Queue Basic FIFO
Circular Queue Rear wraps around to reuse space
Priority Queue Highest priority dequeued first
Deque (Double-ended) Insert/delete from both ends

Circular Queue (fixes wasted space in simple queue):

class CircularQueue {
int arr[5], front = -1, rear = -1, size = 5;
public:
void enqueue(int x) {
rear = (rear + 1) % size;
arr[rear] = x;
if (front == -1) front = 0;
}
int dequeue() {
 int val = arr[front];
if (front == rear) front = rear = -1;
else front = (front + 1) % size;
return val;
}
};

Real-world uses:

 CPU scheduling
 Print queue
 BFS traversal
 Buffer in streaming

3. Non-Linear Data Structures

Elements are not arranged sequentially — they have hierarchical or network relationships.

Trees

Tree = hierarchical structure with a root node, branches, and leaves.

Terminology:

A ← Root
/\
B C ← Internal nodes
/\ \
D E F ← Leaves

- Height of tree = 3 (longest path from root to leaf)

- Depth of node B = 1
- Degree of A = 2 (number of children)

Binary Tree

Each node has at most 2 children (left and right).

struct TreeNode {
int data;
TreeNode *left, *right;
TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};

Types of Binary Trees:

Type Property
Full Every node has 0 or 2 children
Complete All levels filled except last, last filled left to right
Perfect All internal nodes have 2 children, all leaves at same level
 Type Property
Balanced Height difference between subtrees ≤ 1
Degenerate/Skewed Every node has only one child (like a linked list)

Tree Traversals (CRITICAL — memorize all):

1
/\
2 3
/\
4 5
# Inorder: Left → Root → Right → result: 4 2 5 1 3
def inorder(node):
if node:
inorder([Link])
print([Link])
inorder([Link])

# Preorder: Root → Left → Right → result: 1 2 4 5 3

def preorder(node):
if node:
print([Link])
preorder([Link])
preorder([Link])

# Postorder: Left → Right → Root → result: 4 5 2 3 1

def postorder(node):
if node:
postorder([Link])
postorder([Link])
print([Link])

# Level Order (BFS): 1 2 3 4 5

from collections import deque
def levelorder(root):
q = deque([root])
while q:
node = [Link]()
print([Link])
if [Link]: [Link]([Link])
if [Link]: [Link]([Link])

Memory trick: In-order gives sorted output for BST. Pre-order reconstructs tree. Post-order deletes
tree.

4. Searching Algorithms

Linear Search

def linear_search(arr, target):

for i in range(len(arr)):
if arr[i] == target:
return i
return -1
  Works on: Any array (sorted or not)
 Time: O(n) worst, O(1) best
 Space: O(1)

Binary Search

Requires sorted array. Divide and conquer — eliminate half the search space each step.

def binary_search(arr, target):

left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1 # go right
else:
right = mid - 1 # go left
return -1
Array: [2, 5, 8, 12, 16, 23, 38, 50]
Find 23:
Step 1: mid = index 3 (12) → 23 > 12 → search right half
Step 2: mid = index 5 (23) → Found!

 Time: O(log n) — 1 billion elements needs only 30 comparisons!

 Space: O(1) iterative, O(log n) recursive

Recursive Binary Search:

def binary_search_rec(arr, target, left, right):

if left > right: return -1
mid = (left + right) // 2
if arr[mid] == target: return mid
elif arr[mid] < target:
return binary_search_rec(arr, target, mid+1, right)
else:
return binary_search_rec(arr, target, left, mid-1)

Variants:

 Find first occurrence (leftmost)

 Find last occurrence (rightmost)
 Find insert position
 Search in rotated sorted array

5. Sorting Algorithms

Comparison-based sorting lower bound: O(n log n) — proven mathematically.

Bubble Sort

Compare adjacent, swap if out of order. Bubbles largest to end each pass.

def bubble_sort(arr):
n = len(arr)
for i in range(n):
swapped = False
for j in range(n - i - 1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
swapped = True
if not swapped: break # optimization: already sorted

 Time: O(n²) worst/avg, O(n) best (with optimization)

 Space: O(1) in-place
 Stable: ✅ Yes

Selection Sort

Find minimum, place at start. Repeat.

def selection_sort(arr):
for i in range(len(arr)):
min_idx = i
for j in range(i+1, len(arr)):
if arr[j] < arr[min_idx]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]

 Time: O(n²) always (doesn't benefit from sorted data)

 Space: O(1)
 Stable: ❌ No

Insertion Sort

Build sorted portion one element at a time — like sorting playing cards.

def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j=i-1
while j >= 0 and arr[j] > key:
arr[j+1] = arr[j]
j -= 1
arr[j+1] = key

 Time: O(n²) worst, O(n) best (nearly sorted data)

 Space: O(1)
 Stable: ✅ Yes
 Best for: Small arrays, nearly sorted data
Merge Sort

Divide array in half, sort each half, merge them. Classic divide & conquer.

def merge_sort(arr):
if len(arr) <= 1: return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)

def merge(left, right):

result = []
i=j=0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
[Link](left[i]); i += 1
else:
[Link](right[j]); j += 1
[Link](left[i:])
[Link](right[j:])
return result
[38, 27, 43, 3]
→ [38,27] [43,3]
→ [38][27] [43][3]
→ [27,38] [3,43]
→ [3, 27, 38, 43]

 Time: O(n log n) always

 Space: O(n) ← needs extra array
 Stable: ✅ Yes
 Best for: Linked lists, guaranteed O(n log n)

Quick Sort

Pick a pivot, partition array so all smaller values are left, larger are right. Recurse.

def quick_sort(arr, low, high):

if low < high:
pi = partition(arr, low, high)
quick_sort(arr, low, pi - 1)
quick_sort(arr, pi + 1, high)

def partition(arr, low, high):

pivot = arr[high] # last element as pivot
i = low - 1
for j in range(low, high):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i+1], arr[high] = arr[high], arr[i+1]
return i + 1

 Time: O(n log n) avg, O(n²) worst (sorted array with bad pivot)
 Space: O(log n) stack
 Stable: ❌ No
  Best for: In-practice fastest for random data, cache-friendly

Pivot strategies: Last element, First element, Random, Median-of-three (best)

Heap Sort

Build a max-heap, repeatedly extract max to end.

 Time: O(n log n) always

 Space: O(1) in-place
 Stable: ❌ No

Counting Sort / Radix Sort (Non-comparison)

# Counting sort — for small integer ranges

def counting_sort(arr, max_val):
count = [0] * (max_val + 1)
for x in arr: count[x] += 1
result = []
for i, c in enumerate(count):
[Link]([i] * c)
return result

 Time: O(n + k) where k = range of values

 Works only on integers/characters
 Radix Sort uses counting sort digit by digit → O(d × (n+k))

Sorting Comparison Table

Algorithm Best Average Worst Space Stable

Bubble O(n) O(n²) O(n²) O(1) ✅
Selection O(n²) O(n²) O(n²) O(1) ❌
Insertion O(n) O(n²) O(n²) O(1) ✅
Merge O(n log n) O(n log n) O(n log n) O(n) ✅
Quick O(n log n) O(n log n) O(n²) O(log n) ❌
Heap O(n log n) O(n log n) O(n log n) O(1) ❌
Counting O(n+k) O(n+k) O(n+k) O(k) ✅

6. Hashing

Hash Table = data structure that maps keys to values using a hash function for O(1) average lookup.

Key "Ali" → hash("Ali") % 10 = 3 → stored at index 3

Key "Sara" → hash("Sara") % 10 = 7 → stored at index 7
Hash Function properties:

 Deterministic (same key → same hash always)

 Fast to compute
 Distribute keys uniformly
 Minimize collisions

Common hash functions:

# Division method
h(k) = k % m # m should be prime

# Multiplication method
h(k) = floor(m * (k * A mod 1)) # A ≈ 0.618...

# Python's built-in
hash("hello") # uses SipHash

Collision = two different keys produce the same hash index.

Collision Resolution:

① Chaining (Separate Chaining): Each slot holds a linked list of all colliding keys.

Index 3: → ["Ali", 25] → ["Bob", 30] → NULL

 Load factor α = n/m (n=keys, m=slots)

 Average search: O(1 + α)
 Works well when α ≤ 0.7

② Open Addressing: Find another open slot in the same table.

# Linear Probing: try next slot

h(k, i) = (h(k) + i) % m

# Quadratic Probing: try i² steps away

h(k, i) = (h(k) + i²) % m

# Double Hashing: use second hash function

h(k, i) = (h1(k) + i * h2(k)) % m

Problem with Linear Probing: Clustering — long runs form, degrading performance.

Operations & Complexity:

Operation Average Worst

Search O(1) O(n)
Insert O(1) O(n)
Delete O(1) O(n)

Dynamic Resizing: When load factor exceeds threshold (e.g., 0.75), resize table (double) and rehash
all keys.

Python dict / Java HashMap are hash table implementations.

7. Tree Algorithms

Binary Search Tree (BST)

Property: For every node, all left descendants < node < all right descendants.

8
/\
3 10
/\ \
1 6 14
/\ /
4 7 13
class BST:
def insert(self, root, val):
if not root: return TreeNode(val)
if val < [Link]:
[Link] = [Link]([Link], val)
else:
[Link] = [Link]([Link], val)
return root

def search(self, root, val):

if not root or [Link] == val: return root
if val < [Link]: return [Link]([Link], val)
return [Link]([Link], val)

def delete(self, root, val):

if not root: return root
if val < [Link]:
[Link] = [Link]([Link], val)
elif val > [Link]:
[Link] = [Link]([Link], val)
else:
# Case 1: No children
if not [Link] and not [Link]: return None
# Case 2: One child
if not [Link]: return [Link]
if not [Link]: return [Link]
# Case 3: Two children — replace with inorder successor
successor = self.find_min([Link])
[Link] = [Link]
[Link] = [Link]([Link], [Link])
return root
Operation Balanced BST Worst (Skewed)
Search O(log n) O(n)
Insert O(log n) O(n)
Delete O(log n) O(n)

Inorder traversal of BST gives sorted output!

AVL Tree (Self-Balancing BST)

Keeps height balanced so operations stay O(log n).

Balance Factor = height(left subtree) - height(right subtree)

 Must be -1, 0, or +1 for every node

 If |BF| > 1 → rotation needed

4 Rotations:

LL Rotation (right rotate): RR Rotation (left rotate):

z y z y
/ → /\ \ → /\
y x z y z x
/ \
x x

LR Rotation: Left rotate on y, then right rotate on z

RL Rotation: Right rotate on y, then left rotate on z

Red-Black Tree

Self-balancing BST with color properties. Used in Java TreeMap, C++ std::map.

Properties:

1. Every node is Red or Black

2. Root is Black
3. No two consecutive Red nodes
4. Every path from node to NULL has same number of Black nodes

 Operations: O(log n) guaranteed

 Less strictly balanced than AVL → faster inserts/deletes

Heap (Binary Heap)

Complete binary tree with heap property.

Max-Heap: Parent ≥ children (root = maximum) Min-Heap: Parent ≤ children (root = minimum)

Max-Heap:
90
/ \
70 80
/\ /\
50 60 10 30

Stored as array: [90, 70, 80, 50, 60, 10, 30]

Parent of i: (i-1)//2
Left child: 2i+1
Right child: 2i+2
import heapq # Python's min-heap
h = []
[Link](h, 5)
[Link](h, 1)
[Link](h, 3)
[Link](h) # returns 1 (minimum)

# Max-heap trick: negate values

[Link](h, -5) # store as -5
-[Link](h) # negate back

Heapify = build heap from array in O(n) (not O(n log n)!)

Operation Complexity
Insert O(log n)
Delete max/min O(log n)
Peek max/min O(1)
Build heap O(n)

Use cases: Priority queues, heap sort, Dijkstra's algorithm, task scheduling.

8. Graph Algorithms

Graph = set of Vertices (nodes) connected by Edges.

G = (V, E)

Types:

Type Description
Directed (Digraph) Edges have direction (A→B ≠ B→A)
Undirected Edges are bidirectional
Weighted Edges have weights/costs
Unweighted All edges equal
Cyclic Contains cycles
Acyclic No cycles (DAG = Directed Acyclic Graph)
Connected Path exists between all pairs

Representations:

Adjacency Matrix:

A B C D
A [0 1 1 0]
B [1 0 1 0]
C [1 1 0 1]
D [0 0 1 0]

Space: O(V²) — good for dense graphs

Edge check: O(1)
Find neighbors: O(V)
Adjacency List:

graph = {
'A': ['B', 'C'],
'B': ['A', 'C'],
'C': ['A', 'B', 'D'],
'D': ['C']
}
# Space: O(V + E) — good for sparse graphs
# Edge check: O(degree)
# Find neighbors: O(degree)

BFS (Breadth-First Search)

Explore level by level. Uses queue.

from collections import deque

def bfs(graph, start):

visited = set()
queue = deque([start])
[Link](start)
order = []

while queue:
node = [Link]()
[Link](node)
for neighbor in graph[node]:
if neighbor not in visited:
[Link](neighbor)
[Link](neighbor)
return order

 Time: O(V + E)
 Space: O(V)
 Finds: Shortest path in unweighted graphs, connected components, level traversal

DFS (Depth-First Search)

Go as deep as possible, then backtrack. Uses stack (or recursion).

def dfs(graph, start, visited=None):

if visited is None: visited = set()
[Link](start)
print(start)
for neighbor in graph[start]:
if neighbor not in visited:
dfs(graph, neighbor, visited)
return visited

 Time: O(V + E)
 Space: O(V)
 Finds: Cycle detection, topological sort, connected components, maze solving
Dijkstra's Algorithm (Shortest Path — weighted, no negative edges)

import heapq

def dijkstra(graph, start):

dist = {node: float('inf') for node in graph}
dist[start] = 0
pq = [(0, start)] # (distance, node)

while pq:
d, u = [Link](pq)
if d > dist[u]: continue
for v, weight in graph[u]:
if dist[u] + weight < dist[v]:
dist[v] = dist[u] + weight
[Link](pq, (dist[v], v))
return dist

 Time: O((V + E) log V) with priority queue

 Fails with negative edges — use Bellman-Ford instead

Bellman-Ford (Shortest Path — handles negative edges)

def bellman_ford(vertices, edges, start):

dist = {v: float('inf') for v in vertices}
dist[start] = 0
for _ in range(len(vertices) - 1):
for u, v, w in edges:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
# Check for negative cycles
for u, v, w in edges:
if dist[u] + w < dist[v]:
return None # negative cycle detected
return dist

 Time: O(V × E)

Topological Sort (for DAGs)

Order vertices so that for every edge u→v, u comes before v. Used in task scheduling, build systems.

def topological_sort(graph):
visited = set()
stack = []

def dfs(node):
[Link](node)
for neighbor in [Link](node, []):
if neighbor not in visited:
dfs(neighbor)
[Link](node)
 for node in graph:
if node not in visited:
dfs(node)
return stack[::-1]

Minimum Spanning Tree (MST)

Connect all vertices with minimum total edge weight, no cycles.

Kruskal's Algorithm:

1. Sort all edges by weight

2. Add edge if it doesn't create a cycle (use Union-Find)
3. Stop when n-1 edges added
Time: O(E log E)

Prim's Algorithm:

1. Start from any vertex

2. Always add the cheapest edge connecting to an unvisited vertex
3. Use priority queue
Time: O(E log V) with priority queue

9. Algorithm Design Techniques

The big 5 paradigms:

① Brute Force

Try every possible solution. Simple but slow.

 Example: Check all pairs for closest pair → O(n²)

② Divide and Conquer

Split problem → solve subproblems → combine results.

Problem
├── Subproblem 1
├── Subproblem 2
└── Combine results

Examples: Merge Sort, Quick Sort, Binary Search

Key idea: Subproblems are independent (don't share state).

③ Dynamic Programming (DP)

Solve overlapping subproblems once, store results (memoization).

Two conditions for DP:

1. Optimal substructure – optimal solution built from optimal sub-solutions

2. Overlapping subproblems – same subproblem solved multiple times

Two approaches:

# Top-Down (Memoization) — recursive + cache

memo = {}
def fib(n):
if n <= 1: return n
if n in memo: return memo[n]
memo[n] = fib(n-1) + fib(n-2)
return memo[n]

# Bottom-Up (Tabulation) — iterative, fill table from base

def fib(n):
dp = [0] * (n+1)
dp[1] = 1
for i in range(2, n+1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]

Classic DP problems:

Knapsack: dp[i][w] = max value with i items and capacity w

Longest Common Subsequence: dp[i][j] = LCS of s1[0:i] and s2[0:j]
Coin Change: dp[amount] = min coins to make amount
Matrix Chain: minimize multiplication cost
Edit Distance: min ops to convert string to another

Knapsack (0/1):

def knapsack(weights, values, capacity):

n = len(weights)
dp = [[0]*(capacity+1) for _ in range(n+1)]
for i in range(1, n+1):
for w in range(capacity+1):
dp[i][w] = dp[i-1][w]
if weights[i-1] <= w:
dp[i][w] = max(dp[i][w],
dp[i-1][w-weights[i-1]] + values[i-1])
return dp[n][capacity]

④ Greedy Algorithms

Make the locally optimal choice at each step, hoping it leads to global optimum.

Rules:
1. Make a choice that looks best right now
2. Never reconsider past choices
3. Prove it works (greedy choice property + optimal substructure)

Classic Greedy problems:

  Activity Selection – pick max non-overlapping activities (sort by end time)
 Huffman Coding – optimal prefix-free encoding
 Dijkstra's – greedy shortest path
 Prim's/Kruskal's – greedy MST
 Fractional Knapsack – take fraction of items (NOT 0/1 knapsack)

Greedy vs DP:

 Greedy: makes irrevocable choices → faster but doesn't always work

 DP: considers all possibilities → always correct but slower

⑤ Backtracking

Explore all possibilities, abandon (backtrack) paths that fail constraints.

# N-Queens: place N queens so none attack each other

def solve_n_queens(n):
solutions = []
board = [-1] * n # board[i] = column of queen in row i

def is_safe(row, col):

for r in range(row):
if board[r] == col: return False # same column
if abs(board[r] - col) == abs(r - row): return False # diagonal
return True

def backtrack(row):
if row == n:
[Link](board[:])
return
for col in range(n):
if is_safe(row, col):
board[row] = col
backtrack(row + 1)
board[row] = -1 # undo choice (backtrack)

backtrack(0)
return solutions

Other backtracking problems: Sudoku solver, subset sum, maze solving, permutations.

10. Advanced Data Structures

Trie (Prefix Tree)

Tree for storing strings where each node represents a character. All children of a node share a common
prefix.

Words: ["cat", "car", "card", "care", "careful"]

root
 |
c
|
a
/\
t r
|
d e
|
f
|
u
|
l
class TrieNode:
def __init__(self):
[Link] = {}
self.is_end = False

class Trie:
def __init__(self):
[Link] = TrieNode()

def insert(self, word):

node = [Link]
for ch in word:
if ch not in [Link]:
[Link][ch] = TrieNode()
node = [Link][ch]
node.is_end = True

def search(self, word):

node = [Link]
for ch in word:
if ch not in [Link]: return False
node = [Link][ch]
return node.is_end

def starts_with(self, prefix):

node = [Link]
for ch in prefix:
if ch not in [Link]: return False
node = [Link][ch]
return True

 Time: O(L) for all operations (L = length of word)

 Space: O(ALPHABET_SIZE × L × N)
 Use cases: Autocomplete, spell checker, IP routing, word games

Segment Tree

Tree for range queries and updates on arrays.

Array: [1, 3, 5, 7, 9, 11]

Query: sum of index 1 to 4 → answer: 24

Segment Tree stores sum/min/max for each range:

[36] ← sum of all
[9] [27] ← left half, right half
[4][5] [16][11] ← quarters
[1][3][5][7][9][11] ← leaves

 Build: O(n)
 Query: O(log n)
 Update: O(log n)
 Use cases: Range sum, range min/max, interval problems

Fenwick Tree / Binary Indexed Tree (BIT)

More compact than segment tree for prefix sum queries.

 Update: O(log n)
 Prefix sum query: O(log n)
 Space: O(n)

Disjoint Set Union (DSU / Union-Find)

Track which elements belong to the same group/component.

class DSU:
def __init__(self, n):
[Link] = list(range(n))
[Link] = [0] * n

def find(self, x):

if [Link][x] != x:
[Link][x] = [Link]([Link][x]) # path compression
return [Link][x]

def union(self, x, y):

px, py = [Link](x), [Link](y)
if px == py: return False # already same component
if [Link][px] < [Link][py]: px, py = py, px
[Link][py] = px # union by rank
if [Link][px] == [Link][py]: [Link][px] += 1
return True

 Find/Union: O(α(n)) ≈ O(1) amortized (α = inverse Ackermann)

 Use cases: Kruskal's MST, cycle detection, network connectivity

Skip List

Probabilistic data structure — multiple layers of linked lists for fast search.

 Search/Insert/Delete: O(log n) expected

 Alternative to balanced BSTs — simpler to implement
 Used in Redis sorted sets
11. String Algorithms

Naive Pattern Matching

def naive_search(text, pattern):

n, m = len(text), len(pattern)
for i in range(n - m + 1):
if text[i:i+m] == pattern:
print(f"Found at index {i}")

 Time: O(n × m)

KMP (Knuth-Morris-Pratt)

Uses a failure function (LPS array) to skip redundant comparisons.

def compute_lps(pattern):
m = len(pattern)
lps = [0] * m
length = 0
i=1
while i < m:
if pattern[i] == pattern[length]:
length += 1
lps[i] = length
i += 1
elif length != 0:
length = lps[length - 1]
else:
lps[i] = 0
i += 1
return lps

def kmp_search(text, pattern):

n, m = len(text), len(pattern)
lps = compute_lps(pattern)
i=j=0
while i < n:
if text[i] == pattern[j]:
i += 1; j += 1
if j == m:
print(f"Found at {i-j}")
j = lps[j-1]
elif i < n and text[i] != pattern[j]:
if j != 0: j = lps[j-1]
else: i += 1

 Time: O(n + m) — huge improvement over naive

 Preprocessing: O(m) to build LPS
LPS (Longest Proper Prefix which is also Suffix):

Pattern: "AABAAB"
LPS: [0,1,0,1,2,3]

Rabin-Karp (Rolling Hash)

Use hashing to find pattern matches quickly.

def rabin_karp(text, pattern, q=101):

n, m = len(text), len(pattern)
d = 256 # character set size
h = pow(d, m-1, q)
p_hash = t_hash = 0

for i in range(m):
p_hash = (d * p_hash + ord(pattern[i])) % q
t_hash = (d * t_hash + ord(text[i])) % q

for i in range(n - m + 1):

if p_hash == t_hash:
if text[i:i+m] == pattern: # verify (avoid false positives)
print(f"Found at {i}")
if i < n - m:
t_hash = (d*(t_hash - ord(text[i])*h) + ord(text[i+m])) % q
if t_hash < 0: t_hash += q

 Time: O(n + m) average, O(nm) worst (many hash collisions)

 Advantage: Finds multiple patterns simultaneously

String Hashing & Other Algorithms

Z-Algorithm: Builds Z-array where Z[i] = length of longest substring starting from i that is also a
prefix.

 Time: O(n)

Suffix Array: Sorted array of all suffixes. Used in bioinformatics, string matching.

Longest Common Subsequence (LCS):

def lcs(s1, s2):

m, n = len(s1), len(s2)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
if s1[i-1] == s2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return dp[m][n]
Edit Distance (Levenshtein):

def edit_distance(s1, s2):

m, n = len(s1), len(s2)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(m+1): dp[i][0] = i
for j in range(n+1): dp[0][j] = j
for i in range(1, m+1):
for j in range(1, n+1):
if s1[i-1] == s2[j-1]:
dp[i][j] = dp[i-1][j-1]
else:
dp[i][j] = 1 + min(dp[i-1][j], # delete
dp[i][j-1], # insert
dp[i-1][j-1]) # replace
return dp[m][n]

12. Complexity & Optimization

P vs NP (Conceptual)

Class Description Example

P Solvable in polynomial time Sorting, shortest path
NP Verifiable in polynomial time Sudoku, traveling salesman
NP-Complete Hardest problems in NP SAT, Knapsack (0/1)
NP-Hard At least as hard as NP-Complete Halting problem

P = NP? — The biggest unsolved problem in computer science. If true, everything verifiable quickly is
also solvable quickly.

Amortized Analysis

Average cost per operation over a sequence of operations, even if some individual operations are
expensive.

Example: Dynamic Array (vector)

 Most pushes: O(1)

 Occasional resize (double size): O(n)
 Amortized cost: O(1) per push

Accounting method: "Save credit" during cheap operations to "pay" for expensive ones.

Space-Time Tradeoff

Use more memory to gain speed, or vice versa.

# Without memoization: O(2ⁿ) time, O(n) space

def fib(n):
if n <= 1: return n
return fib(n-1) + fib(n-2)

# With memoization: O(n) time, O(n) space (tradeoff!)

@lru_cache
def fib(n):
if n <= 1: return n
return fib(n-1) + fib(n-2)

Cache Efficiency (Locality of Reference)

Spatial locality: Access nearby memory locations (arrays are cache-friendly, linked lists are not)

Temporal locality: Reuse recently accessed data (caching, memoization)

// Cache-friendly (row-major access)

for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
sum += matrix[i][j]; // ✅ sequential memory

// Cache-unfriendly (column-major access)

for (j = 0; j < n; j++)
for (i = 0; i < n; i++)
sum += matrix[i][j]; // ❌ jumping in memory

Optimization Strategies Summary

Technique What it does

Memoization Cache repeated subproblem results
Lazy evaluation Compute only when needed
Early termination Stop as soon as answer found
Pruning Skip branches that can't lead to better solution
Two pointers O(n) instead of O(n²) for sorted array problems
Sliding window O(n) for subarray/substring problems
Bit manipulation O(1) operations on sets of flags

Two Pointer technique:

# Find pair summing to target in sorted array

def two_sum(arr, target):
left, right = 0, len(arr) - 1
while left < right:
s = arr[left] + arr[right]
if s == target: return (left, right)
elif s < target: left += 1
else: right -= 1
return None

Sliding Window:

# Maximum sum subarray of size k

def max_sum_subarray(arr, k):
window_sum = sum(arr[:k])
max_sum = window_sum
for i in range(k, len(arr)):
window_sum += arr[i] - arr[i-k]
max_sum = max(max_sum, window_sum)
return max_sum

Master Quick-Reference Table

# Topic Must-Know
1 Foundations Big O rules, recurrences, ADT, best/avg/worst
2 Linear DS Array O(1) access, LL O(1) insert, Stack LIFO, Queue FIFO
3 Non-Linear DS Tree traversals (in/pre/post/level), BST property
4 Searching Linear O(n), Binary O(log n), requires sorted array
5 Sorting Merge O(n log n) stable, Quick O(n log n) avg, all comparisons
6 Hashing Hash function, chaining vs open addressing, load factor
7 Tree Algorithms BST ops, AVL rotations, Heap operations, heapify O(n)
8 Graph Algorithms BFS (queue, shortest path), DFS (stack, cycle), Dijkstra, MST
9 Design Techniques Brute Force, D&C, DP (memo+tabulation), Greedy, Backtracking
10 Advanced DS Trie O(L), Segment Tree O(log n), DSU O(α), Skip List
11 String Algorithms KMP O(n+m), Rabin-Karp, LCS, Edit Distance
12 Complexity P vs NP, amortized analysis, space-time tradeoff, two pointers

Focus hardest on topics 5 (sorting), 8 (graphs), 9 (DP especially), and 12 (complexity) — these are
the highest-frequency topics in any BSCS-level competitive assessment. Best of luck Eiman!