Contents

Algorithms

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

  1. Probability problems, and other Discrete Math 101 situations.

  2. The essentials of combinatorics and probability.

  3. 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

next

Trees