Patterns
Learn the tricks, not just the problems.
Interviewers rarely ask a problem you have seen. They ask one that uses a trick you have seen. Here every problem is grouped by the trick that cracks it.
Pattern matching
Slide a small word over a big one, and skip ahead smartly when it does not match.
Reach for it when: KMP, Rabin Karp, Z, Boyer Moore.
6 problems
- Write a Code to check whether one string is a rotation of anotherString · String doubling
- Rabin Karp AlgoString · Rolling hash
- KMP AlgoString · Prefix function (KMP)
- Boyer Moore Algorithm for Pattern SearchingString · Pattern matching with skips
- Minimum characters to be added at front to make string palindromeString · Prefix function (KMP)
- Find majority elementSearching & Sorting · Boyer-Moore voting
Two pointers
Two fingers walking along a row, often from both ends toward the middle.
Reach for it when: Sorted arrays, pairs that add up to something, reversing, palindromes.
32 problems
- Reverse the arrayArray
- Write a program to cyclically rotate an array by oneArray · In-place shifting
- Move all the negative elements to one side of the arrayArray
- Given an array which consists of only 0, 1 and 2. Sort the array without using any sorting algoArray · Three pointers
- Find the Union and Intersection of the two sorted arraysArray
- Find common elements In 3 sorted arraysArray
- Find the triplet that sum to a given valueArray
- Three way partitioning of an array around a given valueArray · Dutch national flag
- Next PermutationArray
- Rearrange the array in alternating positive and negative items with O(1) extra spaceArray · In-place rotation
- Trapping Rain water problemArray
- Minimum no. of operations required to make an array palindromeArray
- Reverse a StringString
- Check whether a String is Palindrome or notString
- Write a program to find the longest Palindrome in a string - Longest palindromic SubstringString · Expand around center
- Transform One String to Another using Minimum Number of Given OperationString · Two pointers from the end
- Find a pair with a given differenceSearching & Sorting
- Find four elements that sum to a given valueSearching & Sorting
- Count triplet with sum smaller than a given valueSearching & Sorting
- DoubleHelix SPOJSearching & Sorting
- Partitioning and Sorting Arrays with Many Repeated EntriesSearching & Sorting · Three way partitioning
- Intersection of two Sorted Linked ListLinked List
- Intersection Point of two Linked ListsLinked List · Two pointers that switch lists
- Find pairs with a given sum in a DLLLinked List
- Count triplets in a sorted DLL whose sum is equal to given value XLinked List
- Program for nth node from the end of a Linked ListLinked List
- Implement 2 stack in an arrayStacks & Queues · Two pointers from both ends
- Count pairs from 2 BST whose sum is equal to given value XBinary Search Trees
- Minimum Platforms ProblemGreedy · Sweep line with two pointers
- Maximum sum of absolute difference of an arrayGreedy
- Find maximum sum possible equal sum of three stacksGreedy · Greedy with three pointers
- Longest Palindromic SubstringDynamic Programming · Expand around center
Fast and slow pointers
A tortoise and a hare on the same track. If there is a loop, the hare laps the tortoise.
Reach for it when: Loops in linked lists, the middle of a list, repeated numbers.
8 problems
- Find duplicate in an array of N+1 IntegersArray
- Write a program to Detect loop in a linked listLinked List
- Write a program to Delete loop in a linked listLinked List
- Find the starting point of the loopLinked List
- Find the middle Element of a linked listLinked List
- Check if a linked list is a circular linked listLinked List
- Split a Circular linked list into two halvesLinked List
- Write a Program to check whether the Singly Linked list is a palindrome or notLinked List
Sliding window
A picture frame that slides along a row, adding on one side and dropping on the other.
Reach for it when: Best stretch of k items, the shortest stretch that has everything.
10 problems
- Chocolate Distribution problemArray · Sort then sliding window
- Smallest Subarray with sum greater than a given valueArray
- Minimum no. of Jumps to reach end of an arrayArray · Greedy window (BFS levels)
- Minimum swaps required bring elements less equal K togetherArray
- Write a program to find the smallest window that contains all characters of string itselfString
- Find the smallest window in a string containing all characters of another stringString
- First negative integer in every window of size kStacks & Queues · Sliding window with a queue
- Chocolate Distribution ProblemGreedy
- Minimum number of jumps to reach endDynamic Programming · Greedy jump windows
- Minimum removals from array to make max min less than or equal to KDynamic Programming
Prefix sums
A running total written under each locker, so any stretch is one subtraction away.
Reach for it when: Sums of ranges, subarrays that add to a target.
13 problems
- Find if there is any subarray with sum equal to 0Array · Prefix sum with a hash set
- Kadanes AlgoArray · Kadane running sum
- Best time to buy and Sell stockArray · Running minimum
- Split the Binary string into two substring with equal 0s and 1sString · Running balance
- Print all subarrays with 0 sumSearching & Sorting · Prefix sum with hash map
- Product array PuzzleSearching & Sorting · Prefix and suffix products
- Delete nodes which have a greater value on right sideLinked List · Reverse and running max
- Find the first circular tour that visits all Petrol PumpsStacks & Queues · Greedy with a running sum
- Print all K Sum paths in a Binary treeBinary Trees · Prefix sums with a hash map
- GERGOVIA - Wine trading in GergoviaGreedy · Prefix sum greedy
- Maximum difference of zeros and ones in binary stringDynamic Programming · Kadane running sum
- Largest rectangular sub-matrix whose sum is 0Dynamic Programming · Prefix sums with a hash map
- Largest area rectangular sub-matrix with equal number of 1s and 0sDynamic Programming · Prefix sums with a hash map
Hash map counting
A notebook where you tally what you have seen, so you never look twice.
Reach for it when: Duplicates, pairs, anagrams, first unique thing.
25 problems
- Find all pairs on integer array whose sum is equal to given numberArray
- Find longest consecutive subsequenceArray · Hash set lookups
- Find whether an array is a subset of another arrayArray
- Find Duplicate characters in a stringString
- Count and Say problemString · Run length counting
- Find the first repeated word in stringString · Hash set lookup
- Minimum number of swaps for bracket balancingString · Greedy counting
- Given a sequence of words, print all anagrams togetherString · Hash map grouping
- Function to find Number of customers who could not get a computerString
- Check if two given strings are isomorphic to each otherString · Two hash maps
- Sort array according to count of set bitsSearching & Sorting · Counting sort by key
- Minimum no. of swaps required to sort the arraySearching & Sorting · Cycle counting
- Common elements in all rows of a given matrixMatrix
- Remove Duplicates in a Un-sorted Linked ListLinked List · Hash set lookup
- Find the first non-repeating character from a stream of charactersLinked List · Doubly linked list plus hash map
- LRU Cache ImplementationStacks & Queues · Hash map plus doubly linked list
- Queue based approach or first non-repeating character in a streamStacks & Queues · Queue plus counting
- Count total set bits in all numbers from 1 to nBit Manipulation · Bit column counting
- Find minimum swaps required to convert a Binary tree into BSTBinary Trees · Cycle counting
- Check if a Binary Tree contains duplicate subtrees of size 2 or moreBinary Trees · Hash map of subtree shapes
- Find all Duplicate subtrees in a Binary treeBinary Trees · Hash map of subtree shapes
- Maximum product subset of an arrayGreedy · Counting and case analysis
- Program for Least Recently Used (LRU) Page Replacement algorithmGreedy · Hash map plus doubly linked list
- Clone a graphGraph · Hash map from old to new
- Longest subsequence such that difference between adjacent is oneDynamic Programming · Hash map dynamic programming
Binary search
Open the book in the middle and throw away the half you do not need.
Reach for it when: Anything sorted, or any yes and no question that flips once.
24 problems
- Median of 2 sorted arrays of equal sizeArray · Binary search on the answer
- Median of 2 sorted arrays of different sizeArray · Binary search on the answer
- Find first and last positions of an element in a sorted arraySearching & Sorting
- Find a Fixed Point (Value equal to index) in a given arraySearching & Sorting
- Search in a rotated sorted arraySearching & Sorting
- Square root of an integerSearching & Sorting · Binary search on the answer
- Optimum location of point to minimize total distanceSearching & Sorting · Ternary search
- Searching in an array where adjacent differ by at most kSearching & Sorting · Jump search
- Bishu and SoldiersSearching & Sorting
- Rasta and KheshtakSearching & Sorting · Binary search on the answer
- Kth smallest number againSearching & Sorting · Merge intervals and binary search
- Find pivot element in a sorted arraySearching & Sorting
- K-th Element of Two Sorted ArraysSearching & Sorting · Binary search on the answer
- Aggressive cowsSearching & Sorting · Binary search on the answer
- Book Allocation ProblemSearching & Sorting · Binary search on the answer
- EKOSPOJSearching & Sorting · Binary search on the answer
- Missing Number in APSearching & Sorting
- Smallest number with at least n trailing zeroes in factorialSearching & Sorting · Binary search on the answer
- Painters Partition ProblemSearching & Sorting · Binary search on the answer
- ROTI-Prata SPOJSearching & Sorting · Binary search on the answer
- Subset SumsSearching & Sorting · Meet in the middle
- Find median in a row wise sorted matrixMatrix · Binary search on the answer
- Kth smallest element in a row-column wise sorted matrixMatrix · Binary search on the answer
- Longest Increasing SubsequenceDynamic Programming · Binary search on tails
Sorting first
Line everyone up by height first. Many problems become easy once things are in order.
Reach for it when: Closest pairs, merging, scheduling, grouping.
36 problems
- Find the Kth max and min element of an arrayArray · Quickselect
- Merge 2 sorted arrays without using Extra spaceArray · Gap method (shell sort)
- Merge IntervalsArray · Greedy by sorting
- Minimise the maximum difference between heightsArray · Greedy by sorting
- Merge 2 sorted arraysSearching & Sorting · Gap method (shell sort)
- Job Scheduling AlgoSearching & Sorting · Greedy by sorting
- Flatten a Linked ListLinked List · Merge sorted lists
- Merge Overlapping IntervalsStacks & Queues · Greedy by sorting
- Convert Binary tree into BSTBinary Search Trees · Inorder traversal with sorting
- Sort an Array using heap (HeapSort)Heap · Heap sort
- Merge K sorted arraysHeap · K way merge with a heap
- Merge K Sorted Linked ListsHeap · K way merge with a heap
- Smallest range in K ListsHeap · K way merge with a heap
- Activity Selection ProblemGreedy · Greedy by sorting
- Job Sequencing ProblemGreedy · Greedy by sorting
- Fractional Knapsack ProblemGreedy · Greedy by sorting
- Greedy Algorithm to find Minimum number of CoinsGreedy · Greedy by sorting
- Buy Maximum Stocks if i stocks can be bought on i-th dayGreedy · Greedy by sorting
- Find the minimum and maximum amount to buy all N candiesGreedy · Greedy by sorting
- Minimum Cost to cut a board into squaresGreedy · Greedy by sorting
- Find maximum meetings in one roomGreedy · Greedy by sorting
- Maximize array sum after K negationsGreedy · Greedy by sorting
- Maximize the sum of arr[i] times iGreedy · Greedy by sorting
- Maximize sum of consecutive differences in a circular arrayGreedy · Greedy by sorting
- Minimum sum of absolute difference of pairs of two arraysGreedy · Greedy by sorting
- Smallest subset with sum greater than all other elementsGreedy · Greedy by sorting
- DEFKIN - Defense of a KingdomGreedy · Greedy by sorting
- CHOCOLA - ChocolateGreedy · Greedy by sorting
- ARRANGE - Arranging AmplifiersGreedy · Greedy by sorting
- Implement Topological SortGraph · Topological sort
- Minimum time taken by each job to be completed given by a Directed Acyclic GraphGraph · Topological sort
- Find whether it is possible to finish all tasks or not from given dependenciesGraph · Topological sort
- Given a sorted Dictionary of an Alien Language, find order of charactersGraph · Topological sort
- Longest path in a Directed Acyclic GraphGraph · Topological sort
- Maximum Length Chain of PairsDynamic Programming · Greedy by sorting
- Maximum Length of Pair ChainDynamic Programming · Greedy by sorting
Grid walking
Walk a chocolate bar square by square: along rows, down columns, in a spiral, or down a staircase.
Reach for it when: Matrices: spirals, rotations, searching a sorted grid, scanning in all directions.
6 problems
- Search a Word in a 2D Grid of charactersString · Grid direction scan
- Longest Common PrefixString · Column by column scan
- Spiral traversal on a MatrixMatrix · Matrix simulation
- Search an element in a matrixMatrix · Staircase search
- Find row with maximum no. of 1sMatrix · Staircase search
- Rotate matrix by 90 degreesMatrix · In-place matrix transform
Kadane
Walk the row with a bag of points. If the bag goes negative, drop it and start fresh.
Reach for it when: Best sum or product of a stretch of numbers.
3 problems
Monotonic stack
A pile where shorter kids step out when a taller kid arrives, so everyone finds who is taller next to them.
Reach for it when: Next greater or smaller, histograms, stock spans.
7 problems
- Maximum size rectangleMatrix
- Find the next Greater elementStacks & Queues
- Largest rectangular Area in HistogramStacks & Queues
- Sum of minimum and maximum elements of all subarrays of size kStacks & Queues · Monotonic deque
- Next Smaller ElementStacks & Queues
- Check preorder is valid or notBinary Search Trees
- Maximum of all subarrays of size kHeap · Monotonic deque
Stacks and queues
A pile of plates and a lunch line.
Reach for it when: Brackets, undo, expressions, processing in arrival order.
38 problems
- Balanced Parenthesis problemString · Stack
- Minimum number of bracket reversals needed to make an expression balancedString · Stack matching
- Recursively remove all adjacent duplicatesString · Stack
- Implement Stack from ScratchStacks & Queues · Stack design
- Implement Queue from ScratchStacks & Queues · Queue design
- Implement N stacks in an ArrayStacks & Queues · Free list inside an array
- Check the expression has valid or Balanced parenthesis or notStacks & Queues · Stack matching
- Reverse a String using StackStacks & Queues · Stack reversal
- Design a Stack that supports getMin() in O(1) time and O(1) extra spaceStacks & Queues · Stack with an encoded minimum
- The celebrity ProblemStacks & Queues · Elimination with a stack
- Arithmetic Expression evaluationStacks & Queues · Two stacks for operators and numbers
- Evaluation of Postfix expressionStacks & Queues · Stack evaluation
- Implement a method to insert an element at its bottom without using any other data structureStacks & Queues · Recursion as a hidden stack
- Reverse a stack using recursionStacks & Queues · Recursion as a hidden stack
- Sort a Stack using recursionStacks & Queues · Recursion as a hidden stack
- Length of the Longest Valid SubstringStacks & Queues · Stack of indices
- Expression contains redundant bracket or notStacks & Queues · Stack matching
- Implement Stack using QueueStacks & Queues · Stack and queue design
- Implement Stack using DequeStacks & Queues · Stack and queue design
- Stack Permutations (Check if an array is stack permutation of other)Stacks & Queues · Stack simulation
- Implement Queue using StackStacks & Queues · Two stacks, lazy transfer
- Implement n queue in an arrayStacks & Queues · Free list inside an array
- Implement a Circular queueStacks & Queues · Circular array with modulo
- Reverse a Queue using recursionStacks & Queues · Recursion as a hidden stack
- Reverse the first K elements of a queueStacks & Queues · Stack plus queue rotation
- Interleave the first half of the queue with second halfStacks & Queues · Queue rotation
- Minimum time required to rot all orangesStacks & Queues · Breadth first search with a queue
- Check if all levels of two trees are anagrams or notStacks & Queues · Breadth first search with a queue
- Level order traversalBinary Trees · Breadth first search with a queue
- Reverse Level Order traversalBinary Trees · Breadth first search with a queue
- Inorder Traversal of a tree both using recursion and IterationBinary Trees · Iterative traversal with a stack
- Preorder Traversal of a tree both using recursion and IterationBinary Trees · Iterative traversal with a stack
- Postorder Traversal of a tree both using recursion and IterationBinary Trees · Iterative traversal with a stack
- Top View of a treeBinary Trees · Breadth first search with a queue
- Bottom View of a treeBinary Trees · Breadth first search with a queue
- Zig-Zag traversal of a binary treeBinary Trees · Two stacks
- Diagonal Traversal of a Binary treeBinary Trees · Breadth first search with a queue
- Merge two BSTBinary Search Trees · Inorder traversal with two stacks
Linked list rewiring
Unhook and rehook train cars without dropping any.
Reach for it when: Reversing, merging, rotating, removing from lists.
16 problems
- Write a Program to reverse the Linked List (Both Iterative and recursive)Linked List · Pointer flipping
- Reverse a Linked List in group of Given SizeLinked List · Pointer flipping
- Remove Duplicates in a sorted Linked ListLinked List · Single pointer skip
- Write a Program to Move the last element to Front in a Linked ListLinked List · Trailing pointer
- Add 1 to a number represented as a Linked ListLinked List · Last non 9 pointer
- Add two numbers represented by linked listsLinked List · Reverse and carry
- Deletion from a Circular Linked ListLinked List · Previous pointer walk
- Reverse a Doubly Linked listLinked List · Pointer swapping
- Rotate Doubly Linked list by N nodesLinked List · Make a ring, then cut
- Rotate a Doubly Linked list in group of Given SizeLinked List · Pointer flipping
- Can we reverse a linked list in less than O(n)Linked List · Direction flag
- Sort a LL of 0s, 1s and 2sLinked List · Split into lists and join
- Clone a linked list with next and random pointerLinked List · Interleave copies
- Segregate even and odd nodes in a Linked ListLinked List · Split into lists and join
- Find the middle element of a stackStacks & Queues · Doubly linked list with a middle pointer
- Convert Binary tree into Doubly Linked ListBinary Trees · Inorder traversal with a prev pointer
Tree recursion
Ask the left child, ask the right child, and combine their answers.
Reach for it when: Heights, sums, paths, checks on trees.
24 problems
- Count InversionArray · Divide and conquer
- Find the inversion countSearching & Sorting · Divide and conquer
- Implement Merge-sort in-placeSearching & Sorting · Divide and conquer
- Merge Sort For Linked listsLinked List · Divide and conquer
- Quicksort for Linked ListsLinked List · Divide and conquer
- Why Quicksort is preferred for Arrays and Merge Sort for LinkedListsLinked List · Divide and conquer
- Construct Binary Tree from String with Bracket RepresentationBinary Trees · Recursive parsing
- Construct Binary tree from Inorder and preorder traversalBinary Trees · Divide and conquer
- Find distance between 2 nodes in a Binary treeBinary Trees · Lowest common ancestor
- Find a value in a BSTBinary Search Trees · BST search
- Deletion of a node in a BSTBinary Search Trees · BST search and splice
- Find min and max value in a BSTBinary Search Trees · BST search
- Find inorder successor and inorder predecessor in a BSTBinary Search Trees · BST search
- Populate Inorder successor of all nodesBinary Search Trees · Reverse inorder traversal
- Find LCA of 2 nodes in a BSTBinary Search Trees · BST search
- Convert a normal BST into a Balanced BSTBinary Search Trees · Divide and conquer
- Find Kth largest element in a BSTBinary Search Trees · Reverse inorder traversal
- Find Kth smallest element in a BSTBinary Search Trees · Inorder traversal
- Find the median of BST in O(n) time and O(1) spaceBinary Search Trees · Morris traversal
- Replace every element with the least greater element on its rightBinary Search Trees · BST insert with successor
- Largest BST in a Binary TreeBinary Search Trees · Postorder with return info
- Flatten BST to sorted listBinary Search Trees · Inorder traversal
- Check if a Binary Tree is HeapHeap · Tree walk with array indexes
- Convert BST to Min HeapHeap · Inorder then preorder fill
Breadth first search
Fan out ring by ring with a waiting line, like ripples in a pond.
Reach for it when: Rows of a tree, shortest number of steps, spreading things (rotting oranges).
9 problems
- Distance of nearest cell having 1 in a binary matrixStacks & Queues · Multi-source breadth first search
- Find shortest safe route in a path with landminesBacktracking
- Implement BFS algorithmGraph
- Minimum Step by KnightGraph
- Word LadderGraph
- Snake and Ladders ProblemGraph
- Check whether a graph is Bipartite or NotGraph
- Water Jug problem using BFSGraph
- Minimum edges to reverse to make path from source to destinationGraph · 0-1 breadth first search
Depth first search
Follow one road as far as it goes, then walk back and try the next.
Reach for it when: Islands, connected parts, cycles, all paths.
34 problems
- Height of a treeBinary Trees
- Diameter of a treeBinary Trees
- Mirror of a treeBinary Trees
- Left View of a treeBinary Trees
- Right View of TreeBinary Trees
- Check if a tree is balanced or notBinary Trees
- Boundary traversal of a Binary treeBinary Trees
- Convert Binary tree into Sum treeBinary Trees
- Check if Binary tree is Sum tree or notBinary Trees
- Check if all leaf nodes are at same level or notBinary Trees
- Check if 2 trees are mirror or notBinary Trees
- Sum of Nodes on the Longest path from root to leaf nodeBinary Trees
- Find Largest subtree sum in a treeBinary Trees
- Find LCA in a Binary treeBinary Trees
- Kth Ancestor of node in a Binary treeBinary Trees
- Tree Isomorphism ProblemBinary Trees
- Check if a tree is a BST or notBinary Search Trees · Depth first search with bounds
- Construct BST from preorder traversalBinary Search Trees · Depth first search with bounds
- Count BST nodes that lie in a given rangeBinary Search Trees · Depth first search with pruning
- Check whether BST contains Dead endBinary Search Trees · Depth first search with bounds
- Water Connection ProblemGreedy · Following chains in a graph
- Create a Graph, print itGraph · Adjacency list
- Implement DFS AlgoGraph
- Detect Cycle in Directed Graph using BFS DFS AlgoGraph
- Detect Cycle in UnDirected Graph using BFS DFS AlgoGraph
- Flood fill algoGraph
- Find the no. of IslandsGraph
- Find bridge in a graphGraph · Depth first search with low-link
- Count Strongly connected Components (Kosaraju Algo)Graph · Depth first search, two passes
- Oliver and the GameGraph
- Paths to travel each nodes using each edge (Seven Bridges)Graph · Euler path (Hierholzer)
- Chinese Postman or Route InspectionGraph · Euler circuit plus bitmask matching
- Number of Triangles in a Directed and Undirected GraphGraph · Degree ordering
- Two Clique ProblemGraph · Bipartite check
Shortest paths
Always grow the closest town next, and fix up the distances as you go.
Reach for it when: Weighted maps: Dijkstra, Bellman Ford, Floyd Warshall.
4 problems
Union find
Every kid points to a team captain. Joining teams is pointing one captain at another.
Reach for it when: Grouping, connecting cables, spanning trees, cycles in undirected graphs.
4 problems
Heap
A line where the smallest kid is always at the front, however you add people.
Reach for it when: Top k, merging k sorted things, running medians, scheduling.
22 problems
- Rearrange characters in a string such that no two adjacent are sameString · Greedy with a heap
- Print elements in sorted order using row-column wise sorted matrixMatrix · Heap of size k
- Sort a k sorted Doubly Linked listLinked List · Heap of size k
- Merge K sorted Linked listLinked List · Heap of size k
- Minimum sum of squares of character counts in a given string after removing k charactersStacks & Queues · Heap of counts
- Implement a Maxheap MinHeap using arrays and recursionHeap · Heap basics
- k largest element in an arrayHeap · Heap of size k
- Kth smallest and largest element in an unsorted arrayHeap · Heap of size k
- Merge 2 Binary Max HeapsHeap · Build heap
- Kth largest sum continuous subarraysHeap · Heap of size k
- Leetcode reorganize stringsHeap · Greedy with a max heap
- Median in a stream of IntegersHeap · Two heaps
- Connect n ropes with minimum costHeap · Greedy with a min heap
- Convert min heap to max heapHeap · Build heap
- Rearrange characters in a string such that no two adjacent are sameHeap · Greedy with a max heap
- Minimum sum of two numbers formed from digits of an arrayHeap · Greedy with a min heap
- Huffman CodingGreedy · Greedy with a min heap
- Minimize Cash Flow among a given set of friends who have borrowed money from each otherGreedy · Greedy with two heaps
- Program for Shortest Job First (or SJF) CPU SchedulingGreedy · Greedy with a min-heap
- Minimum Cost of ropesGreedy · Greedy with a min-heap
- Rearrange characters in a string such that no two adjacent are sameGreedy · Greedy with a max-heap
- Implement Prims AlgorithmGraph · Greedy with a heap
Greedy
Grab the best looking choice now and never look back. Works only when you can prove it is safe.
Reach for it when: Intervals, coins with nice values, fractional knapsack.
15 problems
- Given n appointments, find the conflicting appointmentsBinary Search Trees · Interval tree
- Maximum trains for which stoppage can be providedGreedy · Greedy by earliest finish
- Check if it is possible to survive on IslandGreedy · Greedy math
- DIEHARD - DIE HARDGreedy · Greedy simulation
- Picking Up ChicksGreedy · Greedy from the far end
- K Centers ProblemGreedy · Greedy farthest first
- Find smallest number with given number of digits and sum of digitsGreedy · Greedy digit building
- Graph Colouring ProblemGraph · Greedy colouring
- Minimise the cashflow among a given set of friends who have borrowed money from each otherGraph
- Matrix Chain MultiplicationDynamic Programming · Interval dynamic programming
- Longest Palindromic SubsequenceDynamic Programming · Interval dynamic programming
- Count All Palindromic Subsequence in a given StringDynamic Programming · Interval dynamic programming
- Optimal Strategy for a GameDynamic Programming · Interval dynamic programming
- Optimal Binary Search TreeDynamic Programming · Interval dynamic programming
- Boolean Parenthesization ProblemDynamic Programming · Interval dynamic programming
Backtracking
Explore a maze with a ball of string. Dead end? Follow the string back and try the next way.
Reach for it when: All permutations, subsets, boards, mazes.
26 problems
- Print all Subsequences of a stringString
- Print all the permutations of the given stringString
- Find next greater number with same set of digitsString · Next permutation
- Count of number of given string in 2D character arrayString
- Program to generate all possible valid IP addresses from given stringString
- Recursively print all sentences that can be formed from list of word listsString
- Rat in a maze ProblemBacktracking
- Printing all solutions in N-Queen ProblemBacktracking
- Word Break Problem using BacktrackingBacktracking · Backtracking with memoization
- Remove Invalid ParenthesesBacktracking
- Sudoku SolverBacktracking
- m Coloring ProblemBacktracking
- Print all palindromic partitions of a stringBacktracking
- The Knights tour problemBacktracking
- Tug of WarBacktracking
- Combinational SumBacktracking
- Find Maximum number possible by doing at-most K swapsBacktracking
- Print all permutations of a stringBacktracking
- Find if there is a path of more than k length from a sourceBacktracking
- Longest Possible Route in a Matrix with HurdlesBacktracking
- Print all possible paths from top left to bottom right of a mXn matrixBacktracking
- Partition of a set into K subsets with equal sumBacktracking · Backtracking with bitmask memo
- Search in a MazeGraph
- Find if there is a path of more than k length from a sourceGraph
- M-Colouring ProblemGraph
- Vertex Cover ProblemGraph
Trie
A tree of letters where words with the same start share a branch.
Reach for it when: Prefixes, autocomplete, word lists.
6 problems
Dynamic programming
Write each small answer in a chart so you never do the same homework twice.
Reach for it when: Counting ways, best totals, comparing two strings.
58 problems
- Find maximum product subarrayArray · 1D dynamic programming
- Maximum profit by buying and selling a share atmost twiceArray · 1D dynamic programming
- Write a Program to check whether a string is a valid shuffle of two strings or notString · 2D dynamic programming
- Find Longest Recurring Subsequence in StringString · 2D dynamic programming
- Word Wrap ProblemString · 1D dynamic programming
- EDIT DistanceString · 2D dynamic programming
- Word break ProblemString · 1D dynamic programming
- Count All Palindromic Subsequence in a given StringString · 2D dynamic programming
- Find the longest common subsequence between two stringsString · 2D dynamic programming
- String matching where one string contains wildcard charactersString · 2D dynamic programming
- Maximum sum such that no 2 elements are adjacentSearching & Sorting · 1D dynamic programming
- Find a specific pair in matrixMatrix · 2D dynamic programming
- Maximum Sum of nodes in Binary tree such that no two are adjacentBinary Trees · Tree dynamic programming
- Subset Sum ProblemBacktracking · 2D dynamic programming
- Implement Floyd Warshall AlgorithmGraph · 2D dynamic programming
- Travelling Salesman ProblemGraph · Bitmask dynamic programming
- Coin Change ProblemDynamic Programming · Unbounded knapsack
- Knapsack ProblemDynamic Programming · 2D dynamic programming
- Binomial Coefficient ProblemDynamic Programming · 2D dynamic programming
- Permutation Coefficient ProblemDynamic Programming · 1D dynamic programming
- Program for nth Catalan NumberDynamic Programming · 1D dynamic programming
- Edit DistanceDynamic Programming · 2D dynamic programming
- Subset Sum ProblemDynamic Programming · 2D dynamic programming
- Friends Pairing ProblemDynamic Programming · 1D dynamic programming
- Gold Mine ProblemDynamic Programming · 2D dynamic programming
- Assembly Line Scheduling ProblemDynamic Programming · 1D dynamic programming
- Painting the Fence problemDynamic Programming · 1D dynamic programming
- Maximize The Cut SegmentsDynamic Programming · 1D dynamic programming
- Longest Common SubsequenceDynamic Programming · 2D dynamic programming
- Longest Repeated SubsequenceDynamic Programming · 2D dynamic programming
- Space Optimized Solution of LCSDynamic Programming · 2D dynamic programming
- LCS (Longest Common Subsequence) of three stringsDynamic Programming · 3D dynamic programming
- Maximum Sum Increasing SubsequenceDynamic Programming · 1D dynamic programming
- Count all subsequences having product less than KDynamic Programming · 1D dynamic programming
- Maximum subsequence sum such that no three are consecutiveDynamic Programming · 1D dynamic programming
- Egg Dropping ProblemDynamic Programming · 2D dynamic programming
- Maximum size square sub-matrix with all 1sDynamic Programming · 2D dynamic programming
- Maximum sum of pairs with specific differenceDynamic Programming · 1D dynamic programming
- Min Cost Path ProblemDynamic Programming · 2D dynamic programming
- Minimum cost to fill given weight in a bagDynamic Programming · Unbounded knapsack
- Longest Common SubstringDynamic Programming · 2D dynamic programming
- Count number of ways to reach a given score in a gameDynamic Programming · Unbounded knapsack
- Count Balanced Binary Trees of Height hDynamic Programming · 1D dynamic programming
- Largest Sum Contiguous SubarrayDynamic Programming · 1D dynamic programming
- Unbounded Knapsack (Repetition of items allowed)Dynamic Programming · 1D dynamic programming
- Word Break ProblemDynamic Programming · 1D dynamic programming
- Largest Independent Set ProblemDynamic Programming · Tree dynamic programming
- Partition problemDynamic Programming · 2D dynamic programming
- Longest alternating subsequenceDynamic Programming · 1D dynamic programming
- Weighted Job SchedulingDynamic Programming · 1D dynamic programming
- Coin game winner where every player has three choicesDynamic Programming · Game DP with win and lose states
- Count Derangements (Permutation such that no element appears in its original position)Dynamic Programming · 1D dynamic programming
- Maximum profit by buying and selling a share at most twiceDynamic Programming · State machine DP
- Palindrome Partitioning ProblemDynamic Programming · 1D dynamic programming
- Word Wrap ProblemDynamic Programming · 1D dynamic programming
- Mobile Numeric Keypad ProblemDynamic Programming · 2D dynamic programming
- Maximum profit by buying and selling a share at most k timesDynamic Programming · 2D dynamic programming
- Find if a string is interleaved of two other stringsDynamic Programming · 2D dynamic programming
Bit tricks
Numbers are rows of light switches. Flip, test and combine switches fast.
Reach for it when: Single numbers, powers of two, subsets as masks.
9 problems
- Count set bits in an integerBit Manipulation
- Find the two non-repeating elements in an array of repeating elementsBit Manipulation · XOR tricks
- Count number of bits to be flipped to convert A to BBit Manipulation
- Program to find whether a no is power of twoBit Manipulation
- Find position of the only set bitBit Manipulation · Bit masks
- Copy set bits in a rangeBit Manipulation · Bit masks
- Divide two integers without using multiplication, division and mod operatorBit Manipulation · Shift and subtract
- Calculate square of a number without using multiplication, division and pow()Bit Manipulation · Shift and add
- Power SetBit Manipulation · Bitmask enumeration
Math and counting
A neat formula that skips the work.
Reach for it when: Factorials, Catalan numbers, combinations, number puzzles.
10 problems
- Find the maximum and minimum element in an arrayArray · Compare in pairs
- Given an array of size n and a number k, find all elements that appear more than n/k timesArray · Voting with k - 1 candidates
- Find factorial of a large numberArray · Big number arithmetic
- Convert a Sentence into its equivalent mobile numeric keypad sequenceString · Lookup table
- Number of flips to make binary string alternateString · Compare with a target
- Maximum and minimum of an array using minimum number of comparisonsSearching & Sorting · Pair comparison
- Find the repeating and the missingSearching & Sorting · Math with sums
- Multiply 2 no. represented by LLLinked List · Modular arithmetic
- Find the K-th Permutation Sequence of first N natural numbersBacktracking · Factorial number system
- Total no. of Spanning tree in a graphGraph · Matrix tree theorem
Other techniques
2 problems