DSA Patterns Flashcards
How to identify the sliding window problem
You might be asked to find the longest or shortest substring, subarray or a certain value. Additionally, if the problem input is a linear data structure such as a linked list, array or string, chances are it is a sliding window problem.
Some common problems with the sliding window problem:
Maximum sum subarray of size “K”
Longest substring with “K” distinct characters
String anagrams
How to identify the two-pointer method
A two-pointer problem will feature sorted arrays or linked lists. You will typically need to find a set of elements that fulfill certain constraints. The set of elements in the array may also be a pair, triplet or even a subarray.
Some common problems with the two-pointer method:
Squaring a sorted array
Triplets that sum to zero
Comparing strings that contain backspaces
How to identify the fast and slow pointers problem
Fast and slow problems will typically deal with a loop in a linked list or array. You can also use the pattern when you need to know the position of a certain element or the overall length of the linked list.
Some common problems with the fast and slow pointers pattern:
Linked list cycle
Palindrome linked list
Cycle in a circular array
How to identify the merge-intervals pattern
You have a merge-intervals pattern if you’re asked to produce a list with only mutually exclusive intervals or you hear the term “overlapping intervals.”
Some common problems with the merge-intervals pattern:
Intervals intersection
Maximum CPU load
What is a merge interval pattern?
The merge intervals pattern is an efficient technique to work through overlapping intervals. In many problems involving intervals, you either need to find overlapping intervals or merge intervals if they overlap.
The merge-interval pattern works like this: Given two intervals “a” and “b,” there will be six different ways the two intervals can relate to each other
How to identify the cyclic-sort pattern
You can use the cyclic-sort pattern on problems involving a sorted array with numbers in a given range or if the problem asks you to find the missing, duplicate or smallest number in a sorted or rotated array.
Some common problems with a cyclic-sort pattern:
Find the missing number
Find the smallest missing positive number
How to identify the in-place reversal of linked list pattern
You will be asked to reverse a linked list without using extra memory.
Some common problems featuring the in-place reversal of linked list pattern:
Reverse a sublist
Reverse every K-element sublist
How to identify the tree breadth-first pattern
If you’re asked to traverse a tree in a level-by-level fashion or level-order traversal, you can use the tree breadth-first pattern.
Some common problems featuring the tree breadth-first pattern:
Binary tree level order traversal
Zig-zag traversal
How to identify the tree depth-first pattern
If you’re asked to traverse a tree with in-order, preorder, or postorder depth-first search or the problem requires searching for something where the node is closer to a leaf, you can use the tree depth-first pattern.
Some common problems featuring the tree depth-first search pattern:
Sum of path numbers
All paths for a sum
How to identify the two heaps pattern?
The two heaps pattern is useful in priority queue and scheduling situations. If you need to find the smallest, largest or median elements of a set or solve a problem with a binary tree data structure, you can use the two heaps pattern.
Some common problems featuring the two heaps pattern:
Find the median of a number stream
How to identify the subsets pattern?
You can use the subsets pattern when you need to find the combinations or permutations of a given set.
Some common problems featuring the subsets pattern:
Subsets with duplicates
String permutations by changing case
How to identify the modified binary search pattern?
You can use the modified binary search pattern to solve order-agnostic binary search or search in a sorted infinite array problems.
How to identify the top “K” elements pattern?
If you’re asked to find the top, smallest or frequent “K” elements of a given set or sort an array to find an exact element, you can use the top “K” elements pattern.
Some common problems featuring the top “K” elements pattern:
Top “K” numbers
Top “K” frequent numbers
How to identify the K-way merge pattern
The K-way merge pattern can be used in problems featuring sorted arrays, lists or a matrix. You can also use the pattern if you need to merge sorted lists or find the smallest element in a sorted list.
Some common problems featuring the K-way merge pattern:
Merge K-sorted lists
“K” pairs with largest sums
How to identify the topological sort pattern?
If you’re asked to update all objects in a sorted order or have a class of objects in a particular order, you can use the topological sort pattern. The problem might also deal with graphs that have no directed cycles in some problems.
Some common problems featuring the topological sort pattern:
Task scheduling
Minimum height of a tree
