Data Structures and Algorithms Handbook

for Competitive Programming

A Complete Guide Using C Language
Author: Competitive Programming Reference Guide
Date: November 2025
Purpose: Contest-focused comprehensive handbook for coding competitions (ICPC, IOI,
Codeforces, CodeChef, AtCoder)

Table of Contents
1. Introduction to Competitive Programming
2. Time and Space Complexity Analysis
3. Arrays and Strings
4. Searching Algorithms
5. Sorting Algorithms
6. Recursion and Backtracking
7. Stacks and Queues
8. Linked Lists
9. Hashing
10. Trees
11. Binary Search Trees
12. Heaps and Priority Queues
13. Graphs
14. Dynamic Programming
15. Greedy Algorithms
16. Advanced Data Structures
17. Mathematical Algorithms
18. String Algorithms
19. Bit Manipulation
20. Contest Strategies and Tips

Chapter 1: Introduction to Competitive Programming

What is Competitive Programming?
Competitive Programming is a mind sport where participants solve well-defined
algorithmic and mathematical problems under time constraints. Solutions are
automatically judged by testing against multiple test cases[1].
Key characteristics:
• Time-limited problem solving (typically 2-5 hours)
• Automated evaluation with hidden test cases
• Focus on correctness, efficiency, and implementation speed
 • Requires strong algorithmic knowledge and coding skills

Why C for Competitive Programming?

C is highly suitable for competitive programming due to:
• Fast execution speed (crucial for time-limited problems)
• Low-level control over memory and operations
• Available in virtually all contest platforms
• Minimal overhead compared to higher-level languages
• Direct implementation of algorithms without abstraction layers

Contest Platforms
Major competitive programming platforms include:

Platform Description
Codeforces Russian platform with Div 1/2/3 contests
CodeChef Indian platform with Long/Cook-Off challenges
AtCoder Japanese platform known for clean problems
LeetCode Interview-focused with weekly contests
HackerRank Mixed competitive and skill assessment
CSES Problem set by Antti Laaksonen

Table 1: Major competitive programming platforms

Template Setup for C

Fast I/O Template:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <limits.h>
#include <stdbool.h>

#define ll long long

#define ull unsigned long long
#define MOD 1000000007
#define INF 1e9
#define MAX 200005
// Fast input for integers
inline void fastscan(int *number) {
int c;
*number = 0;
int sign = 1;
c = getchar();
if (c == '-') { sign = -1; c = getchar(); }
while (c >= '0' && c <= '9') {
*number = (*number << 1) + (*number << 3) + c - '0';
c = getchar();
}
*number *= sign;
}
int main() {
// Your code here
return 0;
}

Common Macros:
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
#define swap(a,b) {int temp=a; a=b; b=temp;}
#define FOR(i,a,b) for(int i=(a); i<(b); i++)
#define REP(i,n) FOR(i,0,n)

Chapter 2: Time and Space Complexity Analysis

Big-O Notation
Definition: Big-O notation describes the upper bound of time or space required by an
algorithm as input size grows toward infinity[2].
Common Time Complexities (from fastest to slowest):

Notation Name Example

O(1) Constant Array access
O(log n) Logarithmic Binary search
O(n) Linear Linear search
O(n log n) Linearithmic Merge sort
O(n²) Quadratic Bubble sort
O(n³) Cubic Matrix multiplication
O(2ⁿ) Exponential Subset generation
O(n!) Factorial Permutation generation

Table 2: Common time complexity classes

Complexity Analysis Rules

Rule 1: Drop Constants
O(3n) → O(n)
O(n/2) → O(n)
Rule 2: Drop Non-Dominant Terms
O(n² + n) → O(n²)
O(n log n + n) → O(n log n)

Rule 3: Different Input Variables

Two nested loops with different ranges: O(m × n)
Rule 4: Amortized Analysis

Dynamic array resize: O(1) amortized per insertion

Time Limits and Constraints

General guideline for 1 second time limit:
• n ≤ 10: O(n!) or O(2ⁿ)
• n ≤ 20: O(2ⁿ)
• n ≤ 100: O(n⁴)
• n ≤ 500: O(n³)
• n ≤ 5000: O(n²)
• n ≤ 10⁶: O(n log n)
• n ≤ 10⁸: O(n)
• n > 10⁸: O(log n) or O(1)
Example Analysis:

// O(n²) - Nested loops

for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
// O(1) operation
}
}
// O(n log n) - Outer linear, inner logarithmic
for(int i = 0; i < n; i++) {
for(int j = 1; j < n; j *= 2) {
// O(1) operation
}
}
// O(n) - Sequential loops
for(int i = 0; i < n; i++) {
// O(1)
}
for(int j = 0; j < n; j++) {
// O(1)
}
// Total: O(n) + O(n) = O(n)
Space Complexity
Definition: Amount of memory required by an algorithm relative to input size.
Examples:
// O(1) space - constant extra space
int sum(int arr[], int n) {
int total = 0; // Single variable
for(int i = 0; i < n; i++) {
total += arr[i];
}
return total;
}

// O(n) space - auxiliary array

void doubleArray(int arr[], int n) {
int temp = (int)malloc(n * sizeof(int)); // O(n) space
for(int i = 0; i < n; i++) {
temp[i] = arr[i] * 2;
}
free(temp);
}
// O(n) space - recursive call stack
int factorial(int n) {
if(n <= 1) return 1;
return n * factorial(n-1); // O(n) recursive calls
}

Chapter 3: Arrays and Strings

Arrays - Definition
Definition: An array is a contiguous block of memory storing elements of the same data
type, accessible via zero-based indexing[3].
Properties:

• Fixed size (in static arrays)

• O(1) random access
• Contiguous memory allocation
• Homogeneous elements

Basic Array Operations

Declaration and Initialization:
// Static array declaration
int arr[100]; // Uninitialized
int arr2[5] = {1, 2, 3, 4, 5}; // Initialized
int arr3[5] = {0}; // All zeros
// Dynamic array allocation
int arr = (int)malloc(n * sizeof(int));
// Remember to free
free(arr);
// 2D array
int matrix[3][4];
int dynamic_matrix = (int)malloc(rows * sizeof(int*));
for(int i = 0; i < rows; i++) {
dynamic_matrix[i] = (int*)malloc(cols * sizeof(int));
}

Array Traversal - O(n):

