Algorithms

The content of this repository is also hosted at: https://peter-lucia.github.io/algorithms/

Table of Contents:

1. Graph
2. Tree / Binary Search Tree
3. HashTables
4. Sorting And Searching
5. Dynamic Programming
6. Number Theory
7. Math: Combinatorics / Probability)
8. String / Array / Stack
9. Linked List
10. BIT Manipulation
11. Python
12. NP-Complete
13. References

Graph

1. Breadth First Search (BFS)
2. Depth First Search (DFS)
3. Shortest Path from source to all vertices Dijkstra
4. Shortest Path from every vertex to every other vertex Floyd Warshall
5. To detect cycle in a Graph DFS
6. To detect cycle in a Graph Union Find
7. Minimum Spanning tree Prim
8. Minimum Spanning tree Kruskal
9. Topological Sort
10. Boggle (Find all possible words in a board of characters)
11. Bridges in a Graph
12. There are 3 basic ways to represent a graph in memory (objects and pointers, matrix, and adjacency list). Each representation and its pros + cons.
13. 1293. Shortest Path in a Grid with Obstacles Elimination

Trees / Binary Search Tree

1. Basic tree construction, traversal and manipulation algorithms
2. Binary Trees
3. N-ary trees
4. Trie-trees
5. BFS Binary Tree
6. AVL Tree
7. Tree traversal algorithms: BFS Adj list and DFS Adj list
8. The difference between inorder, postorder and preorder.
9. Find Minimum Depth of a Binary Tree
10. Maximum Path Sum in a Binary Tree
11. Check if a given array can represent Preorder Traversal of Binary Search Tree
12. Check whether a binary tree is a full binary tree or not
13. Bottom View Binary Tree
14. Print Nodes in Top View of Binary Tree
15. Remove nodes on root to leaf paths of length < K
16. Lowest Common Ancestor in a Binary Search Tree
17. Check if a binary tree is subtree of another binary tree
18. Reverse alternate levels of a perfect binary tree
19. Find and Remove Leaves of Binary Tree
20. Find and Remove Leaves of Binary Tree (DFS)
21. Find mode in binary search tree (BFS)
22. 116. Populating Next Right Pointers in Each Node in a Perfect Binary Tree
23. 1026. Maximum Difference Between Node and Ancestor

HashTables

1. How to implement one using only arrays.
2. 432. Reconstruct original digits from english
3. 811. Subdomain Visit count
4. 49. Group Anagrams
5. 249. Group Shifted Strings
6. 347. Top k frequent elements

Sorting And Searching

1. Binary Search
2. Search an element in a sorted and rotated array
3. Bubble Sort
4. Insertion Sort
5. Merge Sort can be highly useful in situations where quicksort is impractical
6. Heap Sort (Binary Heap)
7. Quick Sort
8. Interpolation Search
9. Find Kth Smallest/Largest Element In Unsorted Array
10. Given a sorted array and a number x, find the pair in array whose sum is closest to x
11. Counting Sort Pseudocode Worst Time: O(n+k), Worst Space: O(k), k = max(nums)
12. Stock Buy Sell to Maximize Profit
13. 843. Guess the word

Dynamic Programming

1. Longest Common Subsequence
2. Longest Increasing Subsequence
3. Edit Distance
4. Minimum Partition
5. Ways to Cover a Distance
6. Longest Path In Matrix
7. Subset Sum Problem
8. Optimal Strategy for a Game
9. 0-1 Knapsack Problem
10. Boolean Parenthesization Problem
11. Get nth number in the Fibonacci Sequence
12. Longest string chain
13. 792. Number of matching subsequences
14. 70. Climb Stairs
15. 416. Partition Equal Subset Sum

Number Theory

1. Modular Exponentiation
2. Modular multiplicative inverse
3. Primality Test | Set 2 (Fermat Method)
4. Euler’s Totient Function
5. Sieve of Eratosthenes
6. Convex Hull
7. Basic and Extended Euclidean algorithms
8. Segmented Sieve
9. Chinese remainder theorem
10. Lucas Theorem
11. Check if a number is prime or not
12. Number of primes less than n
13. 1015. Smallest Integer Divisible by K

Math: Combinatorics and Probability

15. Probability problems, and other Discrete Math 101 situations.
16. The essentials of combinatorics and probability.
17. N-choose-K problems

String / Array

1. Reverse an array without affecting special characters
2. All Possible Palindromic Partitions
3. Count triplets with sum smaller than a given value
4. Convert array into Zig-Zag fashion
5. Generate all possible sorted arrays from alternate elements of two given sorted arrays
6. Pythagorean Triplet in an array
7. Length of the largest subarray with contiguous elements
8. Find the smallest positive integer value that cannot be represented as sum of any subset of a given array
9. Smallest subarray with sum greater than a given value
10. 735. Asteroid Collision
11. 20. Valid Parentheses
12. 189. Rotate Array
13. 68. Text Justification
14. 2007. Find Original Array from doubled array
15. 822. Find And Replace String
16. 384. Shuffle an Array
17. 53. Maximum subarray
18. 28. Implmeent strStr() / Rabin-Karp find needle in haystack
19. 2128. Remove All Ones With Row and Column Flips

Linked List

1. Insertion of a node in Linked List (On the basis of some constraints)
2. Delete a given node in Linked List (under given constraints)
3. Compare two strings represented as linked lists
4. Add Two Numbers Represented By Linked Lists
5. Merge A Linked List Into Another Linked List At Alternate Positions
6. Reverse A List In Groups Of Given Size
7. Union And Intersection Of 2 Linked Lists
8. Detect And Remove Loop In A Linked List
9. Merge Sort For Linked Lists
10. Select A Random Node from A Singly Linked List
11. Reverse a linked list
12. 2095. Delete the Middle Node of a Linked List
13. 21. Merge Two Sorted Lists

BIT Manipulation

1. Maximum Subarray XOR
2. Magic Number
3. Sum of bit differences among all pairs
4. Swap All Odds And Even Bits
5. Find the element that appears once
6. Binary representation of a given number
7. Count total set bits in all numbers from 1 to n
8. Rotate bits of a number
9. Count number of bits to be flipped to convert A to B
10. Find Next Sparse Number
11. 476. Number Complement

Python Language

1. Defaultdict
2. Bisect
3. Class variables vs. instance variables
4. Static variables in functions

Geometry

1. Is Square Valid

NP-Complete

NP-Complete means a problem is both NP-Hard and a solution is verifiable in polynomial time.

Structure of NP-Complete proofs

1. Demonstrate that we can validate a solution for B in polynomial time (B is in NP)
2. Show the reduction from a known problem, $A \leq_p B$ (A is no harder than B and B is at least as hard as A). (B is NP_Hard)
   1. Instance of A converted to instance of B in polynomial time
   2. Solution of B converted to solution of A in polynomial time
   3. If you have a solution for B you have a solution for A
   4. If no solution for B no solution for A (or contra-positive – if you have a solution for A then you have a solution for B)

References

• Big-O Cheatsheet
• Determine Primes via Square Root
• Primes Stackoverflow
• Baillie-PSW Primality Test
• Wiki - Fermat Pseudoprime
• Primality Test
• Youtube: Khan Academy Combination formula
• Dijkstra's Algorithm
• Graph data structure
• Adjacency List vs. Adjacency Matrix
• Common algorithms
• Python heapq
• Heapsort

Python Version: 3.8.7