Chief-Rishab/Data_Structures_and_Algorithms_CPP

Data Structures. Algorithms. Problems & Solutions implemented in C++.

FMI Data Structures and Algorithms (DSA)

N	loc N	Topics	Problem statement	Solution
WEEK 01	-	-	-	-
lecture 01	-	complexity, data structures and algorithms	-	-
001	01	greedy	Store discount	Solution.cpp
002	02	counting	Substring permutations	Solution.cpp
003	03	sortings	Pipi's socks	Solution.cpp
004	04	counting	Palindromic permutation	Solution.cpp
005	05	implementation	Super reduced string	Solution 1 (fast).cpp Solution 2.cpp
006	06	brute force, recursion	The power sum	Solution (recursive).cpp Solution (generate).cpp
007	07	hw 01, implementation	Encoding password	Solution 1.cpp Solution 2.cpp
008	08	hw 01, implementation	SDA mission	Solution 1.cpp Solution 2.cpp
009	09	hw 01, greedy, implementation	Water supplies	Solution 1.cpp Solution 2.cpp
010	10	hw 01, math	Cloning socks	Solution 1 (induction n).cpp Solution 2.cpp
011	11	hw 01, brute force, implementation	Darts 501	Solution 1.cpp Solution 2.cpp Solution 3.cpp
012	12	binary search	Climbing the leaderboard	Solution.cpp
013	13	recursion	Palindrome word check	Solution.cpp
014	14	counting	Stripe interview problem	Solution.cpp
015	15	counting	Game of thrones - I	Solution.cpp
WEEK 02	-	-	-	-
lecture 02	-	sorting and searching algorithms	-	-
016	01	sortings	Merge sort	Solution 1 (classic).cpp Solution 2 (short).cpp
017	02	sortings	Merge sort inversions count	Solution 1.cpp Solution 2.cpp
018	03	sortings	Quick sort (random pivot)	Solution.cpp
019	04	sortings	Radix sort	Solution.cpp
020	05	sortings	Tim sort	Solution.cpp
021	06	sortings	Couples password	Solution 1.cpp Solution 2 (short).cpp
022	07	searching, sortings	Shoe shopping	Solution.cpp
023	08	counting	String arrangement	Solution.cpp
024	09	greedy, sortings	Scrooge's gift	Solution 1.cpp Solution 2.cpp
025	10	sortings	Software regulation	Solution 1 (fast).cpp Solution 2 (slow).cpp
026	11	hw 02, counting	Permutations	Solution 1.cpp Solution 2.cpp
027	12	hw 02, sortings	Monster world	Solution 1.cpp Solution 2.cpp
028	13	hw 02, sortings	Electrical energy	Solution 1.cpp Solution 2.cpp
029	14	hw 02, greedy, sortings	Events	Solution 1.cpp Solution 2.cpp
030	15	searching, sortings	Quick select	Solution.cpp
031	16	searching, sortings	The jeweller problems	Solution.cpp
032	17	sortings	Visualise sorting by merging	Solution.cpp
033	18	sortings	Visualise sorting by pivoting	Solution.cpp
034	19	control test, counting sort	Control test 01	Solution.cpp
035	20	counting, sortings	Counting sort (float)	Solution.cpp
036	21	searching, sortings	Pairs	Solution.cpp
037	22	binary search	Binary search	Solution 1 (most left/right pos).cpp Solution 2 (recursive).cpp
038	23	searching	Pair sum	Solution.cpp
039	24	binary search	Sqrt (binary search on answer)	Solution.cpp
040	25	binary search	Office printers	Solution.cpp
041	26	binary search	Upper/Lower bound	Solution.cpp
WEEK 03	-	-	-	-
lecture 03 pt.1 lecture 03 pt.2		searching algorithms, linked lists	-	-
042	01	implementation, recursion	Chocolate chip cookies	Solution.cpp
043	02	implementation, quick select	Searching for index	Solution.cpp
044	03	binary search, implementation, searching	Drying clothes	Solution.cpp
045	04	binary search, ternary search	Building alignment	Solution.cpp
046	05	greedy, sortings	Gems	Solution.cpp
047	06	hw 03, binary search	Strawberries	Solution 1.cpp Solution 2.cpp
048	07	hw 03, binary search	Cows	Solution 1.cpp Solution 2.cpp
049	08	hw 03, binary search	Balloons and candy	Solution 1.cpp Solution 2.cpp Solution 3.cpp
050	09	hw 03, binary search, ternary search	Monster trucks	Solution 1 (bs).cpp Solution 2 (ts).cpp Solution 3.cpp
051	10	binary search	Left/Right most	Solution.cpp
052	11	binary search	Search 2 el with diff	Solution.cpp
053	12	binary search	Hackerland radio transmitters	Solution.cpp
WEEK 04	-	-	-	-
lecture 04	-	stack	-	-
054	01	linked lists	Control test 02	Solution.cpp
055	02	linked lists	Singly linked list	Solution.cpp
056	03	linked lists	Min max sum	Solution.cpp
057	04	linked lists	List pairs	Solution.cpp
058	05	implementation	Cloning snowmen	Solution.cpp
059	06	linked lists	Pistols	Solution.cpp
060	07	linked lists	Smurfieta's writing	Solution.cpp
061	08	stacks	MAX element in stack	Solution.cpp
062	09	hw 04, linked lists	Node at pos	Solution.cpp
063	10	hw 04, linked lists	Delete a node	Solution.cpp
064	11	hw 04, linked lists	Merge two sorted linked lists	Solution.cpp
065	12	hw 04, linked lists	Reverse linked list	Solution 1 (iterative).cpp Solution 2 (recursive).cpp
066	13	wh 04, stacks	Truck ordering	Solution 1.cpp Solution 2.cpp
067	14	hw 04, stacks	Welcome to the jungle	Solution 1.cpp Solution 2.cpp
068	15	hw 04, implementation	Optimal teams	Solution 1.cpp Solution 2.cpp
069	16	queues	Hamming numbers	Solution.cpp
070	17	bfs, wave method	Shortest path in maze	Solution.cpp
071	18	queues	Remove min elements in queue	Solution.cpp
072	19	stacks	Hikers	Solution.cpp
WEEK 05	-	-	-	-
lecture 05 pt.1 lecture 05 pt.2 lecture 05 pt.3	-	queues, wave method, non-linear data structures, trees, binary trees	-	-
073	01	linked lists, math	Josephus problem	Solution 1 (linked list).cpp Solution 2 (bitwise).cpp Solution 3 (calculus).cpp
074	02	linked lists	Lilly's stone path	Solution.cpp
075	03	bfs, wave method	Shortest path in labirinth	Solution.cpp
076	04	queues	Magic numbers	Solution.cpp
077	05	hw 05, trees	Los binares	Solution.cpp
078	06	hw 05, bfs, wave method	Rotten from the core	Solution 1.cpp Solution 2.cpp Solution 3.cpp
079	07	hw 05, implementation, queues, structures	Student's queue	Solution 1.cpp Solution 2.cpp
080	08	hw 05, structures, queues	Bonus: Min-Max-Intervals	Solution 1.cpp Solution 2.cpp
081	09	trees	Level order traversal in BT	Solution.cpp
082	10	trees	Binary search tree - insertion	Solution.cpp
083	11	trees	Is this a binary search tree?	Solution 1.cpp Solution 2 (recursive).cpp
084	12	trees	Binary Search Tree - Lowest Common Ancestor	Solution 1.cpp Solution 2.cpp
085	13	trees	RLD	Solution.cpp
086	14	trees	Left-right	Solution 1 (iterative).cpp Solution 2 (recursive).cpp
087	15	trees	Falling leaves	Solution.cpp
088	16	trees	Worry beads	Solution 1 (bfs).cpp Solution 2 (dfs).cpp
089	17	trees	Sum level rows	Solution 1 (bfs).cpp Solution 2 (dfs).cpp
090	18	trees	Depth of BT	Solution.cpp
091	19	trees	Symmetric tree	Solution.cpp
092	20	trees	K-th smallest element in a BST	Solution 1.cpp Solution 2.cpp
093	21	trees	Delete node in a BST	Solution.cpp
094	22	trees	Tree specific print	Solution.cpp
095	23	trees	Print specific level	Solution 1.cpp Solution 2.cpp
096	24	trees	Penultimate descendants	Solution 1.cpp Solution 2.cpp
WEEK 06	-	-	-	-
lecture 06 pt.1 lecture 06 pt.2 (online)	-	balanced trees, AVL tree	-	-
097	01	trees	Height of a binary tree	Solution.cpp
098	02	trees	Top view	Solution.cpp
099	03	trees	K-th ancestor	Solution.cpp
100	04	trees	Self Balancing Tree (AVL)	Solution.cpp
101	05	trees	Valid BST	Solution.cpp
102	06	hw 06, trees	Attacking vigorously the leaderboard	Solution.cpp
103	07	hw 06, trees	Elitism	Solution 1 (multiset).cpp Solution 2 (heap).cpp
104	08	greedy, heap	Closest apartments	Solution.cpp
105	09	greedy	Bonus: 94	Solution 1 (author).cpp Solution 2 (multiset).cpp Solution 3 (flow).cpp
106	10	hash	Online market 1	Solution.cpp
107	11	graphs	Online market 2	Solution.cpp
108	12	heap	K-th largest element in stream	Solution.cpp
109	13	sets	Dundee the crocodile	Solution 1.cpp Solution 2.cpp Solution 3.cpp
110	14	greedy	Minimum number of refueling stops	Solution.cpp
WEEK 07	-	-	-	-
lecture 07	-	heap	-	-
111	01	set	One-Dimensional Battle Ships	Solution.cpp
112	02	hash, set	Administration	Solution.cpp
113	03	hw 07, trees	Autocomplete suggestions	Solution 1 (Trie).cpp Solution 2.cpp
114	04	hw 07, hash	Grand hotel	Solution.cpp
115	05	hw 07, implementation, trees	File system	Solution 1.cpp Solution 2.cpp
116	06	hw 07, hash	Bonus: Text contents	Solution 1 (rolling hash).cpp Solution 2 (experimental).cpp Solution 3 (rolling hash).cpp Solution 4 (secure hash).cpp
117	07	heap	Commandos	Solution.cpp
118	08	implementation	Schedules	Solution 1.cpp Solution 2.cpp
WEEK 08	-	-	-	-
lecture 08 pt.1 lecture 08 pt.2	-	kd-trees	-	-
119	01	bfs, dfs and similar	Components in a graph	Solution 1 (dfs).cpp Solution 2 (bfs).cpp
120	02	bfs, graphs	Snakes and ladders	Solution.cpp
121	03	bfs	Shortest reach	Solution 1.cpp Solution 2.cpp Solution 3.cpp
122	04	graphs	Connected cell in a grid	Solution 1 (bfs).cpp Solution 2 (dfs).cpp
123	05	graphs	Number of Islands	Solution.cpp
124	06	graphs	Course Schedule II	Solution 1 (Kahn).cpp Solution 2 (2 color mark).cpp
125	07	graphs	Cycle detector	Solution 1 (back edge).cpp Solution 2 (topological sort).cpp
126	08	bfs, dfs and similar	Castle on the grid	Solution.cpp
127	09	graphs	Edge removal	Solution 1 (dfs).cpp Solution 2.cpp
128	10	graphs	API	Solution (backtracking).cpp
129	11	graphs	Roads and libraries	Solution.cpp
130	12	hash	Toll tax	Solution.cpp
131	13	graphs	Green school	Solution.cpp
WEEK 09	-	-	-	-
lecture 09 lecture 10	-	hash table, graphs	-	-
132	01	graphs	Dijkstra- shortest reach 2	Solution.cpp
133	02	hw 08, graphs	Christmas markets	Solution 1.cpp Solution 2 (shortest cycle).cpp
134	03	hw 08, graphs	Christmas decoration	Solution 1 (dfs).cpp Solution 2 (bfs).cpp Solution 3.cpp
135	04	hw 08, graphs	Maze escape	Solution 1.cpp Solution 2.cpp
136	05	hw 08, graphs	Discos	Solution.cpp
137	06	hw 08, graphs	Bonus: Tunnel maps	Solution 1.cpp Solution 2.cpp
138	07	hw 08, graphs, dp	Bonus: BDZ	Solution 1 (topological sort).cpp Solution 2 (dp, memo).cpp
WEEK 10	-	-	-	-
lecture 11 lecture 12 lecture 13	-	Dijkstra's shortest path in graph algorithm, Kruskal algorithm (minimal spanning tree), {P, NP, NP-Complete}	-	-
139	01	hw 09, graphs	Minimal forest	Solution.cpp
140	02	hw 09, graphs	Floyd - City of blinding lights	Solution.cpp
141	03	hw 09, graphs, disjoint set	Blocked roads	Solution (disjoint set).cpp
142	04	hw 09, graphs	Kruskal (MST) - Really Special Subtree	Solution.cpp
WEEK 11	-	-	-	-
lecture 14	-	summary	-	-
EXAM 24.01.20	-	-	-	-
143	01	graphs	Road check	Solution 1 (adj matrix).cpp Solution 2 (adj list).cpp Solution 3 (dfs).cpp
144	02	binary search	Find element	Solution 1 (binary search).cpp Solution 2 (bounds).cpp
145	03	graphs	Counting areas	Solution 1 (bfs).cpp Solution 2 (dfs).cpp
146	04	trees	Profil of a tree	Solution (lvl order traversal).cpp
147	05	graphs	Shortest tour	Solution (bfs).cpp