void printArray(int arr[], int n) {
for(int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
Insertion at End - O(1):

void insertEnd(int arr[], int *n, int element) {

arr[*n] = element;
(*n)++;
}
Insertion at Position - O(n):
void insertAt(int arr[], int *n, int pos, int element) {
// Shift elements right
for(int i = *n; i > pos; i--) {
arr[i] = arr[i-1];
}
arr[pos] = element;
(*n)++;
}

Deletion - O(n):
void deleteAt(int arr[], int *n, int pos) {
// Shift elements left
for(int i = pos; i < *n - 1; i++) {
arr[i] = arr[i+1];
}
(*n)--;
}
Common Array Patterns
Pattern 1: Prefix Sum
Problem: Answer multiple range sum queries efficiently.
Approach: Precompute cumulative sums.

void buildPrefixSum(int arr[], int prefix[], int n) {

prefix[0] = arr[0];
for(int i = 1; i < n; i++) {
prefix[i] = prefix[i-1] + arr[i];
}
}
int rangeSum(int prefix[], int left, int right) {
if(left == 0) return prefix[right];
return prefix[right] - prefix[left-1];
}
Pattern 2: Sliding Window

Problem: Find maximum sum of k consecutive elements.

int maxSumSubarray(int arr[], int n, int k) {
int maxSum = 0, windowSum = 0;

// First window
for(int i = 0; i < k; i++) {
windowSum += arr[i];
}
maxSum = windowSum;

// Slide the window

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

return maxSum;

}
Pattern 3: Two Pointers
Problem: Find pair with given sum in sorted array.
bool findPair(int arr[], int n, int target) {
int left = 0, right = n - 1;

while(left < right) {

int sum = arr[left] + arr[right];
if(sum == target) return true;
else if(sum < target) left++;
else right--;
}

return false;

}
Pattern 4: Kadane's Algorithm (Maximum Subarray Sum)
Problem: Find contiguous subarray with maximum sum.

Time Complexity: O(n)

int maxSubarraySum(int arr[], int n) {
int maxSoFar = arr[0];
int maxEndingHere = arr[0];

for(int i = 1; i < n; i++) {

maxEndingHere = max(arr[i], maxEndingHere + arr[i]);
maxSoFar = max(maxSoFar, maxEndingHere);
}

return maxSoFar;

Strings in C
Definition: A string in C is an array of characters terminated by null character \0.
String Operations:
#include <string.h>

// Length
int len = strlen(str);
// Copy
char dest[100];
strcpy(dest, source);
// Concatenation
strcat(dest, source);

// Comparison
if(strcmp(str1, str2) == 0) {
// Strings are equal
}
// Character check
#include <ctype.h>
if(isalpha(c)) { /* alphabetic / }
if(isdigit(c)) { / digit / }
if(islower(c)) { / lowercase / }
if(isupper(c)) { / uppercase */ }
String Pattern Matching:

// Check if string is palindrome

bool isPalindrome(char str[]) {
int left = 0, right = strlen(str) - 1;

while(left < right) {

if(str[left] != str[right]) return false;
left++;
right--;
}
return true;

// Reverse string in-place

void reverseString(char str[]) {
int left = 0, right = strlen(str) - 1;

while(left < right) {

char temp = str[left];
str[left] = str[right];
str[right] = temp;
left++;
right--;
}

}
Practice Problems
1. Find second largest element in array (O(n))
2. Rotate array by k positions
3. Find missing number in array containing 1 to n
4. Merge two sorted arrays
5. Count frequency of each element
6. Remove duplicates from sorted array
7. Find longest substring without repeating characters
8. Check if two strings are anagrams

Chapter 4: Searching Algorithms

Linear Search
Definition: Sequential search through all elements until target is found or end is
reached[4].
Time Complexity: O(n)
Space Complexity: O(1)
Algorithm:

int linearSearch(int arr[], int n, int target) {

for(int i = 0; i < n; i++) {
if(arr[i] == target) {
return i; // Found at index i
}
}
return -1; // Not found
}
Use Cases:
• Unsorted data
• Small datasets
• Single search operation

Binary Search
Definition: Divide-and-conquer algorithm that repeatedly halves the search space in a
sorted array[5].

Prerequisites: Array must be sorted

Time Complexity: O(log n)
Space Complexity: O(1) iterative, O(log n) recursive
Iterative Implementation:

int binarySearch(int arr[], int n, int target) {

int left = 0, right = n - 1;
 while(left <= right) {
int mid = left + (right - left) / 2; // Avoid overflow

if(arr[mid] == target) {
return mid; // Found
} else if(arr[mid] < target) {
left = mid + 1; // Search right half
} else {
right = mid - 1; // Search left half
}
}

return -1; // Not found

Recursive Implementation:
int binarySearchRecursive(int arr[], int left, int right, int target) {
if(left > right) return -1;

int mid = left + (right - left) / 2;

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

else if(arr[mid] < target)
return binarySearchRecursive(arr, mid + 1, right, target);
else
return binarySearchRecursive(arr, left, mid - 1, target);

Binary Search Variants

Lower Bound: Find first element >= target
int lowerBound(int arr[], int n, int target) {
int left = 0, right = n - 1, result = n;

while(left <= right) {

int mid = left + (right - left) / 2;
 if(arr[mid] >= target) {
result = mid;
right = mid - 1; // Look for smaller index
} else {
left = mid + 1;
}
}

return result;

Upper Bound: Find first element > target

int upperBound(int arr[], int n, int target) {
int left = 0, right = n - 1, result = n;

while(left <= right) {

int mid = left + (right - left) / 2;

if(arr[mid] > target) {

result = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}

return result;

}
Finding First and Last Occurrence:
int findFirst(int arr[], int n, int target) {
int left = 0, right = n - 1, result = -1;

while(left <= right) {

int mid = left + (right - left) / 2;

if(arr[mid] == target) {
 result = mid;
right = mid - 1; // Continue searching left
} else if(arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}

return result;

int findLast(int arr[], int n, int target) {

int left = 0, right = n - 1, result = -1;

while(left <= right) {

int mid = left + (right - left) / 2;

if(arr[mid] == target) {
result = mid;
left = mid + 1; // Continue searching right
} else if(arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}

return result;

Binary Search on Answer

Pattern: When answer space is monotonic, binary search on possible answers.

Problem: Find square root using binary search.

int sqrtBS(int x) {
if(x == 0 || x == 1) return x;
 int left = 1, right = x, result = 0;

while(left <= right) {

int mid = left + (right - left) / 2;

if(mid <= x / mid) { // Avoid overflow

result = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}

return result;

Problem: Find minimum in rotated sorted array.

int findMin(int arr[], int n) {
int left = 0, right = n - 1;

while(left < right) {

int mid = left + (right - left) / 2;

if(arr[mid] > arr[right]) {

left = mid + 1; // Minimum in right half
} else {
right = mid; // Minimum in left half or at mid
}
}

return arr[left];

}
Ternary Search
Definition: Divide search space into three parts (for unimodal functions).
Time Complexity: O(log₃ n)
double ternarySearch(double left, double right, double (*f)(double)) {
double eps = 1e-9;

while(right - left > eps) {

double mid1 = left + (right - left) / 3;
double mid2 = right - (right - left) / 3;

if(f(mid1) < f(mid2)) {

left = mid1;
} else {
right = mid2;
}
}

return left;

Practice Problems
1. Search in rotated sorted array
2. Find peak element in array
3. Search in 2D sorted matrix
4. Find kth smallest element
5. Aggressive cows (binary search on answer)
6. Book allocation problem
7. Painter's partition problem
8. Find median of two sorted arrays

Chapter 5: Sorting Algorithms

Bubble Sort
Definition: Repeatedly swap adjacent elements if they are in wrong order.
Time Complexity: O(n²)
Space Complexity: O(1)
Stable: Yes

void bubbleSort(int arr[], int n) {

for(int i = 0; i < n - 1; i++) {
bool swapped = false;

for(int j = 0; j < n - i - 1; j++) {

if(arr[j] > arr[j + 1]) {
swap(arr[j], arr[j + 1]);
swapped = true;
}
}

// If no swap, array is sorted

if(!swapped) break;
}

Selection Sort
Definition: Find minimum element and place it at beginning, repeat for remaining
elements.
Time Complexity: O(n²)
Space Complexity: O(1)
Stable: No
void selectionSort(int arr[], int n) {
for(int i = 0; i < n - 1; i++) {
int minIdx = i;

// Find minimum in unsorted portion

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

// Swap with first unsorted element

if(minIdx != i) {
swap(arr[i], arr[minIdx]);
}
}

}
Insertion Sort
Definition: Build sorted array one element at a time by inserting elements in correct
position.
Time Complexity: O(n²) worst, O(n) best
Space Complexity: O(1)
Stable: Yes
void insertionSort(int arr[], int n) {
for(int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;

// Move elements greater than key one position ahead

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

arr[j + 1] = key;
}

Merge Sort
Definition: Divide array into two halves, recursively sort them, then merge[6].

Time Complexity: O(n log n)

Space Complexity: O(n)
Stable: Yes
void merge(int arr[], int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;

// Create temp arrays

int *L = (int*)malloc(n1 * sizeof(int));
int *R = (int*)malloc(n2 * sizeof(int));

// Copy data
for(int i = 0; i < n1; i++)
L[i] = arr[left + i];
for(int j = 0; j < n2; j++)
 R[j] = arr[mid + 1 + j];

// Merge back
int i = 0, j = 0, k = left;

while(i < n1 && j < n2) {

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

// Copy remaining
while(i < n1) arr[k++] = L[i++];
while(j < n2) arr[k++] = R[j++];

free(L);
free(R);

void mergeSort(int arr[], int left, int right) {

if(left < right) {
int mid = left + (right - left) / 2;

mergeSort(arr, left, mid);

mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}

Quick Sort
Definition: Select pivot, partition array around pivot, recursively sort partitions[7].

Time Complexity: O(n log n) average, O(n²) worst

Space Complexity: O(log n)
Stable: No
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);
}

}
Randomized Quick Sort (Better average case):
int randomPartition(int arr[], int low, int high) {
int random = low + rand() % (high - low + 1);
swap(arr[random], arr[high]);
return partition(arr, low, high);
}

void randomizedQuickSort(int arr[], int low, int high) {

if(low < high) {
int pi = randomPartition(arr, low, high);
randomizedQuickSort(arr, low, pi - 1);
randomizedQuickSort(arr, pi + 1, high);
}
}
Counting Sort
Definition: Count occurrences of each value, then place elements in sorted order.
Time Complexity: O(n + k) where k is range
Space Complexity: O(k)
Stable: Yes
void countingSort(int arr[], int n) {
// Find range
int max = arr[0];
for(int i = 1; i < n; i++) {
if(arr[i] > max) max = arr[i];
}

// Count array
int *count = (int*)calloc(max + 1, sizeof(int));

// Store count
for(int i = 0; i < n; i++) {
count[arr[i]]++;
}

// Reconstruct array
int idx = 0;
for(int i = 0; i <= max; i++) {
while(count[i]-- > 0) {
arr[idx++] = i;
}
}

free(count);

Comparison of Sorting Algorithms

 Algorithm Best Average Worst Space
Bubble Sort O(n) O(n²) O(n²) O(1)
Selection Sort O(n²) O(n²) O(n²) O(1)
Insertion Sort O(n) O(n²) O(n²) 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²) O(log n)
Counting Sort O(n+k) O(n+k) O(n+k) O(k)

Table 3: Sorting algorithms comparison

qsort() - C Standard Library

#include <stdlib.h>
int compare(const void a, const void b) {
return ((int)a - (int)b); // Ascending
}

int compareDesc(const void a, const void b) {

return ((int)b - (int)a); // Descending
}
// Usage
qsort(arr, n, sizeof(int), compare);

Practice Problems
1. Sort array by frequency of elements
2. Sort array by number of set bits
3. Merge k sorted arrays
4. Count inversions in array
5. Find kth largest element (QuickSelect)
6. Sort colors (Dutch National Flag)
7. Maximum gap in sorted array
8. Minimum platforms required (interval sorting)

Chapter 6: Recursion and Backtracking

Recursion - Definition
Definition: A function that calls itself with a smaller or simpler input until reaching a base
case.
Components:

• Base case: Termination condition

• Recursive case: Function calls itself
• Progress: Each call moves toward base case
Basic Recursion Examples
Factorial:
int factorial(int n) {
// Base case
if(n <= 1) return 1;

// Recursive case
return n * factorial(n - 1);

}
Fibonacci:
int fibonacci(int n) {
if(n <= 1) return n;
return fibonacci(n - 1) + fibonacci(n - 2);
}

// Optimized with memoization

int fib[100];
int fibMemo(int n) {
if(n <= 1) return n;
if(fib[n] != -1) return fib[n];
return fib[n] = fibMemo(n - 1) + fibMemo(n - 2);
}
Power Function:

long long power(long long base, int exp) {

if(exp == 0) return 1;
if(exp == 1) return base;

long long half = power(base, exp / 2);

if(exp % 2 == 0) {
return half * half;
} else {
return base * half * half;
}

}
Backtracking - Definition
Definition: Algorithmic technique for solving problems by trying to build a solution
incrementally and abandoning solutions that fail to satisfy constraints[8].
General Template:
void backtrack(State state, Solution solution) {
if(isValid(state) == false) return;

if(isComplete(solution)) {
processSolution(solution);
return;
}

for each choice in possibleChoices(state) {

makeChoice(choice);
backtrack(nextState, solution);
unmakeChoice(choice); // Backtrack
}

N-Queens Problem
Problem: Place N queens on N×N chessboard such that no two queens attack each other.

#define MAX_N 20
int board[MAX_N][MAX_N];
int solutions = 0;
bool isSafe(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;

void solveNQueens(int row, int n) {

if(row == n) {
solutions++;
return;
}

for(int col = 0; col < n; col++) {

if(isSafe(row, col, n)) {
board[row][col] = 1; // Place queen
solveNQueens(row + 1, n);
board[row][col] = 0; // Backtrack
}
}

Subset Generation
Generate all subsets of a set:

void generateSubsets(int arr[], int n, int idx, int subset[], int size) {
// Print current subset
printf("{ ");
for(int i = 0; i < size; i++) {
printf("%d ", subset[i]);
}
printf("}\n");

// Generate subsets by including remaining elements

for(int i = idx; i < n; i++) {
subset[size] = arr[i];
generateSubsets(arr, n, i + 1, subset, size + 1);
}

// Call: generateSubsets(arr, n, 0, subset, 0);

Permutation Generation
Generate all permutations:
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
void generatePermutations(int arr[], int left, int right) {
if(left == right) {
// Print permutation
for(int i = 0; i <= right; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return;
}

for(int i = left; i <= right; i++) {

swap(&arr[left], &arr[i]);
generatePermutations(arr, left + 1, right);
swap(&arr[left], &arr[i]); // Backtrack
}

Rat in a Maze
Problem: Find path from (0,0) to (n-1,n-1) in maze with obstacles.

#define N 4
int maze[N][N];
int solution[N][N];
bool isSafe(int x, int y) {
return (x >= 0 && x < N && y >= 0 && y < N && maze[x][y] == 1);
}
bool solveMaze(int x, int y) {
// Reached destination
if(x == N - 1 && y == N - 1) {
solution[x][y] = 1;
return true;
}
 if(isSafe(x, y)) {
solution[x][y] = 1;

// Move right
if(solveMaze(x, y + 1)) return true;

// Move down
if(solveMaze(x + 1, y)) return true;

// Backtrack
solution[x][y] = 0;
return false;
}

return false;

Sudoku Solver
#define SIZE 9

bool isSafeSudoku(int grid[SIZE][SIZE], int row, int col, int num) {

// Check row
for(int x = 0; x < SIZE; x++) {
if(grid[row][x] == num) return false;
}

// Check column
for(int x = 0; x < SIZE; x++) {
if(grid[x][col] == num) return false;
}

// Check 3x3 box

int startRow = row - row % 3;
int startCol = col - col % 3;
for(int i = 0; i < 3; i++) {
for(int j = 0; j < 3; j++) {
if(grid[i + startRow][j + startCol] == num) return false;
}
 }

return true;

bool solveSudoku(int grid[SIZE][SIZE], int row, int col) {

// Reached end
if(row == SIZE - 1 && col == SIZE) return true;

// Move to next row

if(col == SIZE) {
row++;
col = 0;
}

// Skip filled cells

if(grid[row][col] != 0) {
return solveSudoku(grid, row, col + 1);
}

// Try digits 1-9

for(int num = 1; num <= 9; num++) {
if(isSafeSudoku(grid, row, col, num)) {
grid[row][col] = num;

if(solveSudoku(grid, row, col + 1)) return true;

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

return false;

}
Practice Problems
1. Generate all balanced parentheses combinations
2. Word search in 2D grid
3. Combination sum
4. Letter combinations of phone number
5. Palindrome partitioning
6. Knight's tour problem
7. Hamiltonian path
8. Graph coloring problem

Chapter 7: Stacks and Queues

Stack - Definition
Definition: Linear data structure following Last-In-First-Out (LIFO) principle[9].
Operations:
• Push: Add element to top - O(1)
• Pop: Remove element from top - O(1)
• Peek/Top: View top element - O(1)
• isEmpty: Check if empty - O(1)

Stack Implementation (Array-based)

#define MAX_SIZE 1000

typedef struct {
int data[MAX_SIZE];
int top;
} Stack;
void initStack(Stack *s) {
s->top = -1;
}
bool isEmpty(Stack *s) {
return s->top == -1;
}

bool isFull(Stack *s) {

return s->top == MAX_SIZE - 1;
}
void push(Stack *s, int value) {
if(isFull(s)) {
printf("Stack overflow\n");
return;
}
s->data[++(s->top)] = value;
}
int pop(Stack *s) {
if(isEmpty(s)) {
printf("Stack underflow\n");
return -1;
}
return s->data[(s->top)--];
}
int peek(Stack *s) {
if(isEmpty(s)) return -1;
return s->data[s->top];
}

Stack Applications
Balanced Parentheses:

bool isBalanced(char expr[]) {

Stack s;
initStack(&s);

for(int i = 0; expr[i]; i++) {

if(expr[i] == '(' || expr[i] == '{' || expr[i] == '[') {
push(&s, expr[i]);
} else if(expr[i] == ')' || expr[i] == '}' || expr[i] == ']') {
if(isEmpty(&s)) return false;

char top = pop(&s);

if((expr[i] == ')' && top != '(') ||
(expr[i] == '}' && top != '{') ||
(expr[i] == ']' && top != '[')) {
return false;
}
}
}

return isEmpty(&s);

Next Greater Element:

void nextGreater(int arr[], int n, int result[]) {
Stack s;
initStack(&s);
 // Traverse from right to left
for(int i = n - 1; i >= 0; i--) {
// Pop elements smaller than current
while(!isEmpty(&s) && peek(&s) <= arr[i]) {
pop(&s);
}

result[i] = isEmpty(&s) ? -1 : peek(&s);

push(&s, arr[i]);
}

Stock Span Problem:

void calculateSpan(int price[], int n, int span[]) {
Stack s;
initStack(&s);

for(int i = 0; i < n; i++) {

// Pop elements smaller than current price
while(!isEmpty(&s) && price[peek(&s)] <= price[i]) {
pop(&s);
}

span[i] = isEmpty(&s) ? (i + 1) : (i - peek(&s));

push(&s, i);
}

Queue - Definition
Definition: Linear data structure following First-In-First-Out (FIFO) principle[10].
Operations:
• Enqueue: Add element to rear - O(1)
• Dequeue: Remove element from front - O(1)
• Front: View front element - O(1)
• isEmpty: Check if empty - O(1)
Queue Implementation (Circular Array)
#define MAX_SIZE 1000
typedef struct {
int data[MAX_SIZE];
int front, rear, size;
} Queue;
void initQueue(Queue *q) {
q->front = 0;
q->rear = -1;
q->size = 0;
}

bool isEmptyQueue(Queue *q) {

return q->size == 0;
}
bool isFullQueue(Queue *q) {
return q->size == MAX_SIZE;
}
void enqueue(Queue *q, int value) {
if(isFullQueue(q)) {
printf("Queue overflow\n");
return;
}
q->rear = (q->rear + 1) % MAX_SIZE;
q->data[q->rear] = value;
q->size++;
}

int dequeue(Queue *q) {

if(isEmptyQueue(q)) {
printf("Queue underflow\n");
return -1;
}
int value = q->data[q->front];
q->front = (q->front + 1) % MAX_SIZE;
q->size--;
return value;
}
int front(Queue *q) {
if(isEmptyQueue(q)) return -1;
return q->data[q->front];
}
Deque (Double-ended Queue)
typedef struct {
int data[MAX_SIZE];
int front, rear, size;
} Deque;
void initDeque(Deque *dq) {
dq->front = -1;
dq->rear = 0;
dq->size = 0;
}
void insertFront(Deque *dq, int value) {
if(dq->size == MAX_SIZE) return;

if(dq->front == -1) {
dq->front = 0;
dq->rear = 0;
} else {
dq->front = (dq->front - 1 + MAX_SIZE) % MAX_SIZE;
}

dq->data[dq->front] = value;
dq->size++;

}
void insertRear(Deque *dq, int value) {
if(dq->size == MAX_SIZE) return;

if(dq->front == -1) {
dq->front = 0;
dq->rear = 0;
} else {
dq->rear = (dq->rear + 1) % MAX_SIZE;
}

dq->data[dq->rear] = value;
dq->size++;

}
int deleteFront(Deque *dq) {
if(dq->size == 0) return -1;

int value = dq->data[dq->front];

if(dq->front == dq->rear) {
dq->front = -1;
dq->rear = -1;
} else {
dq->front = (dq->front + 1) % MAX_SIZE;
}

dq->size--;
return value;

}
int deleteRear(Deque *dq) {
if(dq->size == 0) return -1;

int value = dq->data[dq->rear];

if(dq->front == dq->rear) {
dq->front = -1;
dq->rear = -1;
} else {
dq->rear = (dq->rear - 1 + MAX_SIZE) % MAX_SIZE;
}

dq->size--;
return value;

Sliding Window Maximum (Deque Application)

void maxSlidingWindow(int arr[], int n, int k, int result[]) {
Deque dq;
initDeque(&dq);
int resultIdx = 0;
 for(int i = 0; i < n; i++) {
// Remove elements outside window
if(dq.size > 0 && dq.data[dq.front] <= i - k) {
deleteFront(&dq);
}

// Remove smaller elements from rear

while(dq.size > 0 && arr[dq.data[dq.rear]] <= arr[i]) {
deleteRear(&dq);
}

insertRear(&dq, i);

// Store result after first window

if(i >= k - 1) {
result[resultIdx++] = arr[dq.data[dq.front]];
}
}

Practice Problems
1. Implement stack using queues
2. Implement queue using stacks
3. Largest rectangle in histogram
4. Min stack (supporting getMin in O(1))
5. Evaluate postfix expression
6. Infix to postfix conversion
7. Celebrity problem
8. Rotten oranges (BFS using queue)

Chapter 8: Linked Lists

Singly Linked List - Definition
Definition: Linear data structure where elements are stored in nodes, each containing data
and pointer to next node[11].

Advantages:
• Dynamic size
• Efficient insertion/deletion at beginning - O(1)
• No memory waste
Disadvantages:
• No random access - O(n)
• Extra memory for pointers
• Sequential access only

Node Structure
typedef struct Node {
int data;
struct Node *next;
} Node;

Node* createNode(int data) {

Node newNode = (Node)malloc(sizeof(Node));
newNode->data = data;
newNode->next = NULL;
return newNode;
}

Basic Operations
Insert at Beginning - O(1):
void insertAtBegin(Node **head, int data) {
Node *newNode = createNode(data);
newNode->next = *head;
*head = newNode;
}

Insert at End - O(n):

void insertAtEnd(Node **head, int data) {
Node *newNode = createNode(data);

if(*head == NULL) {
*head = newNode;
return;
}

Node *temp = *head;

while(temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;

}
Insert at Position - O(n):
void insertAtPosition(Node **head, int data, int pos) {
if(pos == 0) {
insertAtBegin(head, data);
return;
}

Node *newNode = createNode(data);

Node *temp = *head;

for(int i = 0; i < pos - 1 && temp != NULL; i++) {

temp = temp->next;
}

if(temp == NULL) return;

newNode->next = temp->next;
temp->next = newNode;

}
Delete Node - O(n):

void deleteNode(Node **head, int key) {

Node *temp = *head;
Node *prev = NULL;

// If head contains key

if(temp != NULL && temp->data == key) {
*head = temp->next;
free(temp);
return;
}

// Search for key

while(temp != NULL && temp->data != key) {
prev = temp;
temp = temp->next;
}
 if(temp == NULL) return; // Not found

prev->next = temp->next;
free(temp);

Search - O(n):
bool search(Node *head, int key) {
Node *current = head;
while(current != NULL) {
if(current->data == key) return true;
current = current->next;
}
return false;
}
Display:

void display(Node *head) {

Node *temp = head;
while(temp != NULL) {
printf("%d -> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}

Advanced Linked List Problems

Reverse Linked List - O(n):
Node* reverse(Node *head) {
Node *prev = NULL;
Node *current = head;
Node *next = NULL;

while(current != NULL) {
next = current->next;
current->next = prev;
prev = current;
current = next;
}

return prev;
}
Detect Cycle (Floyd's Algorithm) - O(n):

bool hasCycle(Node *head) {

if(head == NULL) return false;

Node *slow = head;

Node *fast = head;

while(fast != NULL && fast->next != NULL) {

slow = slow->next;
fast = fast->next->next;

if(slow == fast) return true;

}

return false;

Find Cycle Start:

Node* detectCycleStart(Node *head) {
if(head == NULL) return NULL;

Node *slow = head;

Node *fast = head;
bool hasCycle = false;

while(fast != NULL && fast->next != NULL) {

slow = slow->next;
fast = fast->next->next;

if(slow == fast) {
hasCycle = true;
break;
}
}

if(!hasCycle) return NULL;

 slow = head;
while(slow != fast) {
slow = slow->next;
fast = fast->next;
}

return slow;

Find Middle Element:

Node* findMiddle(Node *head) {
if(head == NULL) return NULL;

Node *slow = head;

Node *fast = head;

while(fast->next != NULL && fast->next->next != NULL) {

slow = slow->next;
fast = fast->next->next;
}

return slow;

}
Merge Two Sorted Lists:
Node* mergeSorted(Node *l1, Node *l2) {
if(l1 == NULL) return l2;
if(l2 == NULL) return l1;

Node *result;

if(l1->data <= l2->data) {

result = l1;
result->next = mergeSorted(l1->next, l2);
} else {
result = l2;
 result->next = mergeSorted(l1, l2->next);
}

return result;

Remove Nth Node from End:

Node* removeNthFromEnd(Node *head, int n) {
Node *dummy = createNode(0);
dummy->next = head;
Node *first = dummy;
Node *second = dummy;

// Move first n+1 steps ahead

for(int i = 0; i <= n; i++) {
first = first->next;
}

// Move both until first reaches end

while(first != NULL) {
first = first->next;
second = second->next;
}

// Delete node
Node *toDelete = second->next;
second->next = second->next->next;
free(toDelete);

return dummy->next;

Doubly Linked List

typedef struct DNode {
int data;
struct DNode *prev;
struct DNode *next;
} DNode;
DNode* createDNode(int data) {
DNode newNode = (DNode)malloc(sizeof(DNode));
newNode->data = data;
newNode->prev = NULL;
newNode->next = NULL;
return newNode;
}
void insertAtBeginDLL(DNode **head, int data) {
DNode *newNode = createDNode(data);
newNode->next = *head;

if(*head != NULL) {
(*head)->prev = newNode;
}

*head = newNode;

}
void deleteNodeDLL(DNode **head, DNode *del) {
if(*head == NULL || del == NULL) return;

if(*head == del) {
*head = del->next;
}

if(del->next != NULL) {
del->next->prev = del->prev;
}

if(del->prev != NULL) {
del->prev->next = del->next;
}

free(del);

}
Circular Linked List
void insertCircular(Node **head, int data) {
Node *newNode = createNode(data);

if(*head == NULL) {
newNode->next = newNode;
*head = newNode;
return;
}

Node *temp = *head;

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

temp->next = newNode;
newNode->next = *head;

Practice Problems
1. Palindrome linked list
2. Intersection point of two linked lists
3. Add two numbers represented by linked lists
4. Clone linked list with random pointer
5. Flatten multilevel linked list
6. Sort linked list (merge sort)
7. Rotate linked list
8. Swap nodes in pairs

Chapter 9: Hashing
Hash Table - Definition
Definition: Data structure that maps keys to values using a hash function, providing
average O(1) lookup, insertion, and deletion[12].

Components:
• Hash function: Converts key to array index
• Hash table: Array storing key-value pairs
• Collision resolution: Handle multiple keys mapping to same index
Hash Functions
Simple Hash Functions:
// Division method
int hashDivision(int key, int tableSize) {
return key % tableSize;
}
// Multiplication method
int hashMultiplication(int key, int tableSize) {
double A = 0.6180339887; // Golden ratio
double frac = key * A - (int)(key * A);
return (int)(tableSize * frac);
}

// String hashing (polynomial rolling hash)

unsigned long hashString(char *str) {
unsigned long hash = 5381;
int c;

while((c = *str++)) {
hash = ((hash << 5) + hash) + c; // hash * 33 + c
}

return hash;

Collision Resolution - Chaining

#define TABLE_SIZE 1000
typedef struct Entry {
int key;
int value;
struct Entry *next;
} Entry;
typedef struct {
Entry *buckets[TABLE_SIZE];
} HashTable;

void initHashTable(HashTable *ht) {

for(int i = 0; i < TABLE_SIZE; i++) {
ht->buckets[i] = NULL;
}
}
void insert(HashTable *ht, int key, int value) {
int index = key % TABLE_SIZE;

Entry *newEntry = (Entry*)malloc(sizeof(Entry));

newEntry->key = key;
newEntry->value = value;
newEntry->next = ht->buckets[index];
ht->buckets[index] = newEntry;

}
int search(HashTable *ht, int key) {
int index = key % TABLE_SIZE;
Entry *current = ht->buckets[index];

while(current != NULL) {
if(current->key == key) {
return current->value;
}
current = current->next;
}

return -1; // Not found

}
void deleteKey(HashTable *ht, int key) {
int index = key % TABLE_SIZE;
Entry *current = ht->buckets[index];
Entry *prev = NULL;

while(current != NULL && current->key != key) {

prev = current;
current = current->next;
}

if(current == NULL) return; // Not found

if(prev == NULL) {
ht->buckets[index] = current->next;
 } else {
prev->next = current->next;
}

free(current);

Collision Resolution - Open Addressing

Linear Probing:

typedef struct {
int key;
int value;
bool occupied;
} HashEntry;
typedef struct {
HashEntry entries[TABLE_SIZE];
int size;
} HashTableOpen;
void initHashTableOpen(HashTableOpen *ht) {
for(int i = 0; i < TABLE_SIZE; i++) {
ht->entries[i].occupied = false;
}
ht->size = 0;
}

void insertOpen(HashTableOpen *ht, int key, int value) {

int index = key % TABLE_SIZE;
int i = 0;

while(ht->entries[(index + i) % TABLE_SIZE].occupied) {
i++;
if(i == TABLE_SIZE) return; // Table full
}

int finalIndex = (index + i) % TABLE_SIZE;

ht->entries[finalIndex].key = key;
ht->entries[finalIndex].value = value;
ht->entries[finalIndex].occupied = true;
ht->size++;
}
int searchOpen(HashTableOpen *ht, int key) {
int index = key % TABLE_SIZE;
int i = 0;

while(ht->entries[(index + i) % TABLE_SIZE].occupied) {
int currentIndex = (index + i) % TABLE_SIZE;
if(ht->entries[currentIndex].key == key) {
return ht->entries[currentIndex].value;
}
i++;
if(i == TABLE_SIZE) break;
}

return -1; // Not found

}
Quadratic Probing:

void insertQuadratic(HashTableOpen *ht, int key, int value) {

int index = key % TABLE_SIZE;
int i = 0;

while(ht->entries[(index + i*i) % TABLE_SIZE].occupied) {

i++;
if(i == TABLE_SIZE) return;
}

int finalIndex = (index + i*i) % TABLE_SIZE;

ht->entries[finalIndex].key = key;
ht->entries[finalIndex].value = value;
ht->entries[finalIndex].occupied = true;
ht->size++;

}
Hash Map Applications
Count Frequency of Elements:
void countFrequency(int arr[], int n) {
HashTable ht;
initHashTable(&ht);

for(int i = 0; i < n; i++) {

int freq = search(&ht, arr[i]);
if(freq == -1) {
insert(&ht, arr[i], 1);
} else {
insert(&ht, arr[i], freq + 1);
}
}

}
Two Sum Problem:
int* twoSum(int nums[], int n, int target, int *returnSize) {
HashTable ht;
initHashTable(&ht);

for(int i = 0; i < n; i++) {

int complement = target - nums[i];
int index = search(&ht, complement);

if(index != -1) {
int *result = (int*)malloc(2 * sizeof(int));
result[0] = index;
result[1] = i;
*returnSize = 2;
return result;
}

insert(&ht, nums[i], i);

}
 *returnSize = 0;
return NULL;

Longest Consecutive Sequence:

int longestConsecutive(int nums[], int n) {
HashTable ht;
initHashTable(&ht);

// Insert all numbers

for(int i = 0; i < n; i++) {
insert(&ht, nums[i], 1);
}

int maxLength = 0;

for(int i = 0; i < n; i++) {

// Check if start of sequence
if(search(&ht, nums[i] - 1) == -1) {
int currentNum = nums[i];
int currentLength = 1;

while(search(&ht, currentNum + 1) != -1) {

currentNum++;
currentLength++;
}

maxLength = max(maxLength, currentLength);

}
}

return maxLength;

}
Rolling Hash (Rabin-Karp)
#define BASE 256
#define PRIME 101
bool rabinKarpSearch(char text[], char pattern[]) {
int n = strlen(text);
int m = strlen(pattern);
int patternHash = 0, textHash = 0;
int h = 1;

// Calculate h = pow(BASE, m-1) % PRIME

for(int i = 0; i < m - 1; i++) {
h = (h * BASE) % PRIME;
}

// Calculate initial hash values

for(int i = 0; i < m; i++) {
patternHash = (BASE * patternHash + pattern[i]) % PRIME;
textHash = (BASE * textHash + text[i]) % PRIME;
}

// Slide pattern over text

for(int i = 0; i <= n - m; i++) {
if(patternHash == textHash) {
// Check character by character
int j;
for(j = 0; j < m; j++) {
if(text[i + j] != pattern[j]) break;
}
if(j == m) return true;
}

// Calculate hash for next window

if(i < n - m) {
textHash = (BASE * (textHash - text[i] * h) + text[i + m]) % PRIME;
if(textHash < 0) textHash += PRIME;
}
}
 return false;

Practice Problems
1. Group anagrams
2. Subarray with sum zero
3. Longest subarray with equal 0s and 1s
4. Count distinct elements in every window
5. Find itinerary from tickets
6. LRU Cache implementation
7. First non-repeating character
8. Isomorphic strings

Chapter 10: Trees

Binary Tree - Definition
Definition: Hierarchical data structure where each node has at most two children (left and
right)[13].

Properties:
• Maximum nodes at level i: 2^i
• Maximum nodes in tree of height h: 2^(h+1) - 1
• Minimum height for n nodes: log₂(n+1) - 1

Tree Node Structure

typedef struct TreeNode {
int data;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
TreeNode* createTreeNode(int data) {
TreeNode node = (TreeNode)malloc(sizeof(TreeNode));
node->data = data;
node->left = NULL;
node->right = NULL;
return node;
}
Tree Traversals
Inorder (Left-Root-Right):
void inorder(TreeNode *root) {
if(root == NULL) return;

inorder(root->left);
printf("%d ", root->data);
inorder(root->right);

}
Preorder (Root-Left-Right):
void preorder(TreeNode *root) {
if(root == NULL) return;

printf("%d ", root->data);

preorder(root->left);
preorder(root->right);

}
Postorder (Left-Right-Root):

void postorder(TreeNode *root) {

if(root == NULL) return;

postorder(root->left);
postorder(root->right);
printf("%d ", root->data);

Level Order (BFS):

void levelOrder(TreeNode *root) {
if(root == NULL) return;

Queue q;
initQueue(&q);
enqueue(&q, (int)root);
 while(!isEmptyQueue(&q)) {
TreeNode *current = (TreeNode*)dequeue(&q);
printf("%d ", current->data);

if(current->left) enqueue(&q, (int)current->left);

if(current->right) enqueue(&q, (int)current->right);
}

Tree Properties
Height of Tree:

int height(TreeNode *root) {

if(root == NULL) return -1;

int leftHeight = height(root->left);

int rightHeight = height(root->right);

return 1 + max(leftHeight, rightHeight);

Count Nodes:
int countNodes(TreeNode *root) {
if(root == NULL) return 0;
return 1 + countNodes(root->left) + countNodes(root->right);
}
Sum of All Nodes:

int sumNodes(TreeNode *root) {

if(root == NULL) return 0;
return root->data + sumNodes(root->left) + sumNodes(root->right);
}
Diameter of Tree (Longest path between any two nodes):
int diameterUtil(TreeNode *root, int *height) {
if(root == NULL) {
*height = 0;
return 0;
}
 int leftHeight = 0, rightHeight = 0;
int leftDiameter = diameterUtil(root->left, &leftHeight);
int rightDiameter = diameterUtil(root->right, &rightHeight);

*height = 1 + max(leftHeight, rightHeight);

return max(leftHeight + rightHeight, max(leftDiameter, rightDiameter));

int diameter(TreeNode *root) {

int height = 0;
return diameterUtil(root, &height);
}

Advanced Tree Problems

Lowest Common Ancestor:
TreeNode* lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q) {
if(root == NULL || root == p || root == q) {
return root;
}

TreeNode *left = lowestCommonAncestor(root->left, p, q);

TreeNode *right = lowestCommonAncestor(root->right, p, q);

if(left != NULL && right != NULL) return root;

return (left != NULL) ? left : right;

}
Check if Balanced:
int checkBalanced(TreeNode *root, bool *balanced) {
if(root == NULL) return 0;

int leftHeight = checkBalanced(root->left, balanced);

int rightHeight = checkBalanced(root->right, balanced);

if(abs(leftHeight - rightHeight) > 1) {

*balanced = false;
 }

return 1 + max(leftHeight, rightHeight);

bool isBalanced(TreeNode *root) {

bool balanced = true;
checkBalanced(root, &balanced);
return balanced;
}
Maximum Path Sum:
int maxPathSumUtil(TreeNode *root, int *maxSum) {
if(root == NULL) return 0;

int left = max(0, maxPathSumUtil(root->left, maxSum));

int right = max(0, maxPathSumUtil(root->right, maxSum));

*maxSum = max(*maxSum, left + right + root->data);

return root->data + max(left, right);

}
int maxPathSum(TreeNode *root) {
int maxSum = INT_MIN;
maxPathSumUtil(root, &maxSum);
return maxSum;
}

Vertical Order Traversal:

typedef struct {
TreeNode *node;
int hd; // Horizontal distance
} QueueNode;
void verticalOrder(TreeNode *root) {
if(root == NULL) return;

// Map to store nodes at each horizontal distance

// Simplified implementation
Queue q;
initQueue(&q);
 // Implementation requires hash map for horizontal distances

Serialize and Deserialize:

void serializeUtil(TreeNode *root, char *str) {
if(root == NULL) {
strcat(str, "# ");
return;
}

char temp[20];
sprintf(temp, "%d ", root->data);
strcat(str, temp);

serializeUtil(root->left, str);
serializeUtil(root->right, str);

}
TreeNode* deserializeUtil(char **str) {
char *token = strtok(*str, " ");

if(token == NULL || strcmp(token, "#") == 0) {

return NULL;
}

TreeNode *root = createTreeNode(atoi(token));

*str = NULL; // For subsequent strtok calls

root->left = deserializeUtil(str);
root->right = deserializeUtil(str);

return root;

}
Views of Binary Tree
Left View:
void leftViewUtil(TreeNode *root, int level, int *maxLevel) {
if(root == NULL) return;

if(*maxLevel < level) {

printf("%d ", root->data);
*maxLevel = level;
}

leftViewUtil(root->left, level + 1, maxLevel);

leftViewUtil(root->right, level + 1, maxLevel);

}
void leftView(TreeNode *root) {
int maxLevel = 0;
leftViewUtil(root, 1, &maxLevel);
}
Right View:

void rightViewUtil(TreeNode *root, int level, int *maxLevel) {

if(root == NULL) return;

if(*maxLevel < level) {

printf("%d ", root->data);
*maxLevel = level;
}

rightViewUtil(root->right, level + 1, maxLevel);

rightViewUtil(root->left, level + 1, maxLevel);

Top View:
// Requires horizontal distance tracking with queue/map
void topView(TreeNode *root) {
// Implementation using level order with horizontal distances
}
Practice Problems
1. Zigzag level order traversal
2. Boundary traversal
3. Check if mirror trees
4. Convert binary tree to doubly linked list
5. Construct tree from inorder and preorder
6. Count complete tree nodes
7. Flatten binary tree to linked list
8. Sum of left leaves

Chapter 11: Binary Search Trees

BST - Definition
Definition: Binary tree where for each node, all values in left subtree are smaller and all
values in right subtree are larger[14].
Properties:
• Inorder traversal gives sorted sequence
• Average search/insert/delete: O(log n)
• Worst case (skewed): O(n)

BST Operations
Search:

TreeNode* search(TreeNode *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);

Insert:
TreeNode* insert(TreeNode *root, int key) {
if(root == NULL) {
return createTreeNode(key);
}
 if(key < root->data) {
root->left = insert(root->left, key);
} else if(key > root->data) {
root->right = insert(root->right, key);
}

return root;

Find Minimum:
TreeNode* findMin(TreeNode *root) {
while(root->left != NULL) {
root = root->left;
}
return root;
}
Find Maximum:

TreeNode* findMax(TreeNode *root) {

while(root->right != NULL) {
root = root->right;
}
return root;
}
Delete Node:
TreeNode* deleteNode(TreeNode *root, int key) {
if(root == NULL) return NULL;

if(key < root->data) {

root->left = deleteNode(root->left, key);
} else if(key > root->data) {
root->right = deleteNode(root->right, key);
} else {
// Node with only one child or no child
if(root->left == NULL) {
TreeNode *temp = root->right;
free(root);
return temp;
} else if(root->right == NULL) {
 TreeNode *temp = root->left;
free(root);
return temp;
}

// Node with two children

TreeNode *temp = findMin(root->right);
root->data = temp->data;
root->right = deleteNode(root->right, temp->data);
}

return root;

BST Validation
Check if Valid BST:

bool isValidBSTUtil(TreeNode *root, long min, long max) {

if(root == NULL) return true;

if(root->data <= min || root->data >= max) {

return false;
}

return isValidBSTUtil(root->left, min, root->data) &&

isValidBSTUtil(root->right, root->data, max);

bool isValidBST(TreeNode *root) {

return isValidBSTUtil(root, LONG_MIN, LONG_MAX);
}

BST Advanced Problems

Kth Smallest Element:
void kthSmallestUtil(TreeNode *root, int *k, int *result) {
if(root == NULL) return;
 kthSmallestUtil(root->left, k, result);

(*k)--;
if(*k == 0) {
*result = root->data;
return;
}

kthSmallestUtil(root->right, k, result);

int kthSmallest(TreeNode *root, int k) {

int result = -1;
kthSmallestUtil(root, &k, &result);
return result;
}
Inorder Successor:
TreeNode* inorderSuccessor(TreeNode *root, TreeNode *target) {
TreeNode *successor = NULL;

while(root != NULL) {
if(target->data < root->data) {
successor = root;
root = root->left;
} else {
root = root->right;
}
}

return successor;

}
Convert Sorted Array to BST:

TreeNode* sortedArrayToBST(int arr[], int start, int end) {

if(start > end) return NULL;
 int mid = start + (end - start) / 2;
TreeNode *root = createTreeNode(arr[mid]);

root->left = sortedArrayToBST(arr, start, mid - 1);

root->right = sortedArrayToBST(arr, mid + 1, end);

return root;

Trim BST:
TreeNode* trimBST(TreeNode *root, int low, int high) {
if(root == NULL) return NULL;

if(root->data < low) {

return trimBST(root->right, low, high);
}

if(root->data > high) {

return trimBST(root->left, low, high);
}

root->left = trimBST(root->left, low, high);

root->right = trimBST(root->right, low, high);

return root;

}
Recover BST (Two nodes swapped):
void recoverBSTUtil(TreeNode *root, TreeNode **first, TreeNode **second,
TreeNode **prev) {
if(root == NULL) return;

recoverBSTUtil(root->left, first, second, prev);

if(*prev && (*prev)->data > root->data) {

if(*first == NULL) {
 *first = *prev;
}
*second = root;
}

*prev = root;

recoverBSTUtil(root->right, first, second, prev);

void recoverTree(TreeNode *root) {

TreeNode *first = NULL, *second = NULL, *prev = NULL;
recoverBSTUtil(root, &first, &second, &prev);

if(first && second) {

int temp = first->data;
first->data = second->data;
second->data = temp;
}

AVL Tree (Self-Balancing BST)

AVL Node:

typedef struct AVLNode {

int data;
struct AVLNode *left;
struct AVLNode *right;
int height;
} AVLNode;
int getHeight(AVLNode *node) {
return node ? node->height : 0;
}
int getBalance(AVLNode *node) {
return node ? getHeight(node->left) - getHeight(node->right) : 0;
}

Rotations:
AVLNode* rightRotate(AVLNode *y) {
AVLNode *x = y->left;
AVLNode *T2 = x->right;

x->right = y;
y->left = T2;

y->height = 1 + max(getHeight(y->left), getHeight(y->right));

x->height = 1 + max(getHeight(x->left), getHeight(x->right));

return x;

}
AVLNode* leftRotate(AVLNode *x) {
AVLNode *y = x->right;
AVLNode *T2 = y->left;

y->left = x;
x->right = T2;

x->height = 1 + max(getHeight(x->left), getHeight(x->right));

y->height = 1 + max(getHeight(y->left), getHeight(y->right));

return y;

}
AVL Insert:
AVLNode* insertAVL(AVLNode *node, int key) {
if(node == NULL) {
AVLNode newNode = (AVLNode)malloc(sizeof(AVLNode));
newNode->data = key;
newNode->left = NULL;
newNode->right = NULL;
newNode->height = 1;
return newNode;
}

if(key < node->data) {

node->left = insertAVL(node->left, key);
} else if(key > node->data) {
node->right = insertAVL(node->right, key);
 } else {
return node; // Duplicate
}

node->height = 1 + max(getHeight(node->left), getHeight(node->right));

int balance = getBalance(node);

// Left Left
if(balance > 1 && key < node->left->data) {
return rightRotate(node);
}

// Right Right
if(balance < -1 && key > node->right->data) {
return leftRotate(node);
}

// Left Right
if(balance > 1 && key > node->left->data) {
node->left = leftRotate(node->left);
return rightRotate(node);
}

// Right Left
if(balance < -1 && key < node->right->data) {
node->right = rightRotate(node->right);
return leftRotate(node);
}

return node;

}
Practice Problems
1. Merge two BSTs
2. Largest BST in binary tree
3. Construct BST from preorder
4. Count BST nodes in range
5. Convert BST to greater tree
6. Pair with given sum in BST
7. Vertical sum in binary tree
8. Find mode in BST

Chapter 12: Heaps and Priority Queues

Heap - Definition
Definition: Complete binary tree where parent nodes have specific ordering relationship
with children. Max-heap: parent ≥ children. Min-heap: parent ≤ children[15].
Properties:
• Complete binary tree
• Height: O(log n)
• Root contains max (max-heap) or min (min-heap)
• Efficient insertion and deletion: O(log n)

Array Representation
For node at index i:

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

Min Heap Implementation

typedef struct {
int data[MAX_SIZE];
int size;
} MinHeap;
void initMinHeap(MinHeap *heap) {
heap->size = 0;
}
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}

int parent(int i) { return (i - 1) / 2; }

int leftChild(int i) { return 2 * i + 1; }
int rightChild(int i) { return 2 * i + 2; }
Heapify Down (for deletion):
void heapifyDown(MinHeap *heap, int i) {
int smallest = i;
int left = leftChild(i);
int right = rightChild(i);

if(left < heap->size && heap->data[left] < heap->data[smallest]) {

smallest = left;
}

if(right < heap->size && heap->data[right] < heap->data[smallest]) {

smallest = right;
}

if(smallest != i) {
swap(&heap->data[i], &heap->data[smallest]);
heapifyDown(heap, smallest);
}

}
Heapify Up (for insertion):

void heapifyUp(MinHeap *heap, int i) {

while(i > 0 && heap->data[parent(i)] > heap->data[i]) {
swap(&heap->data[i], &heap->data[parent(i)]);
i = parent(i);
}
}
Insert:
void insert(MinHeap *heap, int key) {
if(heap->size == MAX_SIZE) {
printf("Heap overflow\n");
return;
}

heap->data[heap->size] = key;
heapifyUp(heap, heap->size);
heap->size++;

}
Extract Min:
int extractMin(MinHeap *heap) {
if(heap->size == 0) {
printf("Heap underflow\n");
return -1;
}

int root = heap->data[0];

heap->data[0] = heap->data[heap->size - 1];
heap->size--;
heapifyDown(heap, 0);

return root;

}
Get Min:

int getMin(MinHeap *heap) {

if(heap->size == 0) return -1;
return heap->data[0];
}

Build Heap
void buildHeap(MinHeap *heap, int arr[], int n) {
heap->size = n;
for(int i = 0; i < n; i++) {
heap->data[i] = arr[i];
}

// Heapify from last non-leaf node

for(int i = (n / 2) - 1; i >= 0; i--) {
heapifyDown(heap, i);
}

Heap Sort
void heapSort(int arr[], int n) {
MinHeap heap;
buildHeap(&heap, arr, n);
 for(int i = n - 1; i >= 0; i--) {
arr[i] = extractMin(&heap);
}

// Reverse for ascending order

for(int i = 0; i < n / 2; i++) {
swap(&arr[i], &arr[n - 1 - i]);
}

Priority Queue Applications

Kth Largest Element:

int findKthLargest(int arr[], int n, int k) {

MinHeap heap;
initMinHeap(&heap);

// Maintain heap of size k

for(int i = 0; i < n; i++) {
if(heap.size < k) {
insert(&heap, arr[i]);
} else if(arr[i] > getMin(&heap)) {
extractMin(&heap);
insert(&heap, arr[i]);
}
}

return getMin(&heap);

Merge K Sorted Arrays:

typedef struct {
int value;
int arrayIndex;
int elementIndex;
} HeapNode;
typedef struct {
HeapNode data[MAX_SIZE];
int size;
} MinHeapNode;
void mergeKArrays(int **arrays, int k, int n, int result[]) {
MinHeapNode heap;
heap.size = 0;

// Insert first element from each array

for(int i = 0; i < k; i++) {
HeapNode node;
node.value = arrays[i][0];
node.arrayIndex = i;
node.elementIndex = 0;
// Insert into heap (implementation simplified)
}

int resultIdx = 0;

while(heap.size > 0) {
// Extract min (implementation simplified)
// Insert next element from same array
resultIdx++;
}

}
Median of Stream:

typedef struct {
MinHeap minHeap; // Larger half
MinHeap maxHeap; // Smaller half (negate values)
} MedianFinder;
void addNum(MedianFinder *mf, int num) {
if(mf->maxHeap.size == 0 || num < -getMin(&mf->maxHeap)) {
insert(&mf->maxHeap, -num); // Negate for max heap behavior
} else {
insert(&mf->minHeap, num);
}

// Balance heaps
if(mf->maxHeap.size > mf->minHeap.size + 1) {
int val = -extractMin(&mf->maxHeap);
 insert(&mf->minHeap, val);
} else if(mf->minHeap.size > mf->maxHeap.size) {
int val = extractMin(&mf->minHeap);
insert(&mf->maxHeap, -val);
}

double findMedian(MedianFinder *mf) {

if(mf->maxHeap.size > mf->minHeap.size) {
return -getMin(&mf->maxHeap);
}
return (-getMin(&mf->maxHeap) + getMin(&mf->minHeap)) / 2.0;
}

Top K Frequent Elements

typedef struct {
int num;
int freq;
} FreqNode;
void topKFrequent(int nums[], int n, int k, int result[]) {
// Count frequencies using hash map
HashTable ht;
initHashTable(&ht);

for(int i = 0; i < n; i++) {

int freq = search(&ht, nums[i]);
if(freq == -1) {
insert(&ht, nums[i], 1);
} else {
insert(&ht, nums[i], freq + 1);
}
}

// Use min heap of size k

MinHeap heap;
initMinHeap(&heap);

// Implementation for frequency-based heap insertion

// Return top k elements
}

Practice Problems
1. Find median from data stream
2. Reorganize string (no adjacent duplicates)
3. Meeting rooms II (minimum meeting rooms)
4. Sliding window median
5. Kth smallest element in sorted matrix
6. Find K pairs with smallest sums
7. Ugly number II
8. Task scheduler

References
[1] Halim, S., & Halim, F. (2013). Competitive Programming 3. Lulu Press.
[2] Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction to Algorithms
(4th ed.). MIT Press.

[3] Laaksonen, A. (2018). Competitive Programmer's Handbook. https://cses.fi/book.pdf

[4] GeeksforGeeks. (2021). Searching Algorithms. https://www.geeksforgeeks.org/searching-a
lgorithms/
[5] DesignGurus. (2025). Advanced Data Structure Patterns for Competitive Coding. https://w
ww.designgurus.io/blog/advanced-data-structure-patterns-for-competitive-coding

[6] Skiena, S. S. (2020). The Algorithm Design Manual (3rd ed.). Springer.
[7] Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed.). Addison-Wesley.
[8] Bhargava, A. Y. (2016). Grokking Algorithms. Manning Publications.

[9] Karumanchi, N. (2016). Data Structures and Algorithms Made Easy. CareerMonk
Publications.
[10] Goodrich, M. T., Tamassia, R., & Goldwasser, M. H. (2013). Data Structures and
Algorithms in Python. Wiley.
[11] Weiss, M. A. (2014). Data Structures and Algorithm Analysis in C (2nd ed.). Pearson.

[12] Knuth, D. E. (1998). The Art of Computer Programming, Volume 3: Sorting and Searching
(2nd ed.). Addison-Wesley.
[13] Aho, A. V., & Ullman, J. D. (1992). Foundations of Computer Science. W. H. Freeman.
[14] Manber, U. (1989). Introduction to Algorithms: A Creative Approach. Addison-Wesley.

[15] Williams, J. W. J. (1964). Algorithm 232: Heapsort. Communications of the ACM, 7(6), 347-
348.
Chapter 13: Object-Oriented Programming (OOP)
Concepts
Introduction to OOP
Definition: Object-Oriented Programming is a programming paradigm that organizes
software design around data (objects) rather than functions and logic. It bundles data and
methods that operate on that data within a single unit called a class[16].
Why OOP Matters in Competitive Programming:
While competitive programming traditionally focuses on procedural approaches in C,
understanding OOP concepts is valuable for:

• Interview preparation (C++ STL, Java Collections)

• Complex data structure implementation
• Code organization and reusability
• Modern contest platforms supporting C++ and Python

The Four Pillars of OOP

1. Encapsulation
Definition: Bundling data (attributes) and methods (functions) that operate on the data
into a single unit (class), while restricting direct access to some components[17].
Benefits:
• Data hiding and protection
• Controlled access via getter/setter methods
• Internal implementation can change without affecting external code
• Reduces complexity

C Implementation (Using Structs and Functions):

// Simulating encapsulation in C
typedef struct {
int balance; // Private-like data
char accountNumber[20];
} BankAccount;
// "Constructor"
void initAccount(BankAccount *acc, const char *accNum, int initialBalance) {
strcpy(acc->accountNumber, accNum);
acc->balance = initialBalance;
}

// Getter
int getBalance(BankAccount *acc) {
return acc->balance;
}
// Setter with validation
void deposit(BankAccount *acc, int amount) {
if(amount > 0) {
acc->balance += amount;
}
}
void withdraw(BankAccount *acc, int amount) {
if(amount > 0 && amount <= acc->balance) {
acc->balance -= amount;
}
}

Python Implementation:
class BankAccount:
def init(self, account_number, initial_balance):
self.__balance = initial_balance # Private attribute
self.__account_number = account_number

def get_balance(self):
return self.__balance

def deposit(self, amount):

if amount > 0:
self.__balance += amount
return True
return False

def withdraw(self, amount):

if 0 < amount <= self.__balance:
self.__balance -= amount
return True
return False

Usage
account = BankAccount("ACC001", 1000)
account.deposit(500)
print(account.get_balance()) # 1500
2. Inheritance
Definition: Mechanism where a new class (derived/child) acquires properties and
behaviors of an existing class (base/parent), enabling code reuse and hierarchical
relationships[18].
Benefits:
• Code reusability
• Establishes hierarchical classification
• Polymorphism support
• Extensibility

C Implementation (Using Composition):

// Base "class"
typedef struct {
char name[50];
int age;
} Person;
void initPerson(Person *p, const char *name, int age) {
strcpy(p->name, name);
p->age = age;
}

void displayPerson(Person *p) {

printf("Name: %s, Age: %d\n", p->name, p->age);
}
// Derived "class" - contains Person
typedef struct {
Person person; // Composition
int studentId;
float gpa;
} Student;
void initStudent(Student *s, const char *name, int age, int id, float gpa) {
initPerson(&s->person, name, age);
s->studentId = id;
s->gpa = gpa;
}

void displayStudent(Student *s) {

displayPerson(&s->person);
printf("Student ID: %d, GPA: %.2f\n", s->studentId, s->gpa);
}
Python Implementation:
class Person:
def init(self, name, age):
self.name = name
self.age = age
 def display(self):
print(f"Name: {self.name}, Age: {self.age}")

class Student(Person): # Inheritance

def init(self, name, age, student_id, gpa):
super().init(name, age) # Call parent constructor
self.student_id = student_id
self.gpa = gpa

def display(self):
super().display()
print(f"Student ID: {self.student_id}, GPA: {self.gpa}")

class Teacher(Person):
def init(self, name, age, subject, salary):
super().init(name, age)
self.subject = subject
self.salary = salary

def display(self):
super().display()
print(f"Subject: {self.subject}, Salary: ${self.salary}")

Usage
student = Student("Alice", 20, 101, 3.8)
teacher = Teacher("Dr. Smith", 45, "Mathematics", 60000)
student.display()
teacher.display()
Types of Inheritance:

Type Description
Single One parent, one child
Multiple parents, one child (Python supports, C++
Multiple
supports)
Multilevel Chain of inheritance (A → B → C)
Hierarchical One parent, multiple children
Hybrid Combination of multiple types

Table 4: Types of inheritance

3. Polymorphism
Definition: Ability of objects to take multiple forms. Same interface, different
implementations. "Many forms"[19].
Types:
• Compile-time (Static): Function overloading, operator overloading
• Runtime (Dynamic): Method overriding via virtual functions

Benefits:
• Flexibility and extensibility
• Code reusability
• Loose coupling
• Interface-based programming
C Implementation (Function Pointers):

typedef struct Shape Shape;

// Function pointer for polymorphic behavior
typedef double (AreaFunction)(Shape);
struct Shape {
AreaFunction calculateArea;
void *data; // Pointer to specific shape data
};

// Circle data
typedef struct {
double radius;
} Circle;
double circleArea(Shape *shape) {
Circle circle = (Circle)shape->data;
return 3.14159 * circle->radius * circle->radius;
}
// Rectangle data
typedef struct {
double width;
double height;
} Rectangle;

double rectangleArea(Shape *shape) {

Rectangle rect = (Rectangle)shape->data;
return rect->width * rect->height;
}
// Usage
void printArea(Shape *shape) {
printf("Area: %.2f\n", shape->calculateArea(shape));
}
int main() {
Circle c = {5.0};
Shape circleShape = {circleArea, &c};

Rectangle r = {4.0, 6.0};

Shape rectShape = {rectangleArea, &r};

printArea(&circleShape); // Polymorphic call

printArea(&rectShape); // Polymorphic call

return 0;

}
Python Implementation:
from abc import ABC, abstractmethod
import math

class Shape(ABC): # Abstract base class

@abstractmethod
def area(self):
pass

@abstractmethod
def perimeter(self):
pass

class Circle(Shape):
def init(self, radius):
self.radius = radius

def area(self):
return math.pi * self.radius ** 2

def perimeter(self):
return 2 * math.pi * self.radius

class Rectangle(Shape):
def init(self, width, height):
self.width = width
self.height = height
 def area(self):
return self.width * self.height

def perimeter(self):
return 2 * (self.width + self.height)

class Triangle(Shape):
def init(self, a, b, c):
self.a = a
self.b = b
self.c = c

def area(self):
s = (self.a + self.b + self.c) / 2
return math.sqrt(s * (s - self.a) * (s - self.b) * (s - self.c))

def perimeter(self):
return self.a + self.b + self.c

Polymorphic function
def print_shape_info(shape):
print(f"{shape.class.name}:")
print(f" Area: {shape.area():.2f}")
print(f" Perimeter: {shape.perimeter():.2f}")

Usage
shapes = [
Circle(5),
Rectangle(4, 6),
Triangle(3, 4, 5)
]
for shape in shapes:
print_shape_info(shape) # Polymorphism in action

Method Overloading Example (Python):

class Calculator:
def add(self, a, b, c=0): # Default parameter for overloading effect
return a + b + c
 def multiply(self, *args): # Variable arguments
result = 1
for num in args:
result *= num
return result

calc = Calculator()
print(calc.add(2, 3)) # 5
print(calc.add(2, 3, 4)) # 9
print(calc.multiply(2, 3)) # 6
print(calc.multiply(2, 3, 4, 5)) # 120

4. Abstraction
Definition: Hiding complex implementation details and showing only essential features.
Focuses on WHAT an object does rather than HOW it does it[20].

Benefits:
• Reduces complexity
• Improves code maintainability
• Enhances security
• Allows focus on high-level operations
C Implementation (Header Files and Opaque Pointers):

// stack.h - Abstract interface

#ifndef STACK_H
#define STACK_H
typedef struct Stack Stack; // Opaque pointer
Stack* createStack(int capacity);
void push(Stack *s, int value);
int pop(Stack *s);
int peek(Stack *s);
int isEmpty(Stack *s);
void destroyStack(Stack *s);

#endif
// stack.c - Hidden implementation
struct Stack {
int *data;
int top;
int capacity;
};
Stack* createStack(int capacity) {
Stack s = (Stack)malloc(sizeof(Stack));
s->data = (int*)malloc(capacity * sizeof(int));
s->top = -1;
s->capacity = capacity;
return s;
}
void push(Stack *s, int value) {
if(s->top < s->capacity - 1) {
s->data[++(s->top)] = value;
}
}

int pop(Stack *s) {

if(s->top >= 0) {
return s->data[(s->top)--];
}
return -1;
}
// Users only see the interface, not implementation details
Python Implementation:

from abc import ABC, abstractmethod

class Database(ABC): # Abstract class
@abstractmethod
def connect(self):
pass

@abstractmethod
def execute_query(self, query):
pass

@abstractmethod
def close(self):
pass

class MySQLDatabase(Database):
def connect(self):
print("Connecting to MySQL database...")
# Complex connection logic hidden

def execute_query(self, query):

print(f"Executing MySQL query: {query}")
# Complex query execution logic hidden
return "MySQL results"
 def close(self):
print("Closing MySQL connection...")

class MongoDatabase(Database):
def connect(self):
print("Connecting to MongoDB...")

def execute_query(self, query):

print(f"Executing MongoDB query: {query}")
return "MongoDB results"

def close(self):
print("Closing MongoDB connection...")

User code - doesn't need to know

implementation details
def perform_database_operation(db: Database):
db.connect()
results = db.execute_query("SELECT * FROM users")
print(f"Results: {results}")
db.close()

Usage
mysql_db = MySQLDatabase()
mongo_db = MongoDatabase()
perform_database_operation(mysql_db)
perform_database_operation(mongo_db)

OOP Concepts Comparison Table

 Concept C Support Python Support
Partial (structs +
Encapsulation Full (classes with __private)
functions)
Inheritance Composition only Full (single and multiple)
Full (duck typing +
Polymorphism Function pointers
inheritance)
Header files + opaque
Abstraction Full (ABC module)
types

Table 5: OOP support in C vs Python

Advanced OOP Concepts

Constructor and Destructor
Python:

class Resource:
def init(self, name): # Constructor
self.name = name
print(f"Resource {self.name} acquired")

def __del__(self): # Destructor

print(f"Resource {self.name} released")

Class vs Instance Variables

Python:
class Counter:
total_count = 0 # Class variable (shared)

def __init__(self):
self.count = 0 # Instance variable (unique per object)
Counter.total_count += 1

def increment(self):
self.count += 1

c1 = Counter()
c2 = Counter()
c1.increment()
print(f"c1 count: {c1.count}") # 1
print(f"c2 count: {c2.count}") # 0
print(f"Total counters: {Counter.total_count}") # 2

Static Methods and Class Methods

Python:
class MathUtils:
@staticmethod
def add(a, b): # No access to instance or class
return a + b

@classmethod
def from_string(cls, string): # Access to class
values = string.split(',')
return cls(values)

print(MathUtils.add(5, 3)) # 8

OOP Design Patterns for Competitive Programming

Singleton Pattern
Python:
class Logger:
_instance = None

def __new__(cls):
if cls._instance is None:
cls._instance = super().__new__(cls)
cls._instance.logs = []
return cls._instance

def log(self, message):

self.logs.append(message)

logger1 = Logger()
logger2 = Logger()
logger1.log("Event 1")
logger2.log("Event 2")
print(logger1.logs) # ['Event 1', 'Event 2']
print(logger1 is logger2) # True
Factory Pattern
Python:
class ShapeFactory:
@staticmethod
def create_shape(shape_type, *args):
if shape_type == "circle":
return Circle(args[0])
elif shape_type == "rectangle":
return Rectangle(args[0], args[1])
elif shape_type == "triangle":
return Triangle(args[0], args[1], args[2])
return None
shape = ShapeFactory.create_shape("circle", 5)

OOP in Competitive Programming

When to Use OOP Concepts:

• Complex data structure implementation (LRU Cache, Trie)

• Graph algorithms with custom node/edge objects
• Simulation problems (game states, entities)
• Multiple test cases with state management
• Interview problems requiring design
Python Data Structures with OOP:
class Node:
def init(self, data):
self.data = data
self.next = None

class LinkedList:
def init(self):
self.head = None

def insert(self, data):

new_node = Node(data)
new_node.next = self.head
self.head = new_node

def display(self):
current = self.head
while current:
print(current.data, end=" -> ")
 current = current.next
print("None")

class TreeNode:
def init(self, val=0):
self.val = val
self.left = None
self.right = None

class BinaryTree:
def init(self):
self.root = None

def inorder(self, node):

if node:
self.inorder(node.left)
print(node.val, end=" ")
self.inorder(node.right)

Practice Problems - OOP

1. Design a parking lot system with different vehicle types
2. Implement LRU Cache using OOP principles
3. Create a library management system
4. Design a deck of cards with shuffle functionality
5. Implement a file system with folders and files
6. Create a restaurant ordering system
7. Design a banking system with accounts and transactions
8. Implement a social media friend recommendation system

Chapter 14: Python-Specific Data Structures

Python Built-in Collections
Python provides powerful built-in data structures optimized for competitive
programming[21].

Lists (Dynamic Arrays)

Operations:
Creation
arr = [1, 2, 3, 4, 5]
arr = list(range(1, 6))

Append - O(1) amortized

arr.append(6)

Insert - O(n)
arr.insert(0, 0)

Remove - O(n)
arr.remove(3)

Pop - O(1) from end, O(n) from beginning

last = arr.pop()
first = arr.pop(0)

Slicing - O(k) where k is slice size

subset = arr[1:4]
reversed_arr = arr[::-1]

List comprehension
squares = [x**2 for x in range(10)]
evens = [x for x in range(20) if x % 2 == 0]

Sorting - O(n log n)

arr.sort() # In-place
sorted_arr = sorted(arr) # Returns new list
arr.sort(reverse=True)

Tuples (Immutable Sequences)

Creation
point = (3, 4)
single = (5,) # Note comma for single element

Unpacking
x, y = point

Named tuples
from collections import namedtuple
Point = namedtuple('Point', ['x', 'y'])
p = Point(3, 4)
print(p.x, p.y)

Sets (Hash-based)

Creation
s = {1, 2, 3, 4, 5}
s = set([1, 2, 2, 3, 3]) # {1, 2, 3}

Operations - All O(1) average

s.add(6)
s.remove(3)
s.discard(10) # No error if not present

Set operations
a = {1, 2, 3}
b = {3, 4, 5}
union = a | b # {1, 2, 3, 4, 5}
intersection = a & b # {3}
difference = a - b # {1, 2}
symmetric_diff = a ^ b # {1, 2, 4, 5}

Dictionaries (Hash Maps)

Creation
d = {'a': 1, 'b': 2, 'c': 3}
d = dict(a=1, b=2, c=3)

Access - O(1) average

value = d['a']
value = d.get('a', 0) # Default value

Insert/Update - O(1)
d['d'] = 4

Delete - O(1)
del d['a']
value = d.pop('b', None)

Iteration
for key in d:
print(key, d[key])
for key, value in d.items():
print(key, value)

Dictionary comprehension
squares = {x: x**2 for x in range(5)}

Collections Module
Counter (Frequency Counter)
from collections import Counter

Count frequency
arr = [1, 2, 2, 3, 3, 3, 4, 4, 4, 4]
counter = Counter(arr)
print(counter) # Counter({4: 4, 3: 3, 2: 2, 1: 1})
Most common
print(counter.most_common(2)) # [(4, 4), (3, 3)]

Operations
c1 = Counter(['a', 'b', 'c', 'a'])
c2 = Counter(['a', 'b', 'd'])
print(c1 + c2) # Counter({'a': 3, 'b': 2, 'c': 1, 'd': 1})

defaultdict (Auto-initializing Dict)

from collections import defaultdict

List as default
graph = defaultdict(list)
graph[1].append(2)
graph[1].append(3)

Int as default (for counting)

freq = defaultdict(int)
for char in "hello":
freq[char] += 1

Set as default
groups = defaultdict(set)
groups['vowels'].add('a')

deque (Double-ended Queue)

from collections import deque

Creation
dq = deque([1, 2, 3])

Operations - All O(1)

dq.append(4) # Add to right
dq.appendleft(0) # Add to left
dq.pop() # Remove from right
dq.popleft() # Remove from left
Rotation
dq.rotate(2) # Rotate right
dq.rotate(-1) # Rotate left

Use case: Sliding window

def max_sliding_window(arr, k):
dq = deque()
result = []

for i in range(len(arr)):
# Remove elements outside window
while dq and dq[0] <= i - k:
dq.popleft()

# Remove smaller elements

while dq and arr[dq[-1]] <= arr[i]:
dq.pop()

dq.append(i)

if i >= k - 1:
result.append(arr[dq[0]])

return result

heapq (Priority Queue)

import heapq

Min heap (default)

heap = []
heapq.heappush(heap, 3)
heapq.heappush(heap, 1)
heapq.heappush(heap, 2)
min_val = heapq.heappop(heap) # 1
Heapify existing list
arr = [3, 1, 4, 1, 5, 9, 2, 6]
heapq.heapify(arr) # O(n)

Max heap (negate values)

max_heap = []
heapq.heappush(max_heap, -3)
heapq.heappush(max_heap, -1)
max_val = -heapq.heappop(max_heap) # 3

K largest elements
k_largest = heapq.nlargest(3, arr)

K smallest elements
k_smallest = heapq.nsmallest(3, arr)

bisect (Binary Search)

import bisect

Sorted list
arr = [1, 3, 5, 7, 9]

Find insertion point

pos = bisect.bisect_left(arr, 6) # 3
pos = bisect.bisect_right(arr, 5) # 3

Insert maintaining sorted order

bisect.insort(arr, 6)

Binary search implementation

def binary_search(arr, x):
i = bisect.bisect_left(arr, x)
if i != len(arr) and arr[i] == x:
return i
return -1
Python Itertools for Combinations
import itertools

Permutations
perms = list(itertools.permutations([1, 2, 3]))

Combinations
combs = list(itertools.combinations([1, 2, 3, 4], 2))

Combinations with replacement

combs_rep = list(itertools.combinations_with_replacement([1, 2], 2))

Product (Cartesian product)

prod = list(itertools.product([1, 2], ['a', 'b']))

Chain (flatten)
chained = list(itertools.chain([1, 2], [3, 4], [5]))

Fast I/O in Python

import sys

Fast input
def fast_input():
return sys.stdin.readline().strip()
def fast_int():
return int(sys.stdin.readline())

def fast_ints():
return map(int, sys.stdin.readline().split())

Fast output
def fast_print(*args):
sys.stdout.write(' '.join(map(str, args)) + '\n')
Usage
n = fast_int()
arr = list(fast_ints())

Python vs C: Performance Comparison

Operation C Time Python Time
Array access O(1) O(1)
Hash table lookup O(1) O(1) (dict)
Sorting O(n log n) O(n log n) (Timsort)
String concatenation O(n) O(n) but slower
I/O operations Very fast Slower (use sys)

Table 6: Performance comparison

Python Optimization Tips:

1. Use built-in functions (sum, max, min) - implemented in C
2. List comprehensions faster than loops
3. Use sets for membership testing
4. Avoid global variables in functions
5. Use local variable caching: append = list.append
6. Use sys.stdin for fast input
7. Use generators for memory efficiency

Complete Python Template for Contests

import sys
from collections import defaultdict, deque, Counter
import heapq
import bisect
from typing import List, Set, Dict, Tuple
def solve():
# Fast input
input = sys.stdin.readline

# Read input
n = int(input())
arr = list(map(int, input().split()))

# Your solution here

result = 0
 # Fast output
print(result)

if name == "main":
t = int(input()) # Number of test cases
for _ in range(t):
solve()

Chapter 15: Advanced Programming Concepts for DSA

C Programming Language Fundamentals
Data Types and Variables
Basic Data Types:

Type Size Range

char 1 byte -128 to 127
unsigned
1 byte 0 to 255
char
2
short -32,768 to 32,767
bytes
4
int -2,147,483,648 to 2,147,483,647
bytes
8 -9,223,372,036,854,775,808 to
long long
bytes 9,223,372,036,854,775,807
4
float 3.4E-38 to 3.4E+38
bytes
8
double 1.7E-308 to 1.7E+308
bytes

Table 7: C data types

Variable Declaration and Initialization:

// Declaration
int x;
float pi;
char grade;
// Initialization
int count = 0;
double price = 99.99;
char letter = 'A';
// Multiple declarations
int a = 1, b = 2, c = 3;
// Constants
const int MAX_SIZE = 1000;
#define MOD 1000000007

Operators
Arithmetic Operators:

int a = 10, b = 3;
int sum = a + b; // 13
int diff = a - b; // 7
int prod = a * b; // 30
int quot = a / b; // 3 (integer division)
int rem = a % b; // 1 (modulo)
Relational Operators:
if(a == b) // Equal to
if(a != b) // Not equal to
if(a > b) // Greater than
if(a < b) // Less than
if(a >= b) // Greater than or equal to
if(a <= b) // Less than or equal to

Logical Operators:
if(a > 0 && b > 0) // AND
if(a > 0 || b > 0) // OR
if(!(a > 0)) // NOT
Bitwise Operators:

int x = 5; // 0101 in binary

int y = 3; // 0011 in binary
int and = x & y; // 0001 = 1
int or = x | y; // 0111 = 7
int xor = x ^ y; // 0110 = 6
int not = ~x; // 1010 = -6 (two's complement)
int lshift = x << 1; // 1010 = 10
int rshift = x >> 1; // 0010 = 2

Control Structures
If-Else Statements:
if(condition) {
// code
} else if(another_condition) {
// code
} else {
// code
}
// Ternary operator
int max = (a > b) ? a : b;

Switch Statement:
switch(choice) {
case 1:
printf("Option 1\n");
break;
case 2:
printf("Option 2\n");
break;
default:
printf("Invalid option\n");
}
Loops:

// For loop
for(int i = 0; i < n; i++) {
printf("%d ", i);
}
// While loop
int i = 0;
while(i < n) {
printf("%d ", i);
i++;
}
// Do-while loop
int j = 0;
do {
printf("%d ", j);
j++;
} while(j < n);

// Break and continue

for(int i = 0; i < 10; i++) {
if(i == 5) continue; // Skip 5
if(i == 8) break; // Exit at 8
printf("%d ", i);
}
Functions
Function Declaration and Definition:
// Function prototype
int add(int a, int b);
void printArray(int arr[], int n);
// Function definition
int add(int a, int b) {
return a + b;
}

void printArray(int arr[], int n) {

for(int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
// Recursive function
int factorial(int n) {
if(n <= 1) return 1;
return n * factorial(n - 1);
}
// Pass by value
void increment(int x) {
x++; // Original not modified
}

// Pass by reference (using pointers)

void incrementRef(int *x) {
(*x)++; // Original modified
}

Pointers
Pointer Basics:
int x = 10;
int *ptr = &x; // ptr stores address of x
printf("Value: %d\n", *ptr); // Dereference: 10
printf("Address: %p\n", ptr); // Address of x
printf("Pointer address: %p\n", &ptr); // Address of ptr

// Pointer arithmetic
int arr[5] = {1, 2, 3, 4, 5};
int *p = arr;
printf("%d\n", *(p + 2)); // 3
p++;
printf("%d\n", *p); // 2
Pointers and Arrays:
int arr[5] = {1, 2, 3, 4, 5};
int *ptr = arr; // arr decays to pointer

// These are equivalent

arr[i] == *(arr + i)
ptr[i] == *(ptr + i)
Pointers and Functions:
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}

int main() {
int x = 5, y = 10;
swap(&x, &y); // Pass addresses
printf("x=%d, y=%d\n", x, y); // x=10, y=5
return 0;
}
Function Pointers:
int add(int a, int b) { return a + b; }
int subtract(int a, int b) { return a - b; }

int main() {
int (*operation)(int, int); // Function pointer

operation = add;
printf("%d\n", operation(5, 3)); // 8

operation = subtract;
printf("%d\n", operation(5, 3)); // 2

return 0;

Structures
Structure Definition:

struct Point {
int x;
int y;
};
// Declaration
struct Point p1;
p1.x = 10;
p1.y = 20;
// Initialization
struct Point p2 = {30, 40};

// Typedef
typedef struct {
int x;
int y;
} Point;
Point p3 = {50, 60};
Structures and Pointers:

Point p = {10, 20};

Point *ptr = &p;
// Access members
printf("%d %d\n", ptr->x, ptr->y); // Arrow operator
printf("%d %d\n", (*ptr).x, (*ptr).y); // Equivalent
Structures and Functions:

void printPoint(Point p) {
printf("(%d, %d)\n", p.x, p.y);
}
void movePoint(Point *p, int dx, int dy) {
p->x += dx;
p->y += dy;
}

File I/O
Reading from File:
FILE *fp = fopen("input.txt", "r");
if(fp == NULL) {
printf("Error opening file\n");
return 1;
}

int n;
fscanf(fp, "%d", &n);
int arr[n];
for(int i = 0; i < n; i++) {
fscanf(fp, "%d", &arr[i]);
}
fclose(fp);
Writing to File:
FILE *fp = fopen("output.txt", "w");
fprintf(fp, "Result: %d\n", result);
fclose(fp);

Python Programming Language Fundamentals

Data Types and Variables
Basic Data Types:

Numbers
integer = 42
floating = 3.14159
complex_num = 3 + 4j

Strings
string = "Hello, World!"
multi_line = """This is a
multi-line string"""

Boolean
is_valid = True
is_false = False

None type
nothing = None
Type Conversion:

Implicit
result = 10 + 3.5 # 13.5 (int + float = float)

Explicit
x = int(3.7) # 3
y = float(5) # 5.0
z = str(100) # "100"
w = bool(0) # False
Python Operators
Arithmetic:
a, b = 10, 3
print(a + b) # 13
print(a - b) # 7
print(a * b) # 30
print(a / b) # 3.333... (float division)
print(a // b) # 3 (floor division)
print(a % b) # 1 (modulo)
print(a ** b) # 1000 (exponentiation)
Comparison:

print(a == b) # False
print(a != b) # True
print(a > b) # True
print(a < b) # False
print(a >= b) # True
print(a <= b) # False
Logical:
print(True and False) # False
print(True or False) # True
print(not True) # False

Membership:
print(5 in [1, 2, 3, 4, 5]) # True
print('a' not in 'hello') # True
Identity:

a = [1, 2, 3]
b = [1, 2, 3]
c =a
print(a is c) # True (same object)
print(a is b) # False (different objects)
print(a == b) # True (same value)

Control Flow
If-Elif-Else:
score = 85

if score >= 90:

grade = 'A'
elif score >= 80:
grade = 'B'
elif score >= 70:
grade = 'C'
else:
grade = 'F'

Ternary
max_val = a if a > b else b
For Loops:

Range
for i in range(5):
print(i) # 0 1 2 3 4
for i in range(1, 6):
print(i) # 1 2 3 4 5
for i in range(0, 10, 2):
print(i) # 0 2 4 6 8

Iterate over list

fruits = ['apple', 'banana', 'orange']
for fruit in fruits:
print(fruit)

Enumerate (index + value)

for idx, fruit in enumerate(fruits):
print(f"{idx}: {fruit}")
While Loops:
count = 0
while count < 5:
print(count)
count += 1

Break and continue

for i in range(10):
if i == 3:
continue # Skip 3
if i == 7:
break # Stop at 7
print(i)
Functions
Function Definition:
def greet(name):
return f"Hello, {name}!"
def add(a, b):
return a + b

Multiple return values

def get_stats(numbers):
return min(numbers), max(numbers), sum(numbers)
min_val, max_val, total = get_stats([1, 2, 3, 4, 5])

Default Arguments:
def power(base, exponent=2):
return base ** exponent
print(power(5)) # 25 (default exponent=2)
print(power(5, 3)) # 125

Keyword Arguments:
def describe_pet(animal, name, age):
print(f"{name} is a {age}-year-old {animal}")
describe_pet(animal='dog', name='Buddy', age=5)
describe_pet(name='Whiskers', age=3, animal='cat')

Variable Arguments:
def sum_all(*args):
return sum(args)
print(sum_all(1, 2, 3, 4, 5)) # 15

def print_info(**kwargs):
for key, value in kwargs.items():
print(f"{key}: {value}")
print_info(name='Alice', age=25, city='NYC')
Lambda Functions:

square = lambda x: x ** 2
print(square(5)) # 25
With map, filter, reduce
numbers = [1, 2, 3, 4, 5]
squares = list(map(lambda x: x**2, numbers))
evens = list(filter(lambda x: x % 2 == 0, numbers))

from functools import reduce

product = reduce(lambda x, y: x * y, numbers) # 120

List Comprehensions
Basic Comprehension:

Traditional
squares = []
for i in range(10):
squares.append(i**2)

List comprehension
squares = [i**2 for i in range(10)]

With condition
evens = [x for x in range(20) if x % 2 == 0]

With if-else
labels = ['even' if x % 2 == 0 else 'odd' for x in range(10)]

Nested Comprehensions:

2D matrix
matrix = [[i*j for j in range(5)] for i in range(5)]

Flatten matrix
flat = [num for row in matrix for num in row]
Dictionary Comprehension:

squares_dict = {x: x**2 for x in range(5)}

{0: 0, 1: 1, 2: 4, 3: 9, 4: 16}
Set Comprehension:

unique_squares = {x**2 for x in [1, 2, 2, 3, 3, 4]}

{1, 4, 9, 16}
String Methods
Common Operations:
s = "Hello, World!"

Length
print(len(s)) # 13

Case conversion
print(s.lower()) # hello, world!
print(s.upper()) # HELLO, WORLD!
print(s.title()) # Hello, World!

Strip whitespace
s2 = " hello "
print(s2.strip()) # "hello"

Split and join

words = s.split(', ') # ['Hello', 'World!']
joined = '-'.join(words) # 'Hello-World!'

Replace
print(s.replace('World', 'Python')) # Hello, Python!

Find and count

print(s.find('World')) # 7 (index)
print(s.count('l')) # 3
Check methods
print(s.startswith('Hello')) # True
print(s.endswith('!')) # True
print('123'.isdigit()) # True
print('abc'.isalpha()) # True

Exception Handling
Try-Except:

try:
result = 10 / 0
except ZeroDivisionError:
print("Cannot divide by zero!")
try:
num = int(input("Enter a number: "))
except ValueError:
print("Invalid input!")
Multiple Exceptions:

try:
# code that may raise exceptions
pass
except (TypeError, ValueError) as e:
print(f"Error: {e}")
except Exception as e:
print(f"Unexpected error: {e}")
finally:
print("This always executes")
Raising Exceptions:
def validate_age(age):
if age < 0:
raise ValueError("Age cannot be negative")
if age > 150:
raise ValueError("Age too high")
return True

Memory Management
Dynamic Memory Allocation in C
malloc() - Memory Allocation:
int arr = (int)malloc(n * sizeof(int));
if(arr == NULL) {
printf("Memory allocation failed\n");
exit(1);
}
// Use array
for(int i = 0; i < n; i++) {
arr[i] = i * 2;
}
// Free memory
free(arr);

calloc() - Contiguous Allocation (Initialized to 0):

int arr = (int)calloc(n, sizeof(int));
realloc() - Resize Allocation:

arr = (int*)realloc(arr, new_size * sizeof(int));

2D Array Dynamic Allocation:
// Method 1: Array of pointers
int matrix = (int)malloc(rows * sizeof(int*));
for(int i = 0; i < rows; i++) {
matrix[i] = (int*)malloc(cols * sizeof(int));
}

// Free
for(int i = 0; i < rows; i++) {
free(matrix[i]);
}
free(matrix);
// Method 2: Single allocation
int matrix = (int)malloc(rows * cols * sizeof(int));
// Access: matrix[i * cols + j]
free(matrix);
Common Memory Errors:

1. Memory leaks (forgetting to free)

2. Double free
3. Use after free
4. Buffer overflow
5. Uninitialized memory access

Memory Management in Python

Python handles memory automatically via:
• Reference counting
• Garbage collection
• Memory pooling
Memory profiling
import sys

arr = [1, 2, 3, 4, 5]
print(sys.getsizeof(arr)) # Size in bytes

Delete references
del arr

Garbage collection
import gc
gc.collect()

Bit Manipulation Techniques

Basic Operations:
// Set bit
n |= (1 << i)

// Clear bit
n &= ~(1 << i)
// Toggle bit
n ^= (1 << i)
// Check if bit is set
if(n & (1 << i))

// Count set bits (Brian Kernighan's algorithm)

int countSetBits(int n) {
int count = 0;
while(n) {
n &= (n - 1);
count++;
}
return count;
}
// Check if power of 2
bool isPowerOfTwo(int n) {
return n > 0 && (n & (n - 1)) == 0;
}
// Get rightmost set bit
int rightmostSetBit(int n) {
return n & -n;
}
// Clear all bits from LSB to i-th bit
n &= (-1 << (i + 1))
// Clear all bits from MSB to i-th bit
n &= ((1 << i) - 1)

Python Bit Manipulation:

Set bit
n |= (1 << i)

Count set bits (built-in)

count = bin(n).count('1')

XOR all elements (find unique)

def find_unique(arr):
result = 0
for num in arr:
result ^= num
return result

Modular Arithmetic
Essential for Competitive Programming:
#define MOD 1000000007
// Modular addition
int add(int a, int b) {
return ((a % MOD) + (b % MOD)) % MOD;
}

// Modular subtraction
int sub(int a, int b) {
return ((a % MOD) - (b % MOD) + MOD) % MOD;
}
// Modular multiplication
long long mul(long long a, long long b) {
return ((a % MOD) * (b % MOD)) % MOD;
}
// Modular exponentiation - O(log n)
long long power(long long base, long long exp, long long mod) {
long long result = 1;
base %= mod;
 while(exp > 0) {
if(exp & 1) {
result = (result * base) % mod;
}
base = (base * base) % mod;
exp >>= 1;
}

return result;

// Modular inverse (when mod is prime)

long long modInverse(long long a, long long mod) {
return power(a, mod - 2, mod); // Fermat's little theorem
}
// Modular division
long long divide(long long a, long long b, long long mod) {
return mul(a, modInverse(b, mod));
}
Python Implementation:

MOD = 10**9 + 7
def power(base, exp, mod=MOD):
result = 1
base %= mod
while exp > 0:
if exp & 1:
result = (result * base) % mod
base = (base * base) % mod
exp >>= 1
return result
def mod_inverse(a, mod=MOD):
return power(a, mod - 2, mod)

Prefix and Suffix Techniques

Prefix Sum:

void buildPrefix(int arr[], int prefix[], int n) {

prefix[0] = arr[0];
for(int i = 1; i < n; i++) {
prefix[i] = prefix[i-1] + arr[i];
}
}
// Range sum [l, r]
int rangeSum(int prefix[], int l, int r) {
if(l == 0) return prefix[r];
return prefix[r] - prefix[l-1];
}

Prefix XOR:
void buildPrefixXOR(int arr[], int prefixXOR[], int n) {
prefixXOR[0] = arr[0];
for(int i = 1; i < n; i++) {
prefixXOR[i] = prefixXOR[i-1] ^ arr[i];
}
}
2D Prefix Sum:

void build2DPrefix(int mat[][MAX], int prefix[][MAX], int rows, int cols) {

for(int i = 0; i < rows; i++) {
for(int j = 0; j < cols; j++) {
prefix[i][j] = mat[i][j];
if(i > 0) prefix[i][j] += prefix[i-1][j];
if(j > 0) prefix[i][j] += prefix[i][j-1];
if(i > 0 && j > 0) prefix[i][j] -= prefix[i-1][j-1];
}
}
}
int query2D(int prefix[][MAX], int r1, int c1, int r2, int c2) {
int sum = prefix[r2][c2];
if(r1 > 0) sum -= prefix[r1-1][c2];
if(c1 > 0) sum -= prefix[r2][c1-1];
if(r1 > 0 && c1 > 0) sum += prefix[r1-1][c1-1];
return sum;
}

Two Pointers Technique

Pattern 1: Opposite Ends:
bool twoSum(int arr[], int n, int target) {
int left = 0, right = n - 1;

while(left < right) {

int sum = arr[left] + arr[right];
if(sum == target) return true;
else if(sum < target) left++;
 else right--;
}
return false;

Pattern 2: Same Direction (Fast and Slow):

int removeDuplicates(int arr[], int n) {
if(n == 0) return 0;

int slow = 0;
for(int fast = 1; fast < n; fast++) {
if(arr[fast] != arr[slow]) {
slow++;
arr[slow] = arr[fast];
}
}

return slow + 1;

}
Python Two Pointers:
def three_sum(arr):
arr.sort()
result = []

for i in range(len(arr) - 2):

if i > 0 and arr[i] == arr[i-1]:
continue

left, right = i + 1, len(arr) - 1

while left < right:

total = arr[i] + arr[left] + arr[right]
if total == 0:
result.append([arr[i], arr[left], arr[right]])
while left < right and arr[left] == arr[left+1]:
left += 1
 while left < right and arr[right] == arr[right-1]:
right -= 1
left += 1
right -= 1
elif total < 0:
left += 1
else:
right -= 1

return result

Sliding Window Technique

Fixed Size Window:
int maxSumWindow(int arr[], int n, int k) {
int windowSum = 0;

// First window
for(int i = 0; i < k; i++) {
windowSum += arr[i];
}

int maxSum = windowSum;

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

return maxSum;

}
Variable Size Window:

int longestSubarrayWithSumK(int arr[], int n, int k) {

int left = 0, sum = 0, maxLen = 0;
 for(int right = 0; right < n; right++) {
sum += arr[right];

while(sum > k && left <= right) {

sum -= arr[left];
left++;
}

if(sum == k) {
maxLen = max(maxLen, right - left + 1);
}
}

return maxLen;

Python Sliding Window:

def longest_substring_without_repeating(s):
char_set = set()
left = 0
max_length = 0

for right in range(len(s)):

while s[right] in char_set:
char_set.remove(s[left])
left += 1

char_set.add(s[right])
max_length = max(max_length, right - left + 1)

return max_length

Practice Problems - Advanced Concepts

1. Subarray with given XOR
2. Count subarrays with sum divisible by K
3. Longest substring with at most K distinct characters
4. Minimum window substring
5. Maximum of all subarrays of size K
 6. Count pairs with XOR in range
7. Matrix block sum using 2D prefix
8. Container with most water (two pointers)

Chapter 16: Solutions to All Practice Problems

Chapter 3: Arrays and Strings - Solutions
Problem 1: Find Second Largest Element
C Solution:
int findSecondLargest(int arr[], int n) {
if(n < 2) return -1;

int first = INT_MIN, second = INT_MIN;

for(int i = 0; i < n; i++) {

if(arr[i] > first) {
second = first;
first = arr[i];
} else if(arr[i] > second && arr[i] != first) {
second = arr[i];
}
}

return (second == INT_MIN) ? -1 : second;

}
Python Solution:

def find_second_largest(arr):
if len(arr) < 2:
return -1

first = second = float('-inf')

for num in arr:

if num > first:
second = first
first = num
elif num > second and num != first:
 second = num

return second if second != float('-inf') else -1

Problem 2: Rotate Array by K Positions

C Solution:
void reverse(int arr[], int start, int end) {
while(start < end) {
int temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
start++;
end--;
}
}
void rotateArray(int arr[], int n, int k) {
k = k % n; // Handle k > n

reverse(arr, 0, n - 1); // Reverse entire array

reverse(arr, 0, k - 1); // Reverse first k elements
reverse(arr, k, n - 1); // Reverse remaining elements

}
Python Solution:

def rotate_array(arr, k):

n = len(arr)
k=k%n
return arr[-k:] + arr[:-k]

Alternative in-place
def rotate_array_inplace(arr, k):
def reverse(start, end):
while start < end:
arr[start], arr[end] = arr[end], arr[start]
start += 1
end -= 1

n = len(arr)
k=k%n
reverse(0, n - 1)
 reverse(0, k - 1)
reverse(k, n - 1)

Problem 3: Find Missing Number (1 to n)

C Solution:
int findMissing(int arr[], int n) {
int total = (n + 1) * (n + 2) / 2; // Sum of 1 to n+1
int sum = 0;

for(int i = 0; i < n; i++) {

sum += arr[i];
}

return total - sum;

}
// XOR approach
int findMissingXOR(int arr[], int n) {
int xor1 = 0, xor2 = 0;

for(int i = 0; i < n; i++) {

xor1 ^= arr[i];
}

for(int i = 1; i <= n + 1; i++) {

xor2 ^= i;
}

return xor1 ^ xor2;

}
Python Solution:
def find_missing(arr):
n = len(arr)
expected_sum = (n + 1) * (n + 2) // 2
actual_sum = sum(arr)
return expected_sum - actual_sum
XOR approach
def find_missing_xor(arr):
xor1 = xor2 = 0
n = len(arr)

for num in arr:

xor1 ^= num

for i in range(1, n + 2):

xor2 ^= i

return xor1 ^ xor2

Problem 4: Merge Two Sorted Arrays

C Solution:

void mergeSortedArrays(int arr1[], int n1, int arr2[], int n2, int result[]) {
int i = 0, j = 0, k = 0;

while(i < n1 && j < n2) {

if(arr1[i] <= arr2[j]) {
result[k++] = arr1[i++];
} else {
result[k++] = arr2[j++];
}
}

while(i < n1) {

result[k++] = arr1[i++];
}

while(j < n2) {

result[k++] = arr2[j++];
}

Python Solution:
def merge_sorted_arrays(arr1, arr2):
result = []
i=j=0

while i < len(arr1) and j < len(arr2):

if arr1[i] <= arr2[j]:
result.append(arr1[i])
i += 1
else:
result.append(arr2[j])
j += 1

result.extend(arr1[i:])
result.extend(arr2[j:])

return result

Problem 5: Count Frequency of Elements

C Solution:
void countFrequency(int arr[], int n) {
int visited[MAX_SIZE] = {0};

for(int i = 0; i < n; i++) {

if(visited[i] == 1) continue;

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

printf("%d appears %d times\n", arr[i], count);

}

}
Python Solution:
from collections import Counter
def count_frequency(arr):
freq = Counter(arr)
for num, count in freq.items():
print(f"{num} appears {count} times")

Manual approach
def count_frequency_manual(arr):
freq = {}
for num in arr:
freq[num] = freq.get(num, 0) + 1

for num, count in freq.items():

print(f"{num} appears {count} times")

Problem 6: Remove Duplicates from Sorted Array

C Solution:
int removeDuplicates(int arr[], int n) {
if(n == 0 || n == 1) return n;

int j = 0; // Index for unique elements

for(int i = 0; i < n - 1; i++) {

if(arr[i] != arr[i + 1]) {
arr[j++] = arr[i];
}
}

arr[j++] = arr[n - 1];

return j; // New size

}
Python Solution:

def remove_duplicates(arr):
if not arr:
return 0
 j=0
for i in range(len(arr) - 1):
if arr[i] != arr[i + 1]:
arr[j] = arr[i]
j += 1

arr[j] = arr[-1]
return j + 1

Problem 7: Longest Substring Without Repeating Characters

C Solution:
int longestUniqueSubstring(char str[]) {
int n = strlen(str);
int maxLen = 0;
int lastIndex[256]; // ASCII characters

for(int i = 0; i < 256; i++) {

lastIndex[i] = -1;
}

int start = 0;

for(int end = 0; end < n; end++) {

if(lastIndex[(int)str[end]] >= start) {
start = lastIndex[(int)str[end]] + 1;
}

lastIndex[(int)str[end]] = end;
maxLen = max(maxLen, end - start + 1);
}

return maxLen;

}
Python Solution:
def longest_unique_substring(s):
char_index = {}
max_len = 0
start = 0

for end in range(len(s)):

if s[end] in char_index and char_index[s[end]] >= start:
start = char_index[s[end]] + 1

char_index[s[end]] = end
max_len = max(max_len, end - start + 1)

return max_len

Problem 8: Check Anagrams

C Solution:
bool areAnagrams(char str1[], char str2[]) {
int count[256] = {0};

if(strlen(str1) != strlen(str2)) return false;

for(int i = 0; str1[i] && str2[i]; i++) {

count[(int)str1[i]]++;
count[(int)str2[i]]--;
}

for(int i = 0; i < 256; i++) {

if(count[i] != 0) return false;
}

return true;

}
Python Solution:

def are_anagrams(str1, str2):

return sorted(str1) == sorted(str2)
Using Counter
from collections import Counter
def are_anagrams_counter(str1, str2):
return Counter(str1) == Counter(str2)

Chapter 4: Searching - Solutions

Problem 1: Search in Rotated Sorted Array

C Solution:
int searchRotated(int arr[], int n, int target) {
int left = 0, right = n - 1;

while(left <= right) {

int mid = left + (right - left) / 2;

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

// Left half is sorted

if(arr[left] <= arr[mid]) {
if(target >= arr[left] && target < arr[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
}
// Right half is sorted
else {
if(target > arr[mid] && target <= arr[right]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
}

return -1;

}
Python Solution:
def search_rotated(arr, target):
left, right = 0, len(arr) - 1

while left <= right:

mid = (left + right) // 2

if arr[mid] == target:
return mid

if arr[left] <= arr[mid]:

if arr[left] <= target < arr[mid]:
right = mid - 1
else:
left = mid + 1
else:
if arr[mid] < target <= arr[right]:
left = mid + 1
else:
right = mid - 1

return -1

Problem 2: Find Peak Element

C Solution:

int findPeak(int arr[], int n) {

int left = 0, right = n - 1;

while(left < right) {

int mid = left + (right - left) / 2;

if(arr[mid] > arr[mid + 1]) {

right = mid;
} else {
left = mid + 1;
}
}
 return left;

Python Solution:
def find_peak(arr):
left, right = 0, len(arr) - 1

while left < right:

mid = (left + right) // 2

if arr[mid] > arr[mid + 1]:

right = mid
else:
left = mid + 1

return left

Problem 3: Search 2D Matrix

C Solution:
bool searchMatrix(int matrix[][MAX_COLS], int rows, int cols, int target) {
int left = 0, right = rows * cols - 1;

while(left <= right) {

int mid = left + (right - left) / 2;
int midVal = matrix[mid / cols][mid % cols];

if(midVal == target) return true;

else if(midVal < target) left = mid + 1;
else right = mid - 1;
}

return false;

}
Python Solution:
def search_matrix(matrix, target):
if not matrix or not matrix[0]:
return False

rows, cols = len(matrix), len(matrix[0])

left, right = 0, rows * cols - 1

while left <= right:

mid = (left + right) // 2
mid_val = matrix[mid // cols][mid % cols]

if mid_val == target:
return True
elif mid_val < target:
left = mid + 1
else:
right = mid - 1

return False

Flowcharts and Sequence Diagrams

Binary Search Flowchart

[Start]
|
[Initialize left=0, right=n-1]
|
[While left <= right]
|
[Calculate mid]
|
[arr[mid] == target?]
/ \
Yes No
| |

[Return] [target < arr[mid]?]

mid /
Yes No
||
[right=mid-1] [left=mid+1]
||
+-----+-----+
|
[Loop back]
|
[Return -1]
(Not found)
|
[End]

Merge Sort Sequence

Array: [38, 27, 43, 3, 9, 82, 10]
Level 0: [38, 27, 43, 3, 9, 82, 10]
|
+---------+---------+
||
Level 1: [38, 27, 43, 3] [9, 82, 10]
||
+---+---+ +---+---+
||||
Level 2:[38,27][43,3] [9,82] [10]
|||||||
Level 3:[38][27][43][3] [9] [82] [10]
|||||||
Merge: +---+ +---+ +---+ |
[27,38] [3,43] [9,82] [10]
||||
+-------+ +-----+
||
[3,27,38,43] [9,10,82]
||
+-----------------+
|
[3,9,10,27,38,43,82]

QuickSort Partition Process

Initial: [6, 3, 8, 1, 9, 2, 5] (pivot = 5)

Step 1: i=-1, j=0

[6, 3, 8, 1, 9, 2, 5]
^^
i pivot
Step 2: j=1, arr[j]=3 < pivot, swap(i+1, j)
[3, 6, 8, 1, 9, 2, 5]
^^^
i j pivot
Step 3: j=3, arr[j]=1 < pivot, swap(i+1, j)
[3, 1, 8, 6, 9, 2, 5]
^^^
i j pivot
Step 4: j=5, arr[j]=2 < pivot, swap(i+1, j)
[3, 1, 2, 6, 9, 8, 5]
^^^
i j pivot

Step 5: Swap pivot with i+1

[3, 1, 2, 5, 9, 8, 6]
^
pivot position
Recursively sort left and right subarrays

DFS vs BFS Tree Traversal

Tree:
1
/\
2 3
/\ \
4 5 6

DFS (Preorder):
Stack: [1] → Visit 1
Stack: [3,2] → Visit 2
Stack: [3,5,4] → Visit 4
Stack: [3,5] → Visit 5
Stack: [3] → Visit 3
Stack: [6] → Visit 6
Output: 1 2 4 5 3 6

BFS (Level Order):

Queue: [1] → Visit 1
Queue: [2,3] → Visit 2
Queue: [3,4,5] → Visit 3
Queue: [4,5,6] → Visit 4
Queue: [5,6] → Visit 5
Queue: [6] → Visit 6
Output: 1 2 3 4 5 6
Dynamic Programming - Fibonacci Sequence
Recursive Tree (Inefficient):
fib(5)
/
fib(4) fib(3)
/\/
fib(3) fib(2) fib(2) fib(1)
/\/\/
fib(2) fib(1) ... ...
Memoization (Top-down):
memo = {}
fib(5) → compute
fib(4) → compute
fib(3) → compute
fib(2) → compute → memo[2]=1
fib(1) → return 1
memo[3] = 2
fib(2) → return memo[2]=1
memo[4] = 3
fib(3) → return memo[3]=2
memo[5] = 5
Tabulation (Bottom-up):
dp[0] = 0
dp[1] = 1
dp[2] = dp[0] + dp[1] = 1
dp[3] = dp[1] + dp[2] = 2
dp[4] = dp[2] + dp[3] = 3
dp[5] = dp[3] + dp[4] = 5

Graph Algorithm Comparison

 Time Space
Algorithm Use Case
Complexity Complexity
Shortest path
BFS O(V + E) O(V)
(unweighted)
Connectivity, Cycle
DFS O(V + E) O(V)
detection
Shortest path
Dijkstra O((V+E) log V) O(V)
(weighted)
Bellman-
Negative weights O(VE) O(V)
Ford
Floyd-
All pairs shortest O(V³) O(V²)
Warshall
Minimum spanning
Kruskal O(E log E) O(V)
tree
Minimum spanning
Prim O((V+E) log V) O(V)
tree

Table 8: Graph algorithms comparison

References
[16] GeeksforGeeks. (2023). Python OOP Concepts. https://www.geeksforgeeks.org/python/py
thon-oops-concepts/
[17] Real Python. (2024). Object-Oriented Programming in Python. https://realpython.com/p
ython3-object-oriented-programming/

[18] Programiz. (2024). Python Object Oriented Programming. https://www.programiz.com/

python-programming/object-oriented-programming
[19] W3Schools. (2025). Python OOP. https://www.w3schools.com/python/python_oop.asp
[20] Error Makes Clever. (2025). OOPS Concepts in Python: A Developer's Guide. https://www.
errormakesclever.com/blog/oops-concepts-in-python

[21] Goodrich, M. T., Tamassia, R., & Goldwasser, M. H. (2013). Data Structures and
Algorithms in Python. Wiley.