ROADMAP TO DSA 450

I HAVE BEEN FOLOWING THIS SHEET GIVEN BY LOVE BABBAR

ARRAY

Q. Reverse the array ✅
Q. Find the maximum and minimum element in an array <✅>
Q. Find the "Kth" max and min element of an array <✅>
Q. Given an array which consists of only 0, 1 and 2. Sort the array without using any sorting algo <✅>
Q. Move all the negative elements to one side of the array <✅>
Q. Find the Union and Intersection of the two sorted arrays. <✅>
Q. Write a program to cyclically rotate an array by one. <✅>
Q. find Largest sum contiguous Subarray [V.IMP] <✅>
Q. Minimise the maximum difference between heights [V.IMP] <✅>
Q. Minimum-number-of-jumps to reach the end of Array<->
Q. find duplicate in an array of N+1 Integers <✅>
Q. Merge 2 sorted arrays without using Extra space. <✅>
Q. Kadane's Algo [V.V.V.V.V IMP] <✅>
Q. Merge Intervals <✅>
Q. Next Permutation <🔴>
Q. Count Inversion <🔴>
Q. Best time to buy and Sell stock <✅>
Q. find all pairs on integer array whose sum is equal to given number <✅>
Q. find common elements In 3 sorted arrays <✅>
Q. Rearrange the array in alternating positive and negative items with O(1) extra space <🔴>
Q. Find if there is any subarray with sum equal to 0 <✅>
Q. Find factorial of a large number <✅>
Q. find maximum product subarray <✅>
Q. Find longest coinsecutive subsequence <✅>
Q. Given an array of size n and a number k, fin all elements that appear more than " n/k " times. <✅>
Q. Maximum profit by buying and selling a share atmost twice <🔴>
Q. Find whether an array is a subset of another array <✅>
Q. Find the triplet that sum to a given value <✅>
Q. Trapping Rain water problem <✅>
Q. Chocolate Distribution problem <🔴>
Q. Smallest Subarray with sum greater than a given value <✅>
Q. Three way partitioning of an array around a given value <✅>
Q. Minimum swaps required bring elements less equal K together <✅>
Q. Minimum no. of operations required to make an array palindrome <✅>
Q. Median of 2 sorted arrays of equal size <✅>
Q. Median of 2 sorted arrays of different size <✅>

MATRIX

Q. Spiral traversal on a Matrix <->
Q. Search an element in a matriix <->
Q. Find median in a row wise sorted matrix <->
Q. Find row with maximum no. of 1's <->
Q. Print elements in sorted order using row-column wise sorted matrix <->
Q. Maximum size rectangle <->
Q. Find a specific pair in matrix <->
Q. Rotate matrix by 90 degrees <->
Q. Kth smallest element in a row-cpumn wise sorted matrix <->
Q. Common elements in all rows of a given matrix <->
Q. Rotate matrix element clockwise

STRING

SEARCHING AND SORTING

Q. Find first and last positions of an element in a sorted array <->
Q. Find a Fixed Point (Value equal to index) in a given array <->
Q. Search in a rotated sorted array <->
Q. square root of an integer <->
Q. Maximum and minimum of an array using minimum number of comparisons <->
Q. Optimum location of point to minimize total distance <->
Q. Find the repeating and the missing <->
Q. find majority element <->
Q. Searching in an array where adjacent differ by at most k <->
Q. find a pair with a given difference <->
Q. find four elements that sum to a given value <->
Q. maximum sum such that no 2 elements are adjacent <->
Q. Count triplet with sum smaller than a given value <->
Q. merge 2 sorted arrays <->
Q. print all subarrays with 0 sum <->
Q. Product array Puzzle <->
Q. Sort array according to count of set bits <->
Q. minimum no. of swaps required to sort the array <->
Q. Bishu and Soldiers <->
Q. Rasta and Kheshtak <->
Q. Kth smallest number again <->
Q. Find pivot element in a sorted array <->
Q. K-th Element of Two Sorted Arrays <->
Q. Aggressive cows <->
Q. Book Allocation Problem <->
Q. EKOSPOJ: <->
Q. Job Scheduling Algo <->
Q. Missing Number in AP <->
Q. Smallest number with atleastn trailing zeroes infactorial <->
Q. Painters Partition Problem: <->
Q. ROTI-Prata SPOJ <->
Q. DoubleHelix SPOJ <->
Q. Subset Sums <->
Q. Findthe inversion count <->
Q. Implement Merge-sort in-place <->
Q. Partitioning and Sorting Arrays with Many Repeated Entries <->

