GFG_DSA_SHEET

Arrays

• 1. Leaders in an array
• 2. Equilibrium point
• 3. Sort an array of 0s, 1s and 2s
• 4. Reverse array in groups
• 5. Convert array into Zig-Zag fashion
• 6. Rearrange array alternatively
• 7. Missing number in array
• 8. K-th element of two sorted Arrays
• 9. Check if two arrays are equal or not
• 10. Kadane’s Algorithm
• 11. Subarray with given sum
• 12. Trapping Rain Water
• 13. Minimum Platforms
• 14. Stock buy and sell
• 15. Largest Number formed from an Array
• 16. Largest subarray with 0 sum
• 17. Swapping pairs make sum equal

Searching and Sorting

• 1. Binary Search
• 2. Quick Sort
• 3. Merge Sort
• 4. Merge two sorted arrays without extra space
• 5. Inversion of Array
• 6. Search in a Rotated Array
• 7. Sorting Elements of an Array by Frequency
• 8. Sum of Middle Elements of two sorted arrays
• 9. K’th smallest element
• 10. Allocate minimum number of pages *

Hashing

• 1. First element to occur k times
• 2. Find the element that appears once in sorted array
• 3. Number of pairs *
• 4. Find all pairs with a given sum
• 5. Common elements
• 6. Find all four sum numbers
• 7. Count distinct elements in every window
• 8. Array Pair Sum Divisibility Problem
• 9. Longest consecutive subsequence
• 10. Array Subset of another array
• 11. Zero Sum Subarrays
• 12. Relative Sorting

Matrix

• 1. Rotate a matrix
• 2. Spirally traversing a matrix
• 3. Search in a row wise and column wise sorted matrix
• 4. Print all palindromic paths from top left to bottom right in a matrix
• 5.Find the row with maximum number of 1s
• 6. Find median in row wise sorted matrix
• 7. Check if all rows of a matrix are circular rotations of each other

String

• 1. Find first repeated character
• 2. Reverse words in a given string
• 3. Check if string is rotated by two places
• 4. Roman Number to Integer
• 5. Remove Duplicates
• 6. Longest Distinct Characters in the string
• 7. Implement Atoi
• 8. Implement strstr
• 9. Rabin Karp Algorithm
• 10. KMP Algorithm
• 11. Convert a Sentence into its equivalent mobile numeric keypad sequence.
• 12. Longest Common Prefix
• 13. Smallest window in a string containing all the characters of another string
• 14. Uncommon characters
• 15. Minimum indexed character

Recursion and Backtracking

• 1. Recursively remove all adjacent duplicates
• 2. Tower Of Hanoi
• 3. Special Keyboard
• 4. Permutations of a given string
• 5. N-Queen Problem
• 6. Solve the Sudoku
• 7. Rat in a Maze Problem
• 8. Word Boggle
• 9. Generate IP Addresses

Dynamic Programming

• 1. Minimum number of Coins
• 2. Longest Common Substring
• 3. Longest Increasing Subsequence
• 4. Longest Common Subsequence
• 5. 0-1 Knapsack Problem
• 6. Maximum sum increasing subsequence
• 7. Minimum number of jumps
• 8. Edit Distance
• 9. Coin Change Problem
• 10. Subset Sum Problem
• 11. Longest Palindrome in a String
• 12. Form a Palindrome
• 13. Box Stacking
• 14. Rod Cutting
• 15. Min Cost Path
• 16. Minimum sum partition
• 17. Count number of ways to cover a distance
• 18. Egg Dropping Puzzle

Greedy Approach

• 1. Activity Selection
• 2. N meetings in one room
• 3. Coin Piles
• 4. Maximize Toys
• 5. Page Faults in LRU
• 6. Largest number possible
• 7. Minimize the heights
• 8. Minimize the sum of product
• 9. Huffman Decoding
• 10. Minimum Spanning Tree

Graph

• 1. Depth First Traversal
• 2. Breadth First Traversal
• 3. Detect cycle in undirected graph
• 4. Detect cycle in a directed graph
• 5. Topological sort
• 6. Find the number of islands
• 7. Implementing Dijkstra
• 8. Minimum Swaps
• 9. Strongly Connected Components
• 10. Shortest Source to Destination Path
• 11. Find whether path exist
• 12. Minimum Cost Path
• 13. Circle of Strings
• 14. Floyd Warshall
• 15. Alien Dictionary
• 16. Snske and Ladder Problem

Trie

• 1. Trie | (Insert and Search)
• 2. Trie | (Delete)
• 3. Print unique rows in a given Binary matrix
• 4. Counting the number of words in a Trie
• 5. Longest Common Prefix using Trie
• 6. Auto-complete feature using Trie
• 7. Boggle | Set 2 (Using Trie)
• 8. Minimum XOR Value Pair
• 9. Palindrome pair in an array of words (or strings)

Heap

• 1. Heap Sort
• 2. Finad Median in a Stream
• 3. Operations on Binary Min Heap
• 4. Rearrange characters
• 5. Merge K sorted Linked lists
• 6. Kth smallest element in a row-column wise sorted matrix