README.md

Competitive Programming Solutions from Leetcode, Kattis + Useful resources & templates

A collection of solutions to Leetcode problems, all in Kotlin language. Mix of EASY, MEDIUM, and HARD questions. Problems are named xxxx-problem-name-in-lowercase.kt, for example 71. Simplify Path is named 0071-simplify-path.kt. Usually all problems are solved in the most efficient way, but some problems contains several and different solutions, in the same file but clearly separated.

There are subfolders for problems from Kattis, Lintcode, Grind75 (Java).

I have also started adding resources and templates below, for all things important in Algorithms, Datastructures and Competitve Programming,

If you have a better solution for a problem, any optimization, another way of solving it, etc, I would love to hear from you. Open a Issue or PR.

Useful algorithms, Datastructures, Math, Techniques, etc for competitive programming

Basics

• Recursion
• Linear search
• Binary search

Sorting

• Heap sort
• Merge sort
• Quick sort
• Quick select
• Bucket sort
• Counting sort
• Radix sort
• Insertion sort
• Bubble sort
• Selection sort
• Shell sort
• Cycle sort

Graphs

• Breadth-first search
• Depth-first search
• Bellman–Ford algorithm
• Dijkstra's algorithm
• Eulerian path
• Floyd–Warshall algorithm
• Ford–Fulkerson algorithm
• Kruskal's algorithm
• Minimax
• Prim's algorithm
• Topological sorting
• Disjoint-set data structure (Union Find)
• Cycle detection in graphs
• Bipartite graph
• Color coding in graphs
• Hungarian algorithm

Trees

• Tree traversal
• Binary search tree
• Red–black tree
• Trie
• Segment tree
• Fenwick tree / Binary Indexed Tree (BIT)
• m-ary tree
• B-tree
• Heap
• Suffix Tree

Dynamic Programming

• Knapsack problem
• Longest increasing subsequence
• Longest common subsequence
• A very good guide on LCS from brute to optimizations
• Levenshtein distance
• Hamming distance

String

• Knuth–Morris–Pratt algorithm
• Rabin–Karp algorithm
• Boyer–Moore string-search algorithm
• Aho–Corasick algorithm
• Z algorithm
• Suffix array

Datastructures

• Linked list
• Stack
• Queue
• Deque
• Hashtable / HashMap / HashSet
• Priority queue
• LRU
• LFU
• Monotonic Queue/Stack
• Skip List

Bitwise operations

• Bit Twiddling Hacks by Sean Eron Anderson (stanford)
• Hacker’s Delight

Techniques

• Two pointers
• Divide-and-conquer
• Dynamic programming
• Heap's algorithm, all possible permutations
• All subsets of a given set
• All combinations of a given set
• Prefix sum / Suffix sum
• Greedy algorithm
• Sliding window
• Memoization
• Digit DP
• Reroot DP (calculate x for all y nodes etc)
• Day–Stout–Warren algorithm to rebalance BSTs

Math

• A List of Useful Equations in Competitive Programming

Misc

• Algorithms for Competitive Programming
• List of Data Structure and Algorithm
• List of Data Structure and Algorithm 2
• Usaco guide, curated list of techniques
• Top Algorithms and Data Structures for Competitive Programming
• KTH's ICPC team reference document
• Handbook of geometry for competitive programmers
• KTH Principles of Algorithmic Problem Solving