LINKEDLIST

Q. Write a Program to reverse the Linked List. (Both Iterative and recursive) <->
Q. Reverse a Linked List in group of Given Size. [Very Imp] <->
Q. Write a program to Detect loop in a linked list. <->
Q. Write a program to Delete loop in a linked list. <->
Q. Find the starting point of the loop.  <->
Q. Remove Duplicates in a sorted Linked List. <->
Q. Remove Duplicates in a Un-sorted Linked List. <->
Q. Write a Program to Move the last element to Front in a Linked List. <->
Q. Add “1” to a number represented as a Linked List. <->
Q. Add two numbers represented by linked lists. <->
Q. Intersection of two Sorted Linked List. <->
Q. Intersection Point of two Linked Lists. <->
Q. Merge Sort For Linked lists.[Very Important] <->
Q. Quicksort for Linked Lists.[Very Important] <->
Q. Find the middle Element of a linked list. <->
Q. Check if a linked list is a circular linked list. <->
Q. Split a Circular linked list into two halves. <->
Q. Write a Program to check whether the Singly Linked list is a palindrome or not. <
-> Q. Deletion from a Circular Linked List. <->
Q. Reverse a Doubly Linked list. <->
Q. Find pairs with a given sum in a DLL. <->
Q. Count triplets in a sorted DLL whose sum is equal to given value “X”. <->
Q. Sort a “k”sorted Doubly Linked list.[Very IMP] <->
Q. Rotate DoublyLinked list by N nodes. <->
Q. Rotate a Doubly Linked list in group of Given Size.[Very IMP] <->
Q. Can we reverse a linked list in less than O(n) ? <->
Q. Why Quicksort is preferred for. Arrays and Merge Sort for LinkedLists ? <->
Q. Flatten a Linked List <->
Q. Sort a LL of 0's, 1's and 2's <->
Q. Clone a linked list with next and random pointer <->
Q. Merge K sorted Linked list <->
Q. Multiply 2 no. represented by LL <->
Q. Delete nodes which have a greater value on right side <->
Q. Segregate even and odd nodes in a Linked List <->
Q. Program for n’th node from the end of a Linked List <->
Q. Find the first non-repeating character from a stream of characters <->

BINARY TREE

Q. level order traversal <->
Q. Reverse Level Order traversal <->
Q. Height of a tree <->
Q. Diameter of a tree <->
Q. Mirror of a tree <->
Q. Inorder Traversal of a tree both using recursion and Iteration <->
Q. Preorder Traversal of a tree both using recursion and Iteration <->
Q. Postorder Traversal of a tree both using recursion and Iteration <->
Q. Left View of a tree <->
Q. Right View of Tree <->
Q. Top View of a tree <->
Q. Bottom View of a tree <->
Q. Zig-Zag traversal of a binary tree <->
Q. Check if a tree is balanced or not <->
Q. Diagnol Traversal of a Binary tree <->
Q. Boundary traversal of a Binary tree <->
Q. Construct Binary Tree from String with Bracket Representation <->
Q. Convert Binary tree into Doubly Linked List <->
Q. Convert Binary tree into Sum tree <->
Q. Construct Binary tree from Inorder and preorder traversal <->
Q. Find minimum swaps required to convert a Binary tree into BST <->
Q. Check if Binary tree is Sum tree or not <->
Q. Check if all leaf nodes are at same level or not <->
Q. Check if a Binary Tree contains duplicate subtrees of size 2 or more [ IMP ] <->
Q. Check if 2 trees are mirror or not <->
Q. Sum of Nodes on the Longest path from root to leaf node <->
Q. Check if given graph is tree or not. [ IMP ] <->
Q. Find Largest subtree sum in a tree <->
Q. Maximum Sum of nodes in Binary tree such that no two are adjacent <->
Q. Print all "K" Sum paths in a Binary tree <->
Q. Find LCA in a Binary tree <->
Q. Find distance between 2 nodes in a Binary tree <->
Q. Kth Ancestor of node in a Binary tree <->
Q. Find all Duplicate subtrees in a Binary tree [ IMP ] <->
Q. Tree Isomorphism Problem <->

