Awesome Competitive Programming Problems

Please press ⭐ button if you like this repo ❤. Thấy ngon thì nhấn star ⭐ ủng hộ mình nha các đồng dâm ❤

This repository contains my implementation of useful / well-known data structures, algorithms and solutions for awesome competitive programming problems in Hackerrank, Project Euler and Leetcode

I create this for faster implementation and better preparation in interviews as well as programming contests :trollface: :trollface:

:warning: This repo is day-by-day updated. Please make sure you have the latest version!

:fire: New updates today: Longest Substring Without Repeating Characters^[Leetcode]

:question: How to use

Overview of the file:

:firecracker: Tips and Tricks

Here is some tips and tricks to ACE all competitive programming problems and interview questions:

If input array is sorted then
    - Binary search
    - Two pointers

If asked for all permutations/subsets then
    - Backtracking

If given a tree then
    - DFS
    - BFS

If given a graph then
    - DFS
    - BFS

If given a linked list then
    - Two pointers

If recursion is banned then
    - Stack

If must solve in-place then
    - Swap corresponding values
    - Store one or more different values in the same pointer

If asked for maximum/minumum subarray/subset/options then
    - Dynamic programming

If asked for top/least K items then
    - Heap

If asked for common strings then
    - Map
    - Trie

Else
    - Map/Set for O(1) time & O(n) space
    - Sort input for O(nlogn) time and O(1) space

:watermelon: Algorithms

A) Data Structures Applications

:palm_tree: Binary Search Tree Algorithm

1. • [x] Binary Search Tree: Original Binary Search Tree Algorithm - O(log(n))
2. • [x] Binary Search Tree: Check a Number: Check if a Number is in a Sorted List using BST Algorithm - O(log(n))
3. • [x] Binary Search Tree: Index of a Number: Find the Index of a Number in a Sorted List using BST Algorithm - O(log(n))

B) String Algorithm

:ear_of_rice: Suffix Tree - Suffix Array

1. • [x] Suffix Array (Manber-Myers Algorithm): Find suffix array of a string S based on Manber-Myers algorithm - O(n.log(n)) , n = |S|
2. • [x] Longest Common Prefix Array (Kasai Algorithm): Find longest common prefix array of a string S with the help of suffix array based on Kasai algorithm - O(n) , n = |S|
3. • [ ] Longest Palindromic Substring - O(n) <Đợi xíu đang (lười) cập nhật :woozy_face:>
4. • [ ] Pattern Search - O(log(n)) <Đợi xíu bug nhiều vl sửa mãi chưa xong :dizzy_face:>

C) Searching and Graph Algorithms

:snowflake: Graph Theory

1. • [x] Graph Representation using Adjacency List: Unweighted, Un-/Directed: Create a Unweighted Un-/Directed Graph using Adjacency List
2. • [ ] Graph Representation using Adjacency List: Weighted, Un-/Directed <Mốt rảnh sẽ cập nhật sau :weary:>
3. • [x] Find All Nodes: Find All Nodes in the Unweighted Graph - O(V+E) for Adjacency List , V, E is the number of vertices and edges
4. • [ ] Find All Edges <Cái này dễ mà lười code ~@@~>
5. • [x] Find All Paths between 2 Nodes: Find All Paths between 2 Nodes in a Unweighted Graph using BFS - NP-Hard
6. • [x] Disjoint Set (Union-Find): Union by Rank and Path Compression: Create a Disjoint Set (Union-Find) using "Union by Rank and Path Compression" for an Undirected Graph (used to Detect Cycle) - Time = O(small constant), Space = O(V)

:recycle: Detect Cycle

7. • [x] Detect Cycle: Disjoint Set: Detect Cycle in an Undirected Graph based on Disjoint Set (Union-Find) using "Union by Rank and Path Compression" - O(V)

:airplane: Graph Traversal

8. • [x] Breadth-First Search: Find BFS Path from a Starting Node in Un-/Directed Graph - O(V+E) for Adjacency List; O(V²) for Adjacency Matrix , V, E is the number of vertices and edges
9. • [x] Depth-First Search: Find DFS Path from a Starting Node in Un-/Directed Graph - O(V+E) for Adjacency List; O(V²) for Adjacency Matrix , V, E is the number of vertices and edges

