Competitive Programming

#include "cp.h"

A repository containing my implementations of popular algorithms used in competitive programming and interviews

1. Arrays

Longest Bitonic Subarray
Longest Increasing Subsequence using Patience Sort
Maximum Subarray using Kadane
Remove duplicates in sorted array

2. Sorting

Bubble sort
Selection sort
Insertion sort
Quicksort
Mergesort

3. Strings

KMP
Z algorithm
Longest Palindromic substring using Manacher's algorithm
Palindrome partitioning using Manacher
Count character occurrences in sorted string
Remove K consecutive same characters

4. Trees

Insertion
Deletion
InOrder, PreOrder, PostOrder, LevelOrder traversal
InOrder traversal using stack
Search
InOrder successor and predecessor
Height of tree
Diameter of tree
Sum of nodes
Lowest Common Ancestor

5. Backtracking

N Queens

6. DP

0/1 Knapsack
stock price (leetcode problem)
Longest common subsequence
Longest common substring
Edit Distance
candles (atcoder problem)

7. Graph

Graph insertion
BFS
DFS
Dijkstra
Kruskal
Prims
Topological sort
Kahn's algorithm for topological sort
Fox and Names codeforces 510/C using Kahn's algorithm
Tarjan's algorithm for bridges and articulation points
Ford-Fulkerson Edmond's-Karp Max Flow algorithm

8. Advanced DS

Segment Tree
Trie

9. Bit Manipulation

hack1: basic stuff
hack2: K'th bit
hack3: rightmost set bit
hack4: letters