BINARY SEARCH TREE

Q. Fina a value in a BST <->
Q. Deletion of a node in a BST <->
Q. Find min and max value in a BST <->
Q. Find inorder successor and inorder predecessor in a BST <->
Q. Check if a tree is a BST or not <->
Q. Populate Inorder successor of all nodes <->
Q. Find LCA of 2 nodes in a BST <->
Q. Construct BST from preorder traversal <->
Q. Convert Binary tree into BST <->
Q. Convert a normal BST into a Balanced BST <->
Q. Merge two BST [ V.V.V>IMP ] <->
Q. Find Kth largest element in a BST <->
Q. Find Kth smallest element in a BST <->
Q. Count pairs from 2 BST whose sum is equal to given value "X" <->
Q. Find the median of BST in O(n) time and O(1) space <->
Q. Count BST ndoes that lie in a given range <->
Q. Replace every element with the least greater element on its right <->
Q. Given "n" appointments, find the conflicting appointments <->
Q. Check preorder is valid or not <->
Q. Check whether BST contains Dead end <->
Q. Largest BST in a Binary Tree [ V.V.V.V.V IMP ] <->
Q. Flatten BST to sorted list <->

GREEDY

Q. Activity Selection Problem <✅>
Q. Job SequencingProblem <✅>
Q. Huffman Coding <->
Q. Water Connection Problem <->
Q. Fractional Knapsack Problem <✅> Q. Greedy Algorithm to find Minimum number of Coins <✅>
Q. Choose and Swap <✅>
Q. Maximum trains for which stoppage can be provided <->
Q. Minimum Platforms Problem <✅>
Q. Buy Maximum Stocks if i stocks can be bought on i-th day <->
Q. Find the minimum and maximum amount to buy all N candies <->
Q. Minimize Cash Flow among a given set of friends who have borrowed money from each other <->
Q. Minimum Cost to cut a board into squares <->
Q. Check if it is possible to survive on Island <->
Q. Find maximum meetings in one room <->
Q. Maximum product subset of an array <->
Q. Maximize array sum after K negations <->
Q. Maximize the sum of arr[i].i <->
Q. Maximum sum of absolute difference of an array <->
Q. Maximize sum of consecutive differences in a circular array <->
Q. Minimum sum of absolute difference of pairs of two arrays <->
Q. Program for Shortest Job First (or SJF) CPU Scheduling <->
Q. Program for Least Recently Used (LRU) Page Replacement algorithm <->
Q. Smallest subset with sum greater than all other elements <->
Q. Chocolate Distribution Problem <->
Q. DEFKIN -Defense of a Kingdom <->
Q. DIEHARD -DIE HARD <->
Q. GERGOVIA -Wine trading in Gergovia <->
Q. Picking Up Chicks <->
Q. CHOCOLA –Chocolate <->
Q. ARRANGE -Arranging Amplifiers <->
Q. K Centers Problem <->
Q. Minimum Cost of ropes <->
Q. Find smallest number with given number of digits and sum of digits <->
Q. Rearrange characters in a string such that no two adjacent are same <->
Q. Find maximum sum possible equal sum of three stacks <->

BACKTRACKING

Q. Rat in a maze Problem <->
Q. Printing all solutions in N-Queen Problem <->
Q. Word Break Problem using Backtracking <->
Q. Remove Invalid Parentheses <->
Q. Sudoku Solver <->
Q. m Coloring Problem <->
Q. Print all palindromic partitions of a string <->
Q. Subset Sum Problem <->
Q. The Knight’s tour problem <->
Q. Tug of War <->
Q. Find shortest safe route in a path with landmines <->
Q. Combinational Sum <->
Q. Find Maximum number possible by doing at-most K swaps <->
Q. Print all permutations of a string <->
Q. Find if there is a path of more than k length from a source <->
Q. Longest Possible Route in a Matrix with Hurdles <->
Q. Print all possible paths from top left to bottom right of a mXn matrix <->
Q. Partition of a set intoK subsets with equal sum <->
Q. Find the K-th Permutation Sequence of first N natural numbers <->

STACK AND QUEUE

