Skip to content

Latest commit

 

History

History
135 lines (124 loc) · 12.4 KB

README.md

File metadata and controls

135 lines (124 loc) · 12.4 KB
Raw

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