Algorithms

Algorithms in C++

A comprehensive guide to algorithmic patterns and problem-solving techniques used in competitive programming and technical interviews.

Table of Contents

1. Backtracking
2. Dynamic Programming
3. Graph Algorithms
4. Greedy Algorithms
5. Binary Search
6. Bit Manipulation
7. Two Pointer Technique
8. Prefix Sum
9. Number Theory
10. Sorting and Array/String

---

Backtracking

Core Logic Pattern

Backtracking follows the "Try, Check, Undo" paradigm:

1. Try: Make a choice/decision
2. Check: Validate if choice leads to solution
3. Undo: Backtrack if choice doesn't work

Key Patterns

1. Subset Generation Pattern

Logic: For each element, we have 2 choices - Include or Exclude
Pattern: Pick/Not Pick

• Applications: All subsequences, subset sum, combination sum
• Time Complexity: O(2^n)
• Space Complexity: O(n) for recursion stack

2. Permutation Pattern

Logic: Try each unused element at current position
Pattern: Fix one element, permute rest

• Applications: All permutations, N-Queens, Sudoku
• Time Complexity: O(n!)
• Space Complexity: O(n)

3. Maze/Path Finding Pattern

Logic: Explore all 4 directions, mark visited, backtrack
Pattern: DFS with state restoration

• Applications: Rat in maze, word search, path counting
• Time Complexity: O(4^(m*n))
• Space Complexity: O(m*n)

Problem Categories

• Combination Problems: Subset sum, combination sum
• Arrangement Problems: N-Queens, Sudoku, graph coloring
• Path Problems: Maze solving, word search
• Optimization Problems: Finding all solutions to choose best

---

Dynamic Programming

Core Logic Patterns

1. Pick/Not Pick Pattern

Logic: For each element, decide whether to include it or not
Recurrence: dp[i] = max(pick[i], not_pick[i])

• Applications: 0/1 Knapsack, House Robber, Subset Sum
• Example: dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight[i]] + value[i])

2. Infinite Pick Pattern

Logic: Can use same element multiple times
Recurrence: dp[i] = dp[i] + dp[i-coin] for all coins

• Applications: Coin Change, Rod Cutting, Unbounded Knapsack
• Example: dp[amount] = min(dp[amount], dp[amount-coin] + 1)

3. Matrix Chain Multiplication (MCM) Pattern

Logic: Try all possible partition points
Recurrence: dp[i][j] = min(dp[i][k] + dp[k+1][j] + cost) for all k

• Applications: Matrix multiplication, palindrome partitioning, burst balloons
• Example: dp[i][j] = min(dp[i][k] + dp[k+1][j] + arr[i-1]*arr[k]*arr[j])

4. Longest Common Subsequence (LCS) Pattern

Logic: Match characters or skip from either string
Recurrence: if(s1[i]==s2[j]) dp[i][j] = 1 + dp[i-1][j-1]
           else dp[i][j] = max(dp[i-1][j], dp[i][j-1])

• Applications: Edit distance, longest palindromic subsequence
• Time Complexity: O(m*n)

5. Longest Increasing Subsequence (LIS) Pattern

Logic: For each element, find longest sequence ending at that element
Recurrence: dp[i] = max(dp[j] + 1) where arr[j] < arr[i]

• Applications: LIS, Russian doll envelopes, box stacking
• Optimization: Binary search approach O(n log n)

DP State Transitions

• 1D DP: dp[i] depends on previous states
• 2D DP: dp[i][j] depends on dp[i-1][j], dp[i][j-1], dp[i-1][j-1]
• 3D DP: Additional dimension for constraints

---

Graph Algorithms

Core Traversal Patterns

1. Depth-First Search (DFS)

Logic: Go as deep as possible, then backtrack
Pattern: Stack-based (recursive or iterative)

• Applications: Cycle detection, topological sort, connected components
• Time Complexity: O(V + E)
• Space Complexity: O(V)

2. Breadth-First Search (BFS)

Logic: Explore level by level
Pattern: Queue-based traversal

• Applications: Shortest path (unweighted), level order traversal
• Time Complexity: O(V + E)
• Space Complexity: O(V)

Specialized Graph Algorithms

3. Topological Sort

