DSA Crack Sheet
Array
- Reverse the array
- Maximum and minimum of an array using minimum number of comparisons
- Kth smallest element - Cpp Solution
- Sort an array of 0s, 1s and 2s - Cpp Solution
- Move all negative numbers to beginning and positive to end with constant extra space
- Union of two arrays - Cpp Solution
- Cyclically rotate an array by one - Cpp Solution
- Kadane's Algorithm - Cpp Solution
- Minimum number of jumps - Cpp Solution
- Find the Duplicate Number - Cpp Solution
- Merge Intervals - Cpp Solution
- Next Permutation - Cpp Solution
- Count Inversions - Cpp Solution
- Best Time to Buy and Sell Stock - Cpp Solution
- Count pairs with given sum - Cpp Solution
- Common elements - Cpp Solution
- Rearrange array in alternating positive & negative items with O(1) extra space - Cpp Solution
- Subarray with 0 sum - Cpp Solution
- Factorials of large numbers - Cpp Solution
- Maximum Product Subarray - Cpp Solution
- Longest consecutive subsequence - Cpp Solution
- Given an array of size n and a number k, find all elements that appear more than n/k times
- Best Time to Buy and Sell Stock III - Cpp Solution
- Array Subset of another array - Cpp Solution
- Triplet Sum in Array - Cpp Solution
- Trapping Rain Water - Cpp Solution
- Chocolate Distribution Problem - Cpp Solution
- Smallest subarray with sum greater than x - Cpp Solution
- Three way partitioning - Cpp Solution
- Minimum swaps and K together - Cpp Solution
- Find minimum number of merge operations to make an array palindrome
- Median of two sorted arrays of same size
- Median of two sorted arrays of different sizes
Matrix
- Spirally traversing a matrix - Cpp Solution
- Search a 2D Matrix - Cpp Solution
- Median in a row-wise sorted Matrix - Cpp Solution
- Row with max 1s - Cpp Solution
- Sorted matrix - Cpp Solution
- Max rectangle - Cpp Solution
- Find a specific pair in Matrix
- Rotate a matrix by 90 degree in clockwise direction without using any extra space
- Kth element in Matrix - Cpp Solution
- Common elements in all rows of a given matrix
Strings
- Reverse String - Cpp Solution
- Palindrome String - Cpp Solution
- Print all the duplicates in the input string
- Why strings are immutable in Java?
- Check if strings are rotations of each other or not - Cpp Solution
- Program to Check if a string is a valid shuffle of two distinct strings
- Count and Say - Cpp Solution
- Longest Palindromic Substring - Cpp Solution
- Print all subsequences of a string
- Longest Repeating Subsequence - Cpp Solution
- Permutations of a given string - Cpp Solution
- Split the binary string into substrings with equal number of 0s and 1s
- Edit Distance - Cpp Solution
- Next Permutation - Cpp Solution
- Parenthesis Checker - Cpp Solution
- Word Break - Cpp Solution
- Rabin-Karp Algorithm for Pattern Searching
- KMP Algorithm for Pattern Searching
- Longest Prefix Suffix - Cpp Solution
- Convert a sentence into its equivalent mobile numeric keypad sequence - Cpp Solution
- Count the Reversals - Cpp Solution
- Count Palindromic Subsequences - Cpp Solution
- Find the string in grid - Cpp Solution
- Roman Number to Integer - Cpp Solution
- Longest Common Prefix - Cpp Solution
- Min Number of Flips - Cpp Solution
- Second most repeated string in a sequence - Cpp Solution
- Minimum Swaps for Bracket Balancing - Cpp Solution
- Longest Common Subsequence - Cpp Solution
- Program to generate all possible valid IP addresses from given string
- Smallest distinct window - Cpp Solution
- Rearrange characters - Cpp Solution
- Minimum characters to be added at front to make string palindrome
- Print Anagrams Together - Cpp Solution
- Remove Consecutive Characters - Cpp Solution
Searching & Sorting
- First and last occurrences of X - Cpp Solution
- Value equal to index value - Cpp Solution
- Search in Rotated Sorted Array - Cpp Solution
- Count Squares - Cpp Solution
- Square root of an integer
- Middle of Three - Cpp Solution
- Optimum location of point to minimize total distance
- Find Missing And Repeating - Cpp Solution
- Majority Element - Cpp Solution
- Searching in an array where adjacent differ by at most k
- Find Pair Given Difference - Cpp Solution
- Find All Four Sum Numbers - Cpp Solution
- Stickler Thief - Cpp Solution
- Count triplets with sum smaller than X - Cpp Solution
- Merge Without Extra Space - Cpp Solution
- Zero Sum Subarrays - Cpp Solution
- Product array puzzle - Cpp Solution
- Sort by Set Bit Count - Cpp Solution
- Minimum Swaps to Sort - Cpp Solution
- Bishu and Soldiers - Cpp Solution
- Kth smallest number again - Cpp Solution
- Find pivot element in a sorted and rotated array
- Find Minimum in Rotated Sorted Array - Cpp Solution
- K-th element of two sorted Arrays - Cpp Solution
- AGGRCOW - Aggressive cows - Cpp Solution
- Allocate minimum number of pages - Cpp Solution
- Capacity To Ship Packages Within D Days - Cpp Solution
Linked-List
- Reverse a linked list - Cpp Solution
- Reverse a Linked List in groups of given size - Cpp Solution
- Detect Loop in linked list - Cpp Solution
- Remove loop in Linked List - Cpp Solution
- Find first node of loop in a linked list
- Remove duplicate element from sorted Linked List - Cpp Solution
- Remove duplicates from an unsorted linked list - Cpp Solution
- Move last element to front of a given Linked List
- Add 1 to a number represented as linked list - Cpp Solution
- Add two numbers represented by linked lists - Cpp Solution
- Intersection of two sorted Linked lists - Cpp Solution
- Intersection Point in Y Shapped Linked Lists - Cpp Solution
- Middle of the Linked List - Cpp Solution
- Merge Sort for Linked List - Cpp Solution
- Quick Sort on Linked List - Cpp Solution
- Check If Circular Linked List - Cpp Solution
- Split a Circular Linked List into two halves - Cpp Solution
- Check if Linked List is Palindrome - Cpp Solution
- Deletion from a Circular Linked List
- Reverse a Doubly Linked List - Cpp Solution
- Find pairs with given sum in doubly linked list
- Count triplets in a sorted doubly linked list whose sum is equal to a given value x
- Sort a k sorted doubly linked list
- Rotate Doubly linked list by N nodes
- Reverse a doubly linked list in groups of given size
- Can we reverse a linked list in less than O(n)?
- Why Quick Sort preferred for Arrays and Merge Sort for Linked Lists?
- Flattening a Linked List - Cpp Solution
- Given a linked list of 0s, 1s and 2s, sort it - Cpp Solution
- Clone a linked list with next and random pointer - Cpp Solution
- Merge K sorted linked lists - Cpp Solution
- Multiply two linked lists - Cpp Solution
- Delete nodes having greater value on right - Cpp Solution
- Segregate even and odd nodes in a Link List - Cpp Solution
- Nth node from end of linked list - Cpp Solution
- First non-repeating character in a stream - Cpp Solution
Binary Tree
- Level order traversal - Cpp Solution
- Reverse Level Order Traversal - Cpp Solution
- Height of Binary Tree - Cpp Solution
- Diameter of Binary Tree - Cpp Solution
- Create a mirror tree from the given binary tree
- Inorder Tree Traversal - Iterative and Recursive
- Preorder Tree Traversal - Iterative and Recursive
- Postorder Tree Traversal - Iterative and Recursive
- Left View of Binary Tree - Cpp Solution
- Right View of Binary Tree - Cpp Solution
- Top View of Binary Tree - Cpp Solution
- Bottom View of Binary Tree - Cpp Solution
- ZigZag Tree Traversal - Cpp Solution
- Check for Balanced Tree - Cpp Solution
- Diagonal Traversal of Binary Tree - Cpp Solution
- Boundary Traversal of binary tree - Cpp Solution
- Construct Binary Tree from String with bracket representation
- Binary Tree to DLL - Cpp Solution
- Transform to Sum Tree - Cpp Solution
- Construct Tree from Inorder & Preorder - Cpp Solution
- Minimum swap required to convert binary tree to binary search tree
- Sum Tree - Cpp Solution
- Leaf at same level - Cpp Solution
- Duplicate subtree in Binary Tree - Cpp Solution
- Check Mirror in N-ary tree - Cpp Solution
- Sum of the Longest Bloodline of a Tree (Sum of nodes on the longest path from root to leaf node) - Cpp Solution
- Check if a given graph is tree or not
- Find largest subtree sum in a tree
- Maximum sum of nodes in Binary tree such that no two are adjacent
- Print all k-sum paths in a binary tree
- Lowest Common Ancestor in a Binary Tree - Cpp Solution
- Min distance between two given nodes of a Binary Tree - Cpp Solution
- Kth ancestor of a node in binary tree
- Duplicate Subtrees - Cpp Solution
- Check if Tree is Isomorphic - Cpp Solution
- Print Right View of a Binary Tree
Binary Search Tree
- Binary Search Tree (Search and Insertion)
- Delete Node in a BST - Cpp Solution
- Minimum element in BST - Cpp Solution
- Predecessor and Successor - Cpp Solution
- Check for BST - Cpp Solution
- Populate Inorder Successor for all nodes - Cpp Solution
- Lowest Common Ancestor in a BST - Cpp Solution
- Construct BST from given preorder traversal
- Binary Tree to BST - Cpp Solution
- Convert a normal BST to Balanced BST
- Merge Two Balanced Binary Search Trees
- Kth largest element in BST - Cpp Solution
- k-th smallest element in BST - Cpp Solution
- Brothers From Different Roots - Cpp Solution
- Inorder Tree Traversal without recursion and without stack!
- Find median of BST in O(n) time and O(1) space
- Count BST nodes that lie in a given range - Cpp Solution
- Replace every element with the least greater element on its right
- Given n appointments, find all conflicting appointments
- Preorder to BST - Cpp Solution
- Check whether BST contains Dead End - Cpp Solution
- Flatten BST to sorted list
- Largest BST - Cpp Solution
Greedy Method
- N meetings in one room - Cpp Solution
- Job Sequencing Problem - Cpp Solution
- Huffman Encoding - Cpp Solution
- Fractional Knapsack - Cpp Solution
- Choose and Swap - Cpp Solution
- Greedy Algorithm to find Minimum number of Coins
- []( "view question") - Cpp Solution
Backtracking
- Rat in a Maze Problem - Cpp Solution
- N-Queens II - Cpp Solution
- N-Queens - Cpp Solution
- Word Break - Part 2 - Cpp Solution
- Remove Invalid Parentheses - Cpp Solution
- Sudoku Solver - Cpp Solution
- M-Coloring Problem - Cpp Solution
- Palindrome Partitioning - Cpp Solution
- Partition Equal Subset Sum - Cpp Solution
- The Knight's tour problem
- Tug of War
- Find shortest safe route in a path with landmines
- Combination Sum - Cpp Solution
- Largest number in K swaps - Cpp Solution
- Permutations of a given string - Cpp Solution
- Find if there is a path of more than k length from a source
- Longest Possible Route in a Matrix with Hurdles
- Print all possible paths from top left to bottom right of a mXn matrix
- Partition array to K subsets - Cpp Solution
- Find the K-th Permutation Sequence of first N natural numbers
Stacks & Queues
- Implement stack using array - Cpp Solution
- Implement Queue using array - Cpp Solution
- Implement two stacks in an array - Cpp Solution
- Design a stack with operations on middle element - Cpp Solution
- How to efficiently implement k stacks in a single array?
- Parenthesis Checker - Cpp Solution
- Reverse a string using Stack - Cpp Solution
- Special Stack - Cpp Solution
- Next Greater Element - Cpp Solution
- The Celebrity Problem - Cpp Solution
- Arithmetic Expression Evaluation
- Evaluation of Postfix Expression - Cpp Solution
- Inserting at the end of stack
- Reverse a stack using recursion
- Sort a stack - Cpp Solution
- Merge Intervals - Cpp Solution
- Maximum Rectangular Area in a Histogram - Cpp Solution
- Valid Substring - Cpp Solution
- Expression contains redundant bracket or not
- Stack using two queues - Cpp Solution
- Implement Stack and Queue using Deque
- Stack Permutations (Check if an array is stack permutation of other)
- Queue using two Stacks - Cpp Solution
- How to efficiently implement k Queues in a single array?
- Circular Queue
- LRU Cache - Cpp Solution
- Queue Reversal - Cpp Solution
- Reverse First K elements of Queue - Cpp Solution
- Interleave the first half of the queue with second half
- Circular tour - Cpp Solution
- Rotten Oranges - Cpp Solution
- Distance of nearest cell having 1 - Cpp Solution
- First negative integer in every window of size k - Cpp Solution
- Check if all levels of two trees are anagrams or not
- Maximum of all subarrays of size k - Cpp Solution
- Sum of minimum and maximum elements of all subarrays of size k
- Game with String - Cpp Solution
- First non-repeating character in a stream - Cpp Solution
- Next Greater Element - Cpp Solution
- Next Smaller Element
Heap
- Building Heap from Array
- Heap Sort - Cpp Solution
- Maximum of all subarrays of size k - Cpp Solution
- k largest elements - Cpp Solution
- Kth smallest element - Cpp Solution
- Merge k Sorted Arrays - Cpp Solution
- Merge two binary Max heaps - Cpp Solution
- K-th Largest Sum Contiguous Subarray
- Reorganize String - Cpp Solution
- Merge K sorted linked lists - Cpp Solution
- Smallest range in K lists - Cpp Solution
- Find median in a stream - Cpp Solution
- Is Binary Tree Heap - Cpp Solution
- Minimum Cost of ropes - Cpp Solution
- Convert BST to Min Heap
- Convert min Heap to max Heap
- Rearrange characters - Cpp Solution
- Minimum sum - Cpp Solution
- []( "view question") - Cpp Solution