Q. Implement Stack from Scratch <->
Q. Implement Queue from Scratch <->
Q. Implement 2 stack in an array <->
Q. find the middle element of a stack <->
Q. Implement "N" stacks in an Array <->
Q. Check the expression has valid or Balanced parenthesis or not. <->
Q. Reverse a String using Stack <->
Q. Design a Stack that supports getMin() in O(1) time and O(1) extra space. <->
Q. Find the next Greater element <->
Q. The celebrity Problem <->
Q. Arithmetic Expression evaluation <->
Q. Evaluation of Postfix expression <->
Q. Implement a method to insert an element at its bottom without using any other data structure. <->
Q. Reverse a stack using recursion <->
Q. Sort a Stack using recursion <->
Q. Merge Overlapping Intervals <->
Q. Largest rectangular Area in Histogram <->
Q. Length of the Longest Valid Substring <->
Q. Expression contains redundant bracket or not <->
Q. Implement Stack using Queue <->
Q. Implement Stack using Deque <->
Q. Stack Permutations (Check if an array is stack permutation of other) <->
Q. Implement Queue using Stack <->
Q. Implement "n" queue in an array <->
Q. Implement a Circular queue <->
Q. LRU Cache Implementationa <->
Q. Reverse a Queue using recursion <->
Q. Reverse the first “K” elements of a queue <->
Q. Interleave the first half of the queue with second half <->
Q. Find the first circular tour that visits all Petrol Pumps <->
Q. Minimum time required to rot all oranges <->
Q. Distance of nearest cell having 1 in a binary matrix <->
Q. First negative integer in every window of size “k” <->
Q. Check if all levels of two trees are anagrams or not. <->
Q. Sum of minimum and maximum elements of all subarrays of size “k”. <->
Q. Minimum sum of squares of character counts in a given string after removing “k” characters. <->
Q. Queue based approach or first non-repeating character in a stream. <->
Q. Next Smaller Element <->

HAEP

Q. Implement a Maxheap/MinHeap using arrays and recursion. <->
Q. Sort an Array using heap. (HeapSort) <->
Q. Maximum of all subarrays of size k. <->
Q. “k” largest element in an array <->
Q. Kth smallest and largest element in an unsorted array <->
Q. Merge “K” sorted arrays. [ IMP ] <->
Q. Merge 2 Binary Max Heaps <->
Q. Kth largest sum continuous subarrays <->
Q. Leetcode- reorganize strings <->
Q. Merge “K” Sorted Linked Lists [V.IMP] <->
Q. Smallest range in “K” Lists <->
Q. Median in a stream of Integers <->
Q. Check if a Binary Tree is Heap <->
Q. Connect “n” ropes with minimum cost <->
Q. Convert BST to Min Heap <->
Q. Convert min heap to max heap <->
Q. Rearrange characters in a string such that no two adjacent are same. <->
Q. Minimum sum of two numbers formed from digits of an array

GRAPH

Q. Create a Graph, print it <->
Q. Implement BFS algorithm <->
Q. Implement DFS Algo <->
Q. Detect Cycle in Directed Graph using BFS/DFS Algo <->
Q. Detect Cycle in UnDirected Graph using BFS/DFS Algo <->
Q. Search in a Maze <->
Q. Minimum Step by Knight <->
Q. flood fill algo <->
Q. Clone a graph <->
Q. Making wired Connections <->
Q. word Ladder <->
Q. Dijkstra algo <->
Q. Implement Topological Sort <->
Q. Minimum time taken by each job to be completed given by a Directed Acyclic Graph <->
Q. Find whether it is possible to finish all tasks or not from given dependencies <->
Q. Find the no. of Isalnds <->
Q. Given a sorted Dictionary of an Alien Language, find order of characters <->
Q. Implement Kruksal’sAlgorithm <->
Q. Implement Prim’s Algorithm <->
Q. Total no. of Spanning tree in a graph <->
Q. Implement Bellman Ford Algorithm <->
Q. Implement Floyd warshallAlgorithm <->
Q. Travelling Salesman Problem <->
Q. Graph ColouringProblem <->
Q. Snake and Ladders Problem <->
Q. Find bridge in a graph <->
Q. Count Strongly connected Components(Kosaraju Algo) <->
Q. Check whether a graph is Bipartite or Not <->
Q. Detect Negative cycle in a graph <->
Q. Longest path in a Directed Acyclic Graph <->
Q. Journey to the Moon <->
Q. Cheapest Flights Within K Stops <->
Q. Oliver and the Game <->
Q. Water Jug problem using BFS <->
Q. Water Jug problem using BFS <->
Q. Find if there is a path of more thank length from a source <->
Q. M-ColouringProblem <->
Q. Minimum edges to reverse o make path from source to destination <->
Q. Paths to travel each nodes using each edge(Seven Bridges) <->
Q. Vertex Cover Problem <->
Q. Chinese Postman or Route Inspection <->
Q. Number of Triangles in a Directed and Undirected Graph <->
Q. Minimise the cashflow among a given set of friends who have borrowed money from each other <->
Q. Two Clique Problem <->