Logic: Linear ordering of vertices in DAG
Patterns: 
- DFS + Stack (finish time order)
- Kahn's Algorithm (indegree-based BFS)

• Applications: Course scheduling, build dependencies
• Cycle Detection: If topological sort includes all vertices, no cycle exists

4. Shortest Path Algorithms

Dijkstra's Algorithm

Logic: Greedy approach using priority queue
Pattern: Always pick minimum distance unvisited vertex

• Use Case: Single source shortest path (non-negative weights)
• Time Complexity: O((V + E) log V)

Bellman-Ford Algorithm

Logic: Relax all edges V-1 times
Pattern: Dynamic programming approach

• Use Case: Handles negative weights, detects negative cycles
• Time Complexity: O(V * E)

5. Cycle Detection Patterns

Undirected Graph

Logic: If we visit an already visited node (not parent), cycle exists
Pattern: DFS/BFS with parent tracking

Directed Graph

Logic: If we encounter a node in current path (back edge), cycle exists
Pattern: DFS with visited + path visited arrays

6. Bipartite Graph Detection

Logic: Try to color graph with 2 colors
Pattern: BFS/DFS with coloring

• Applications: Matching problems, conflict resolution

---

Greedy Algorithms

Core Logic

Make locally optimal choice at each step
Hope that local optimum leads to global optimum

Common Patterns

1. Activity Selection: Sort by end time, pick non-overlapping
2. Fractional Knapsack: Sort by value/weight ratio
3. Huffman Coding: Build optimal prefix-free codes
4. Minimum Spanning Tree: Kruskal's/Prim's algorithm

When Greedy Works

• Problem has optimal substructure
• Greedy choice property holds
• Can prove greedy choice leads to optimal solution

---

Binary Search

Core Logic Pattern

Divide search space in half based on condition
Pattern: left = 0, right = n-1, check mid condition

Search Patterns

1. Find Target: Classic binary search
2. Find First/Last Occurrence: Modified conditions
3. Search in Rotated Array: Find pivot first
4. Search Answer Space: Binary search on answer

Template

while(left <= right) {
    mid = left + (right - left) / 2;
    if(condition) right = mid - 1;
    else left = mid + 1;
}

---

Bit Manipulation

Core Operations

• AND (&): Check bits, clear bits
• OR (|): Set bits
• XOR (^): Toggle bits, find unique elements
• Left Shift (<<): Multiply by 2^n
• Right Shift (>>): Divide by 2^n

Common Patterns

1. Check if Power of 2: n & (n-1) == 0
2. Count Set Bits: Brian Kernighan's algorithm
3. Find Unique Element: XOR all elements
4. Generate Subsets: Use bitmask iteration

---

Two Pointer Technique

Core Patterns

1. Opposite Direction: Start from both ends, move towards center
2. Same Direction: Both pointers move in same direction (sliding window)
3. Fast-Slow Pointers: Detect cycles, find middle element

Applications

• Two Sum: Sorted array, opposite direction
• Three Sum: Fix one element, two pointer on rest
• Sliding Window: Maximum/minimum in subarray
• Palindrome Check: Compare characters from both ends

---

Key Problem-Solving Strategies

1. Pattern Recognition

• Identify if problem fits known patterns
• Look for keywords: "all possible", "optimal", "shortest", "maximum"

2. State Space Analysis

• Define what represents a state
• Identify state transitions
• Determine base cases

3. Complexity Analysis

• Time complexity based on state space size
• Space complexity based on recursion depth/memoization

4. Optimization Techniques

• Memoization (top-down DP)
• Tabulation (bottom-up DP)
• Space optimization (rolling arrays)
• Early termination conditions

---

Algorithm Selection Guide

Problem Type	Algorithm Choice	Time Complexity
All Solutions	Backtracking	Exponential
Optimal Solution	Dynamic Programming	Polynomial
Graph Traversal	DFS/BFS	O(V + E)
Shortest Path	Dijkstra/Bellman-Ford	O(V²) to O(VE)
Sorted Array Search	Binary Search	O(log n)
Local Optimum = Global	Greedy	Varies
Bit Operations	Bit Manipulation	O(1) to O(n)
Array/String Problems	Two Pointer	O(n)

This guide provides the fundamental patterns and logic behind each algorithmic approach, helping you recognize which technique to apply for different problem types.