Theme	Introduction	Implementation
Sorting and Shuffling	Sorting and shuffling	Implementation.cpp
Searching	Searching	Searching.cpp
Recursion and backtracking	Recursive algorithms and backtracking	Implementation.cpp
Combinatorics algorithms	Combinatorics algorithms	Implementation.cpp
Trie	Prefix Trie	Implementation.cpp
Trie	Autocomplete Trie	Implementation.cpp
Binary Heap	Binary Heap	Implementation.cpp
2D Tree	2D Tree	Implementation.cpp
KD-Tree	KD Tree	Implementation.cpp
Hash-Table	Hash-Table using Lists	Implementation.cpp
Dijkstra's algorithm	Dijkstra's algorithm	Implementation.cpp Examples.md
Bellman-Ford algorithm	Bellman–Ford algorithm	Implementation.cpp
Graham scan	Graham scan	Implementation.cpp

Subdomain	Challenge	Points	Solution
Interview Preparation Kit>Stairs	Staircase with n steps	-	Solution.cpp
Interview Preparation Kit>Arrays	Left Rotation	20	Solutioon.cpp
Interview Preparation Kit>Arrays	New Year Chaos	40	Solution.cpp
Interview Preparation Kit>Arrays	Minimum Swaps 2	40	Solution.cpp
Interview Preparation Kit>Trees	Trees:Is This a Binary Search Tree?	30	Solution 1 (recursive).cpp Solution 2 (inorder traversal).cpp
Interview Preparation Kit>Dictionaries and Hashmaps	Ransom Note	25	Solution.cpp
Interview Preparation Kit>Dictionaries and Hashmaps	Two Strings	25	Solution.cpp
Interview Preparation Kit>Dictionaries and Hashmaps	Sherlock and Anagrams	50	Solution.cpp
Algorithms	Smallest positive number missing	-	Solution.cpp
Algorithms	Fractional Knapsack Problem	-	Solution.cpp
Algorithms	Wave Method	-	Solution.cpp
Algorithms	Mixed Words	-	Solution.cpp
Algorithms	Search Word in Grid	-	Solution.cpp
Algorithms	Word Match in Char Grid	-	Solution.cpp
Algorithms	All Paths in Labyrinth	-	Solution.cpp
Algorithms	Sudoku	-	Solution.cpp
Algorithms	Generate Snakes	-	Solution.cpp
Algorithms>Implementation	Electronics Shop	15	Solution.cpp
Algorithms>Implementation	Non-Divisible Subset	20	Solution 1 (counting).cpp
Algorithms>Implementation	Forming a Magic Square	20	Solution 1.cppSolution 2.cpp Solution 3.cpp
Algorithms>Implementation	Extra Long Factorials	20	Solution.cpp
Algorithms>Implementation	Lisa's Workbook	25	Solution 1.cpp Solution 2.cpp
Algorithms>Implementation	Queen's Attack II	30	Solution 1 (bfs).cpp Solution 2 (dfs)
Algorithms>implementation	Organizing Containers of Balls	30	Solution.cpp
Algorithms>Implementation	Bigger is Greater	35	Solution 1 (binary search).cpp Solution 2 (built-in function).cpp
Algorithms>Implementation	The Grid Search	30	Solution 1.cpp Solution 2.cpp
Algorithms>Implementation	Ema's Supercomputer	40	Solution 1 (brute force).cpp
Algorithms>Implementation	Larry's Array	40	Solution 1 (slow).cpp Solution 2 (fast).cpp
Algorithms>Greedy	Minimum Coins	-	Solution.cpp
Algorithms>Greedy	Candies	50	Solution.cpp
Mathematics>Fundamentals	Is Fibo	20	Solution 1 (memory).cpp Solution 2 (precompute).cpp
Data Structures>Arrays	Moving Zeros	-	Solution.cpp
Data Structures>Arrays	Missing Number in AP	-	Solution.cpp
Data Structures>Arrays	Array Manipulation	60	Solution.cpp
Data Structures>2D Arrays	8 Queens Problem	-	Solution.cpp Solution (optimized).cpp
Data Structures>Linked Lists	Cycle Detection	5	Solution 1 (Floyd's algorithm).cpp Solution 2 (unordered set).cpp
Data Structures>Stacks	Signal and Noise	-	Solution.cpp
Data Structures>Stacks	Simple Text Editor	65	Solution 1 (stack).cpp Solution 2 (history stack).cpp
Data Structures>Stacks	Infix to postfix conversion	-	Solution.cpp
Data Structures>Stacks	Evaluation of postfix expression	-	Solution.cpp
Data Structures>Stacks	Game of Two Stacks	30	Solution 1 (vectors).cpp Solution 2 (upper bound).cpp
Data Structures>Stacks	Largest Rectangle	50	Solution 1 (stack).cpp Solution 2 (vector).cpp Algorithm explanation.md
Data Structures>Stacks	Waiter	75	Solution 1 (stacks).cpp Solution 2.cpp
Data Structures>Stacks	Tower of Hanoi	-	Solution.cpp
Data Structures>Queues	Queue using Two Stacks	30	Solution.cpp
Data Structures>Queues	Down to Zero II	40	Solution 1 (precompute).cpp Solution 2 (hidden graph).cpp Solution 3 (queue).cpp
Data Structures>Trees	Preorder, Inorder, Postorder traversals in BT	-	Solution.cpp
Data Structures>Trees	Tree: Huffman Decoding	20	Solution.cpp
Data Structures>Trees	Swap Nodes [Algo]	40	Solution 1 (bfs).cpp Solution 2 (child vectors).cpp
Data Structures>Trees	Inorder successor in BST	-	Solution.cpp
Data Structures>Trie	Contacts	40	Solution 1 (trie).cpp Solution 2 (mapping)
Data Structures>Graph Theory	Journey to the Moon	50	Solution 1 (bfs).cpp Solution 2 (dfs).cpp Solution 3 (disjoint set).cpp
Data Structures>Graph Theory	Rust & Murderer	70	Solution (special bfs).cpp
Data Structures>Graph Theory	Frog in Maze	65	Solution.cpp
Data Structures>Disjoint Set	Components in a graph	50	Solution 1 (bfs).cpp Solution 2 (dfs).cpp Solution 3 (disjoint set).cpp
Data Structures>Advanced	Kindergarten Adventures	30	Solution.cpp
Data Structures Advanced	Mr. X and His Shots	50	Solution 1 (bounds).cpp Solution 2 (marking).cpp
Data Structures>Advances	Jim and the Skyscrapers	60	Solution (stack).cpp
Data Structures>Advanced	Find Maximum Index Product	100	Solution (stack).cpp
Contest>101 Hack Jan 2016	Max-Sum-Subarray	30	Solution.cpp
Contests>101 Hack Jan 2016	Longest Path	50	Solution 1 (2 dfs).cpp Solution 2 (short).cpp Solution 3 (bfs).cpp
Contests>101 Hack Feb 2016	Beautiful Pairs	20	Solution (multiset).cpp
Contests>101 Hack Feb 2016	Minimum Penalty Path	50	Solution 1 (bfs).cpp Solution 2 (dfs).cpp Solution 3 (disjoint set).cpp
Codeforces Round #143	E. Cactus	graphs, trees, combinatorics, data structures	Analysis Solution.cpp
C++>STL	Deque-STL	50	Solution (linear).cpp
C++>STL	Phone Book	30	Solution.cpp
C++>STL	2D Arrays	30	Solution.cpp
C++>STL	Queues and Stacks	30	Solution
C++>STL	Lower Bound-STL	15	Solution 1 (array).cpp Solution 2 (vector).cpp
C++>Linked List	Insert Function	30	Solution.cpp
C++>Linked List	Remove Duplicates	30	Solution.cpp
C++>Exceptions	String to Integer	15	Solution.cpp
C++>Exceptions	More Exceptions	30	Solution.cpp
C++>BST	Binary Search Trees	30	Solution.cpp
C++>BST	Level Order Traversal	30	Solution.cpp
C++>Running Time and Complexity	Is Prime	30	Solution.cpp
C++>RegEx,Patterns	e-mail	30	Solution.cpp
C++>Bitwise	Bitwise AND	30	Solution.cpp Explanation.md

Additional Algorithms

1. Tarjan algorithm for finding Bridges and Articulation Points

2. Sparse Table

3. Lowest Common Ancestor

N	Algorithm	About	Time complexity	Statement	Solution
1.01	Finding bridges in a graph	graphs, dfs trees, back edges	O(N+M)	Critical edges	Solution.cpp Debug.cpp Debug.gif Examples (exploring).cpp
1.02	Finding articulation points in a graph	graphs, dfs trees, back edges	O(N+M)	Submerge Articulation Points and Bridges (Challenge)	Solution (Submerge).cpp Art. Pts. & Bridges (Solution 1).cpp Art. Pts. & Bridges (Solution 2).cpp
1.03	Directing edges to form a strongly connected digraph	dfs and similar, graphs	O(N+M)	Bertown roads	Solution.cpp
1.04	Cactus (Hard)	data structures, dfs and similar, dp, graphs, trees	O(N.log(N) + Q)	E. Cactus	Analysis Solution 1.cpp Solution 2.cpp
2.01	Range Minimum Query (RMQ)	arrays, sparse tables	O(N.log(N)) preprocessing, O(1) for each query	RMQSQ - Range Minimum Query RPLN - Negative Score	Solution (RMQSQ).cpp Solution (RPLN).cpp
2.02	Range Maximum Query (RMQ)	arrays, sparse tables	O(N.log(N)) preprocessing, O(1) for each query	THRBL - Catapult that ball	Solution.cpp
2.03	Range Min & Max Query	arrays, sparse-tables	O(N.log(N)) preprocessing, O(1) for each query	Matchsticks	Solution.cpp
2.04	RMQ, bs on answer with O(1) validation func	binary search, binary search on answer, sparse tables	O(N.log(N)) building ST, O(log N) per RQ	Sereja and D	Solution.cpp Editorial
2.05	Count of intervals with GCD=x	brute force, data structures, math	O(N.log^2(N)) preprocessing, O(1) for each query	CGCDSSQ	Solution algorithm design and analysis Solution 1 (sparse table).cpp Solution 2 (hash table).cpp
2.06	Droid Army (Multiple Sparse Tables)	binary search, data structures, two pointers	O(M.N.log(N))	D. R2D2 and Droid Army	Solution.cpp
2.07	K Subsegments of Sequence	implementation	O(N.log(N)) or O(N)	Maximum of Maximums of Minimums	Solution 1 O(n.log(n)).cpp Solution 2 O(n).cpp Analysis
2.08	Range Minimal Index Query (RMIQ)	data structures	O(N.log(N))	TNVFC1M - Miraculous	Solution.cpp
2.09	Multiplication Interval (Hard)	Segment Tree, Interval Tree, Sparse Table	O(N.log(N))	DCP-19: Multiplication Interval	Solution.cpp
2.10	2D RMQ	data structures, binary search	O(N.M.log(N).log(M)) preprocessing, O(log(N)) for each query	D. Animals and Puzzle	2D RMQ Theory Solution.cpp
3.01	Lowest Common Ancestor (LCA)	trees, lca	O(N.log(N)) preprocessing, O(1) for each query	Algorithm LCA - Lowest Common Ancestor	Solution.cpp