:shamrock: Minimum Spanning Tree (MST)

10. • [x] MST: Prim Algorithm^[PDF]: Find Minimum Spanning Tree (MST) of an Undirected Graph using Prim Algorithm - O(E.log(V))
11. • [x] MST: Kruskal Algorithm^[PDF]: Find Minimum Spanning Tree (MST) of an Undirected Graph using Kruskal Algorithm - O(E.log(E)) or O(E.log(V))

:kick_scooter: Shortest Path

12. • [x] Shortest Path: Breadth-First Search: Find the Shortest Path in a Unweighted Un-/Directed Graph based on BFS - O(V+E) for Adjacency List , V, E is the number of vertices and edges
13. • [x] Shortest Path: Dijkstra using Min-Heap^[PDF]: Find Shortest Path of an Non-Negative Un-/Weighted Un-/Directed Graph based on Dijkstra Algorithm using Min-Heap - O(E.log(V))
14. • [ ] Shortest Path: Bellman-Ford <Khó như chó méo bít code sao lun á mấy ba :joy:>
15. • [ ] Shortest Path: Floyd-Warshall <Cùng lý do như trên :grin:>

D) Greedy Algorithm

1. Sherlock and The Beast

• Find the "Decent Number" having n Digits ("Decent Number" has its digits to be only 3's and/or 5's; the number of 3's it contains is divisible by 5; the number of 5's it contains is divisible by 3; and it is the largest such number for its length)

2. Largest Permutation

• Swap 2 digits of a number k times to get largest number - O(n)

E) Dynamic Programming

Coin Change Algorithms: Given an array of choices, every choice is picked unlimited times

Knapsack Problems: Given an array of choices, every choice is picked only once

:moneybag: Coin Change Algorithms

1. • [x] Coin Change^[PDF]: How many ways to pay V money using C coins [C1,C2,...Cn] - O(C.V)
2. • [x] Integer Partition^[PDF]: How many ways to partition number N using [1,2,...N] numbers - O(n^1.5)
3. • [x] Minimum Coin Change^[Wiki]: Find Minimum Number of Coins to pay V money using C coins [C1,C2,...,Cn] - O(C.V)

:handbag: Knapsack Problems

4. • [x] Knapsack 0/1^[Wiki]: Given a List of Weights associated with their Values, find the Founding Weights and Maximum Total Value attained with its Total Weight <= Given Total Weight, each Weight is only picked once (0/1 Rule) - O(N.W) , N, W is length of weights array and given total weight
5. • [x] Partition Problem: Subset Sum^[Wiki]: Given an Array containing only Positive Integers, find if it can be Partitioned into 2 Subsets having Sum of elements in both subsets is Equal. - O(N.T) , N, T is the length of numbers array and the target sum (=sum/2)
6. • [ ] Partition Problem: Multiway Number Partitioning^[Wiki]: <Câu này để thi Olympic thôi chứ công ty nào hỏi phỏng vấn thì tán xéo háng nó :smiling_imp:>

:chart_with_upwards_trend: Path Sum Problems

7. • [x] Max Path Sum Triangle^[PDF]: Find Maximum Path Sum from Top to Bottom of a Triangle - O(R) , R is number of rows of the triangle
8. • [x] Min Path Sum Matrix: Top-Left to Right-Bottom, Right and Down Moves^[PDF]: Find Min Path Sum from Top-Left to Right-Bottom of a Matrix using Right and Down Moves - O(R.C) , R, C is length of row and column of the matrix

Subsequence = Any subset of an array/string

Subarray = Contiguous subsequence of an array

Substring = Contiguous subsequence of a string

:date: Subarray Problems

