manohar2000/dsa_450

DSA_450

List of 450 Questions for Data Structures and Algorithms Preparation

Link to the YouTube video for motivation : view

Link to Placement Series : view
Link to Competitive Programming Series : view

Arrays

Sno	Topic Name	My Solution	Logic Used	Date Completed
1	Reverse array	view	One index from start another from the last and swap continuously	13th Dec
2	Find max/min	view	Divide and conquer	13th Dec
3	Find max/min	view	Pairs	13th Dec
4	Kth max/min	view	In-built merge sort	13th Dec
5	Trapping Rain water	view	min_of_height(building_in_left,buildings_in_right) - curr_height	16th Dec
6	Sort array of 0,1 and 2	view	Count and replace	1st March
7	Sort such that all neg elements come before pos elements	view	Partitioning of quick sort	1st March
8	Power of N(large N)	view	Right shift and bitwise AND operator	3rd March
9	Rotate array by K positions	view	GCD; juggling algo	5th March
10	Min Heights	view	Sorting; iterating and updating small and large vars	6th March
11	Next Permutation	view	Finding the break in decreasing seq from last, swapping with next greatest element and reversing the array	7th March
12	find duplicate elements in array	view	Floyd cycle detection algo	7th March
13	Rotation of array by K	view	Juggling algorithm	7th March
14	Jump Game 2	view	Top-down dp; 3 vars that keep a count of jumps, steps and maxReach	8th March
15	Merge 2 sorted arrays without extra space	view	Step algorithm	8th March
16	Merge Intervals	view	Consecutively comparing the end interval of curr and start interval of next set	9th March
17	Count Inversions	view	Enhanced merge sort	10th March
18	Buy Sell Stock	view	2 variables to keep a track of the min element and max diff	11th March
19	Count Pairs sum equal to K	view	Hashing	11th March
20	Common Elements in 3 sorted arrays	view	Variable to keep a track of the previous common element and 3 pointers for each of the array	11th March
21	Rearrange array in alternating pos/neg elements	view	Partitioning followed by swapping	13th March
22	Factorial of a large number	view	Storing results in array rather a interger	14th March
23	len of longest consecutive numbers in an array	view	storing all numbers in a set and referencing from it	16th March
24	Max product subarray	view	storing min and max element and iterating through the array	16th March
25	Triplet in array with sum K exists or not	view	sort array and 2 pointer approach	17th March
26	Majority Element	view	creating a array of k-1 elements and using a tetris like approach to store and replace elements. Lastly checking the occurences of the elements in the temp array	17th March
27	Max Circular Subarray Sum	view	max(kadane's algo, (sumofArray + maxsubrray sum of inverted array))	18th March
28	Smallest subarray with sum greater than x	view	two pointer approach	18th April
29	Three way partition	view	Dutch National Flag algo(two pointer approach)	18th April
30	Median of 2 sorted arrays	view	min1,max1 and min2,max2 such max1<=min2 and max2<=min1	19th April

Matrix

Sno	Topic Name	My Solution	Logic Used	Other better approaches	All approaches	Date Completed
1	Spiral traversal	@spiral_print	4 indices in 4 corners of the matrix	DFS recurisve	@spiralPrint	14th Dec
2	Search an element	@staircase	start top right, if curr>k j-=1 else i+=1	-	@searching	14th Dec
3	Rotate matrix by 90 degrees	@rotation	Reverse rows/columns then transpose	-	@rotation	14th Dec

Strings

Sno	Topic Name	My Solution	Logic Used	Date Completed
1	Geneate all Sub seuqneces	view	recursion	26th May

Searching and Sorting

Sno	Topic Name	My Solution	Logic Used	Date Completed

Linked List

Sno	Topic Name	My Solution	Logic Used	Date Completed

Binary Trees

Sno	Topic Name	My Solution	Logic Used	Date Completed
1	Level Order Traversal	view	queue	13th March
2	Reverse Level Order Traversal	view	queue and stack	20th Feb
3	Height of a Tree	view	recursion	13th March
4	Diameter of a Tree	view	diameter can lie in 3 places	13th March
5	Mirror of a Tree	view	recursion	20th Feb
6	Inorder Iterative	view
7	Preorder Iterative	view
8	Postorder Iterative	view
9	Left View	view
10	Top View	view
11	Bottom View	view
12	Zig-Zag Traversal	view
13	Tree balanced or not	view
14	Diagonal Traversal	view
15	Binary Tree into DLL	view
16	Find LCA	view

Binary Search Trees

Sno	Topic Name	My Solution	Logic Used	Date Completed

Greedy Algorithms

Sno	Topic Name	My Solution	Logic Used	Date Completed
1	Fractional Knapsack	view	selecting items based on value/weight ratio	24th May

Backtracking

Sno	Topic Name	My Solution	Logic Used	Date Completed

Stacks and Queues

Sno	Topic Name	My Solution	Logic Used	Date Completed

Heap

Sno	Topic Name	My Solution	Logic Used	Date Completed

Graph

Sno	Topic Name	My Solution	Logic Used	Date Completed
1	Creating a graph with weighted edges	view	map<vector<T,int>>	22nd April
2	BFS traversal	view	queue and a map for visited nodes	22nd April
3	DFS traversal	view	recursion and map for visited nodes	23rd April
4	Cyclce Detection using DFS	view	instack and visited map	24th April
5	Cycle Detection using BFS	view	counting the incoming edges and queue	24th April
6	Cycle Detection in an undirected graph using DFS	view	recursion and visited map	26th April
7	Cycle Detection in an undirected graph using BFS	view	queue and visited map	26th April
8	Dijkstra Algorithm	view	using distance array and set to access the node with lowest distance	26th April
9	Topological Sort using BFS	view	Kahn’s algorithm-counting the total no. of incoming nodes and queue	26th April
10	Find the number of islands	view	bfs traversal	27th April
11	Alien Dictionary	view	making a graph for mismatched chars for every cons words and topological sort	28th April
12	Strongly Connected Components	view	kosaraju's algorithm	28th April
13	Floyd Warshal algorithm	view	floyd warshall algo	28th April
14	Graph Coloring problem	view	array of alloted colors and available colors	29th April
15	Snakes and Ladders	view	single shortest path using bfs	1st May
16	Travelling salesman problem	view	dynamic programming	1st May

Trie

Sno	Topic Name	My Solution	Logic Used	Date Completed

Dynamic Programming(Pep Coding)

Sno	Topic Name	My Solution	Logic Used	Date Completed
1	Climb Stairs With Minimum Moves	view	bottom up DP	23rd May
2	Target Sum	view	2d dp array	23rd May
3	Coin Change Combinations	view	DP array where each state represents ways to achieve the curr den using ith denom	23rd May
4	Coin Change Permutations	view	DP array where each state represents total permutations for that target	23rd May
5	0-1 Knapsack	view	2d dp array where each state represents max value that can achieved using weights till the ith weight	24th May
6	Unbounded Knapsack	view	1d dp array. for each target knapsack we check with all the weights and replace it with the maximum value	24th May

Bit Manipulation

Sno	Topic Name	My Solution	Logic Used	Date Completed