DS_ALGO_prep

Arrays

Index	Problem	Prerequisite
1	Maximum circular subarray sum	Kadane's Algorithm
2	Find subarray with given sum	Hashing
3	Equilibrium index of an array	None
4	Maximum Sum Increasing Subsequence	Simple DP
5	K-Concatenation	Kadane's Algorithm
6	Convert array into Zig-Zag fashion	None
7	Find a pair with the given difference	Hashing
8	Chocolate Distribution Problem	None
9	Minimum Number of Platforms Required for a Railway/Bus Station	None
10	Trapping Rain Water	None
11	Stock Buy Sell to Maximize Profit	None
12	Rotate by 90 degree	None
13	Find k pairs with smallest sums in two arrays	None
14	Search in a Rotated Array	None
15	Given a sorted and rotated array, find if there is a pair with a given sum	None
16	Max sum in the configuration	None
17	Array of alternate +ve and -ve no.s	Caution: When submitting the solution WA as they have not given clarity on how the array has to be change although the code changes the array as specified in the question
18	Three way partitioning	Dutch National Flag Quick Sort
19	Sort an array of 0s, 1s and 2s	Dutch National Flag Quick Sort
20	Maximum length Bitonic Subarray	In O(n) space
21	Maximum length Bitonic Subarray	In O(1) space
22	Count Square Submatrices with All Ones	None

Stacks

Index	Problem	Prerequisite
1	Largest Rectangle in Histogram	None
2	Stock Span Problem	None
3	Reverse a Stack without using extra space	Recursion
4	Delete middle element of stack	Recursion
5	Sort a Stack	Recursion
6	Sed Max	None
7	Move Brackets	None
8	Power Set	Recursion

Segment Trees

Index	Problem	Prerequisite
1	Range Minimum Query	None
2	Help Ashu	None

Greedy Algos

Index	Problem	Prerequisite
1	Activity Selection	Caution: Wrong test case on Geeks for Geeks
2	Egyptian Factors	Mathematics
3	Job Sequencing Problem	None
4	Water Connection Problem	None
5	Police Catch Thieves	None

DFS

Index	Problem	Prerequisite
1	Connected Components in a Graph	DFS on undirected graph
2	Bishu and his Girlfriend	DFS on undirected graph
3	Is it a tree	Graph and Tree knowledge
4	A Bug’s Life	Bipartite graphs
5	Fire Escape Routes	Connected Components
6	Counting Rooms	DFS on 2D grid
7	Longest path in a tree	Diameter of tree
8	A Walk to Remember	Kosaraju's algo
9	Maximum Size	DFS on 2D grid
10	Detect cycle in an undirected graph	DFS
11	Detect cycle in a directed graph	DFS
12	Tree House	DFS
13	Rat in maze Problem 1	DFS on 2D grid and Backtracking
14	Flood Fill	DFS on 2D grid
15	Number of Operations to Make Network Connected	Connected Components
16	Find the number of islands	Connected Components
17	Making A Large Island	DFS

BFS

Index	Problem	Prerequisite
1	Monk and the Islands	BFS on undirected graph
2	Prime Path	Sieve of Erosthenes and BFS
3	Feasible relations	BFS
4	Social Networking Graph	BFS
5	Jungle Run	BFS on 2D grid
6	Chess knight move	BFS on 2D grid
7	Bitmap	BFS on 2D grid
8	Lucius Dungeon	BFS on 2D grid
9	The Cats and the Mouse	BFS on 2D grid
10	Word Ladder	BFS
11	Jump Game VII	BFS
12	Minimum time taken by each job to be completed given by a Directed Acyclic Graph	Topological sorting
13	Topological Sort	Topological sorting
14	Find whether it is possible to finish all tasks or not from given dependencies	Topological sorting

Disjoint Set

Index	Problem	Prerequisite
1	Teacher's Dilemma	None
2	City and Flood	None
3	City and Campers	None
4	City and Fireman Vincent	None
5	City and Soldiers	None

Bit Manipulation

Index	Problem	Prerequisite
1	Number of 1 Bits	None
2	Non Repeating Numbers	None
3	Bit Difference	None
4	Power Set	None
5	Count Total Set Bits	None
6	And Then There Were K	None

Dynamic Programming

Index	Problem	Prerequisite
1	Increasing Subsequence	Basic Dp knowledge
2	Dice Combinations	Basic Dp knowledge
3	Minimizing Coins	Basic Dp knowledge
4	Coin Combinations I	Basic Dp knowledge
5	Coin Combinations II	Basic Dp knowledge
6	Removing Digits	Basic Dp knowledge
7	Grid Paths	Basic Dp knowledge
8	Book Shop	Basic Dp knowledge
9	Array Description	Basic Dp knowledge
10	Counting Towers	Basic Dp knowledge
11	Edit Distance	Basic Dp knowledge
12	Rectangle Cutting	Basic Dp knowledge
13	Money Sums	Basic Dp knowledge
14	Removal Game	Basic Dp knowledge
15	Two Sets II	Basic Dp knowledge
16	Projects	Basic Dp knowledge And Binary Search
17	Edit Distances	Basic Dp knowledge