9. • [x] Max Subarray Sum (Kadane Algorithm)^[PDF]: Find Maximum Subarray Sum of an Array - O(n)
10. • [x] Max Subarray Sum (Kadane Algorithm - Extended)^[PDF]: Find Maximum Subarray Sum of an Array and its Indices - O(n)
11. • [x] Min Subarray Sum (Kadane Algorithm's Min Varient): Find Minimum Subarray Sum of an Array - O(n)
12. • [x] Subarray Sum Equals K^[Leetcode]: Find the Number of Continuous Subarrays of an Array whose Sum Equals to K - O(n)
13. • [x] Subarray Sum Divisible by K^[Leetcode]: Find the Number of Continuous Subarrays of an Array whose Sum is Divisible by K - O(n)

:dango: Subsequence Problems

14. • [x] Longest Common Subsequence (LCS)^[PDF]: Find the longest string S, every character in S is also in S1 and S2 but in order - O(|S1|.|S2|)
15. • [x] Longest Increasing/Decreasing Subsequence (Patience Sorting Algorithm)^[PDF]: Find the Longest Increasing or Decreasing Subsequence of an Array List based on Patience Sorting Algorithm- O(n.log(n))

:page_with_curl: Substring Problems

16. • [x] Longest Common Substring (Longest Common Factor - LCF): Find the Longest Common Substring (Factor) of 2 strings S1 and S2 - O(|S1|.|S2|)
17. • [x] Sum Of Substrings^[PDF]: Find Sum of All Substrings of an Number String S - O(|S|)

F) Two Pointers - Sliding Window

:book: Non-categorized

1. • [x] Longest Substring Without Repeating Characters^[Leetcode]: Find the Length of the Longest Substring Without Repeating Characters - O(|S|)

G) Mathematics

:blue_book: Binomial Coefficient Problems

1. • [x] Pascal Triangle: Create Pascal Triangle (to Calculate Multiple Large-Number Combinations) - O(n²)
2. • [x] PE #15: Lattice Paths^[PDF] : Find the number of routes from the top left corner to the bottom right corner in a rectangular grid

:closed_book: Factors Problems

3. • [x] Factorization: Find All Factors of a Number - O(n^1/2)

:green_book: Multiples Problems

4. • [x] PE #1: Multiples of 3 and 5^[PDF]: Find Sum of Multiples of a Number - O(1)

:notebook: Permutation Problems

5. • [x] Lexicographic Permutations^[PDF]: Find n-th Lexicographic Permutation of a very long Word - O(n)
6. • [x] Permutation Check: Check if 2 Numbers/Strings are Permutations - O(n) , n = max(|a|,|b|)

:orange_book: Primes Problems

7. • [x] "Sieve Method" All Primes: Find All Primes < n - Space = O(n^1/2)
8. • [x] Primality Test (Common Method): Check if n is a Prime Number using "Common Method" - O(n^1/2)
9. • [x] Primality Test (Miller-Rabin): Check if n is a Prime Number using Miller-Rabin Probabilistic Test - O(k.log³n) , k = [1,2,...]
10. • [x] Coprimes Check: Check if 2 Numbers are Coprime - O(log a.b)

:notebook_with_decorative_cover: Primes-Factors Problems

11. • [x] Euler Totient Function (Number List): Find ALL Numbers of Coprimes < n based on Euler Totient Function - O((l) + m.loglogm + l.(logm + k)) , k is the number of prime factors of n; m and l is max value and length of the input number list
12. • [x] Euler Totient Function (Single Number): Find the Number of Coprimes < n based on Euler Totient Function - O(n^1/2 + k) , k is the number of prime factors of the input number n
13. • [x] "Sieve Method" Smallest Prime Factors (SPF): Find Smallest Prime Factors for All Numbers < N - O(n.loglogn)
14. • [x] Prime Factorization (Smallest Prime Factor): Find All Prime Factors of a Number using Smallest Prime Factor (SPF) - O(log n) if a list of all Smallest Prime Factors from 0 to n available
15. • [x] Prime Factorization: Find All Prime Factors of a Number - O(n^1/2)

:ledger: Pythagorean Theorem

16. • [x] Pythagorean Triplets Perimeter: Find Pythagorean Triplets having Perimeter (or Sum) P - O(P)
17. • [x] Pythagorean Triplets Less or Equal N: Generate all Pythagorean Triplets <= N - O(N.log(N))

:book: Non-categorized

18. • [x] Number Spiral Diagonals^[PDF]: Find Sum of Diagonals of Ulam Spiral Matrix

Recursion Algorithm

<Mới bị cắm sừng, méo mún code nữa :bomb:>

Backtracking

Divide and Conquer