DYNAMIC PROGRAMMING

Q. Coin ChangeProblem <->
Q. Knapsack Problem <->
Q. Binomial CoefficientProblem <->
Q. Permutation CoefficientProblem <->
Q. Program for nth Catalan Number <->
Q. Matrix Chain Multiplication  <->
Q. Edit Distance <->
Q. Subset Sum Problem <->
Q. Friends Pairing Problem <->
Q. Gold Mine Problem <->
Q. Assembly Line SchedulingProblem <->
Q. Painting the Fenceproblem <->
Q. Maximize The Cut Segments <->
Q. Longest Common Subsequence <->
Q. Longest Repeated Subsequence <->
Q. Longest Increasing Subsequence <->
Q. Space Optimized Solution of LCS <->
Q. LCS (Longest Common Subsequence) of three strings <->
Q. Maximum Sum Increasing Subsequence <->
Q. Count all subsequences having product less than K <->
Q. Longest subsequence such that difference between adjacent is one <->
Q. Maximum subsequence sum such that no three are consecutive <->
Q. Egg Dropping Problem <->
Q. Maximum Length Chain of Pairs <->
Q. Maximum size square sub-matrix with all 1s <->
Q. Maximum sum of pairs with specific difference <->
Q. Min Cost PathProblem <->
Q. Maximum difference of zeros and ones in binary string <->
Q. Minimum number of jumps to reach end <->
Q. Minimum cost to fill given weight in a bag <->
Q. Minimum removals from array to make max –min <= K <->
Q. Longest Common Substring <->
Q. Count number of ways to reacha given score in a game <->
Q. Count Balanced Binary Trees of Height h <->
Q. LargestSum Contiguous Subarray [V>V>V>V IMP ] <->
Q. Smallest sum contiguous subarray <->
Q. Unbounded Knapsack (Repetition of items allowed) <->
Q. Word Break Problem <->
Q. Largest Independent Set Problem <->
Q. Partition problem <->
Q. Longest Palindromic Subsequence <->
Q. Count All Palindromic Subsequence in a given String <->
Q. Longest Palindromic Substring <->
Q. Longest alternating subsequence <->
Q. Weighted Job Scheduling <->
Q. Coin game winner where every player has three choices <->
Q. Count Derangements (Permutation such that no element appears in its original position) [ IMPORTANT ] <->
Q. Maximum profit by buying and selling a share at most twice [ IMP ] <->
Q. Optimal Strategy for a Game <->
Q. Optimal Binary Search Tree <->
Q. Palindrome PartitioningProblem <->
Q. Word Wrap Problem <->
Q. Mobile Numeric Keypad Problem [ IMP ] <->
Q. Boolean Parenthesization Problem <->
Q. Largest rectangular sub-matrix whose sum is 0 <->
Q. Largest area rectangular sub-matrix with equal number of 1’s and 0’s [ IMP ] <->
Q. Maximum sum rectangle in a 2D matrix <->
Q. Maximum profit by buying and selling a share at most k times <->
Q. Find if a string is interleaved of two other strings <->
Q. Maximum Length of Pair Chain <->

BIT MANIPULATION

Q. Count set bits in an integer <✅>
Q. Find the two non-repeating elements in an array of repeating elements <✅>
Q. Count number of bits to be flipped to convert A to B <✅>
Q. Count total set bits in all numbers from 1 to n <✅>
Q. Program to find whether a no is power of two <✅>
Q. Find position of the only set bit <✅>
Q. Copy set bits in a range <✅>
Q. Divide two integers without using multiplication, division and mod operator <->
Q. Calculate square of a number without using *, / and pow() <->
Q. Power Set <✅>