DSA Patterns Flashcards
Two Pointers
Definition
Use two indices (pointers) that move through a data structure (often an array) at different speeds or directions to solve problems involving pair-sums, sorting, or partitioning.
Common Use Cases
• Finding pairs/triplets in a sorted array that sum to a specific value (e.g., 2-sum, 3-sum).
• Removing duplicates or elements in-place (e.g., “Remove Duplicates from Sorted Array”).
• Partitioning arrays (e.g., “Dutch National Flag”).
Pattern to more optimally calculate the sum of a subset of elements in an array
Prefix Sum. Ex Range Sum Query, Contiguous Array, Subarray Sum. Takes only one pass to create the array, then 0(1) retrieval of sums
Prefix Sum initialization and formula to find sum of subset
Initialization:
new Array(nums.length + 1).fill(0)
This sets up an array with an extra space for the initial sum of 0, and sets all other values to zero until they are summed.
Formula:
Sum(l, r) = prefixSum[r + 1] - prefixSum[l]
Subtracts the total sum just before the left pointer from the sum at the right pointer
Sliding Window
Definition
Maintain a window (subarray or substring) that moves (slides) through the data, expanding or shrinking to satisfy conditions like sum, distinct characters, or maximum average.
Common Use Cases
• Subarray sums (e.g., “Subarray Sum Equals K” when all positives).
• Longest substring with certain constraints (e.g., “Longest Substring Without Repeating Characters”).
• Maximum average subarray, minimum window substring, etc.
Fast and Slow Pointers
Definition
Use two pointers that move at different speeds (commonly in linked lists) to detect cycles or find middle points.
Common Use Cases
• Detecting cycles in a linked list.
• Finding the cycle start or the middle node of a linked list.
• Checking if a linked list is palindrome by splitting and reversing second half.
Properties of a Linked List and Node
LinkedList: head, size
Node: data, next
Linked List Insert First
Create a new node with the data and the current head as it’s next, then set the new node as the head.
Linked List Insert Last
Set a current variable to the head. Then loop through while the current node has a next value and if it does setting next as the new current. When the current.next is null you are at the end of the list and can set current.next to a new node
Linked List Insert at Index
If the index is greater than size exit function. If index is 0 then just invoke insert first method. Initialize variables for the current node, the previous node, and a count. While looping, set previous to current, increment count, and set current to next. Once count == index exit loop. Set new node next to current, set previous.next to new node.
Linked List GetAt
Initialize count variable and loop while count < index then return current
Linked List Remove At
Use current, previous, count and while loop to find node at index and identify its previous and next nodes. Then set previous.next to current.next, effectively removing current from the list
Linked List Reversal
Cur, prev, next variables. While there is a cur:
next = cur.next
cur.next = prev
prev = cur
cur = next
After loop, prev will be the new head so set this.head to prev
Linked List Reverse with Stack
Push all nodes into stack, then while the stack has elements, pop them off and set to the current.next then set current to current.next (the popped off element). Set last next pointer to null
Linked List Clear
this.head = null
Reverse Doubly Linked List
While (current)
temp = current.prev
current.prev = current.next
current.next = temp
current = current.prev
at the end temp will be pointing to new head
this.head = temp.prev
Pattern to find the k smallest or k largest
Heaps. Min heap for k largest, max heap for k smallest.
Formula to calculate the distance between two points on a plot
Math.sqrt((x1 - x2)^2 + (y1 - y2)^2) = distance
Get parent, right child, left child in a heap or binary tree
Parent idx = Math.floor((i- 1) / 2)
Left child idx = 2 * i + 1
Right child idx = 2 * i + 2
Adding to a heap
Push to heap (add lead) and heapify up
Set idx to last idx. While idx > 0
Get parent idx. Compare heap[idx] to heap[parentIdx] and switch them if needed. If not needed, break the loop
Replacing an element in a heap (heap already has k elements and new element is larger/smaller than max/min)
Set root (heap[0]) to new element then heapify down
Set idx to 0. While true
Set largest/smallest idx for min/max heap respectively to idx. Get idx for left and right children. Compare left child the right child to largest/smallest and reassign largest/smallest as necessary. If largest/smallest still equals idx then break. If not switch element at idx with element at largest/smallest and set idx to largest/smallest idx
Binary tree pre order
DFS - root, left, right
Binary tree in order
DFS - left, root, right
Binary tree post order
DFS - left, right, root
Binary tree level order
BFS
How to determine binary tree DFS order
“When processing a node, do I need information from the children first?”
If yes - post order
If no and tree is BST - in order
If no and need to decide process at parent - pre order
Binary tree DFS process
Recursively call method with each child as the new root
Binary tree BFS
Set a queue and add root. While queue has elements
Initialize current level array
Set levelsize to queue length
Loop levelsize amount of times, dequeue (shift) node and if not null push val to current level and push left and right children to queue. Exit inner loop and restart outer loop
DFS
Depth first search. Recursively call on child or top/bottom/left/right element in a matrix
BFS
Use queue to add children or top/bottom/left/right elements of matrix. Use whole loop, then set queue size to a variable (because size will change) and do a for loop where you pop off the next in line, process it, and potentially add more to the queue. Then the while loop starts again with new queue size
Matrix directions
let directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]
for (let [dr, dc] of directions
How do you implement a Queue with O(1) retrieval?
Set the data property to a hash map. Add a front idx and back idx property and initialize at 0 for both. When adding an element, add the current back idx as the key and the element as the value, then increment back idx. When retrieving an element, retrieve the front idx key, save the value to a variable. Delete the element (delete this.data[this.front]) then increment front idx. Can also add size property. Check if it’s clear when front idx == back idx
What is an adjacency list?
It’s a list representation of a graph, usually a hash map or array. For hash map the key is the vertex and the value is a list of vertices connected to that vertex by an edge. For array the index is the vertex and subarray is list of vertices
Graph vertices and edges
A vertex or vertices are nodes or points on the graph. Edges are the connection between two vertices and they can be directed (one way) or undirected
LRU Cache
Initialize with capacity property and cache property (Map).
Get method checks if cache has key. If so it sets value to a variable, deletes the key, sets the key again with the value from the v variable then return the value.
Put method checks for key and deletes if it exists. If it doesn’t exist but cache is at capacity then use Map iterator (this.cache.keys()) to get least recent (iterator.next().value) and delete it. Then add the new key and value.
This can also be implemented with a doubly linked list.
What makes a graph tree valid?
All nodes connected, no cycles
What makes a graph tree valid?
All nodes connected, no cycles
Backtracking
Build a solution incrementally and backtrack when the current path of choices won’t lead to a valid solution. Used for search, permutation, combination
SOLID
Single responsibility principle - every class has one responsibility
Open-closed principle - classes should be open for extension but closed for modification
Liskov substitution principle - functions with references to base classes must be able to use objects of derived classes without knowing it
Interface segregation principle - clients should not be forced to depend on interfaces they don’t use
Dependency inversion principle - depend upon abstractions not concretes
Merge Intervals
Definition
Work with intervals (ranges) on a timeline. Often involves sorting intervals by start time and merging overlapping ones or inserting new intervals.
Common Use Cases
• Merging overlapping intervals (e.g., meeting room scheduling).
• Finding intersection or union of intervals (e.g., “Interval List Intersections”).
• Inserting intervals into existing schedules.
Cyclic Sort
Definition
A pattern that uses array indices as references to place each element in its correct position (usually in an array containing the range [1…n]).
Common Use Cases
• Finding missing/duplicate numbers in an unsorted array of a known range.
• Kth missing positive style problems.
• Cleaning up an array where each element ideally sits at its matching index.
In Place Reversal of LinkedIn List
Definition
Reverse linked list nodes or sublists in-place by adjusting pointers (no extra data structure). Often done by iteratively re-linking node pointers.
Common Use Cases
• Reversing an entire linked list (classic).
• Reversing every k-group or rotating the list.
• Reversing sublists (e.g., positions m through n).
Stack
Definition
A Last-In-First-Out (LIFO) data structure. Push items in, pop them out in reverse order.
Common Use Cases
• Expression evaluation (e.g., “Basic Calculator,” parentheses matching).
• Backtracking or undo operations.
• Reversing strings, validating parentheses, etc.
Monotonic Stack
Definition
A stack that keeps elements in either non-decreasing or non-increasing order, allowing quick access to next/previous greater/smaller elements.
Common Use Cases
• Finding next/previous greater or smaller elements (e.g., “Daily Temperatures,” “Next Greater Element”).
• Largest Rectangle in Histogram.
• Asteroid collision or ocean view type problems.
Hash Map
Definition
Store key-value pairs for efficient lookups and insertions, often in O(1) average time.
Common Use Cases
• Counting frequencies (e.g., top-K frequent elements).
• Lookup sets for fast existence checks (e.g., “Two Sum”).
• String grouping (e.g., “Group Anagrams”).
Tree BFS
Definition
Traverse a tree level by level, often using a queue to process all nodes at a given depth before moving to the next.
Common Use Cases
• Level order traversals (e.g., binary tree level order, right side view).
• Finding shortest path in an unweighted tree/graph.
• Connecting next pointers in a binary tree.
Tree DFS
Definition
Traverse a tree branch by branch (preorder, inorder, or postorder) often using recursion or an explicit stack.
Common Use Cases
• Path sums, diameter, lowest common ancestor in a binary tree.
• Backtracking in tree-based problems.
• Calculating max/min path sums or counting paths.
Graphs
Definition
Nodes connected by edges. Problems revolve around traversals (DFS/BFS), connected components, shortest paths, or cycles.
Common Use Cases
• Finding connected components or detecting cycles.
• Shortest path in unweighted graphs (BFS).
• Cloning or topological sorting for directed acyclic graphs.
Island / Matrix Traversal
Definition
View a grid/matrix as a graph. Each cell has potential edges (usually up, down, left, right). Perform BFS/DFS to explore connected regions.
Common Use Cases
• Counting islands or max area of islands.
• Flood fill or searching for sub-regions.
• Shortest path in a 2D grid.
Two Heaps
Definition
Maintain two heaps (a max-heap and a min-heap) to keep track of different portions of a data stream, often to find medians dynamically.
Common Use Cases
• Median of a running data stream.
• Divide data into a “small half” and a “large half.”
• Maximize capital or scheduling tasks with priorities.
Subsets
Definition
Generating all combinations or subsets of a given set, usually via backtracking or iterative BFS-like approach in the powerset.
Common Use Cases
• All subsets of a set/array.
• Subsets with duplicates, permutations, or combinations.
• Power set generation.
Modified Binary Search
Definition
Applying binary search logic to problems that aren’t simply “find an element in a sorted array.” Often searching in rotated arrays, infinite arrays, or searching for thresholds.
Common Use Cases
• Search in rotated sorted array.
• Find first/last occurrence (lower bound, upper bound).
• Peak finding, median of two sorted arrays.
Bitwise XOR
Definition
Use properties of XOR (like x ^ x = 0, x ^ 0 = x) to solve problems about finding single/missing numbers.
Common Use Cases
• Finding the single element in an array of duplicates (e.g., “Single Number”).
• Finding 2 unique numbers in an array where others appear in pairs.
• Base-10 complement or flipping bits.
Top K Elements
Definition
Use a data structure (often a heap or partial sort) to quickly find or maintain the top/bottom K items in a collection.
Common Use Cases
• Kth largest/smallest element in an unsorted array.
• Top K frequent items (words, numbers).
• K closest points to the origin.
K-Way Merge
Definition
Simultaneously merge data from multiple sorted lists/arrays, often using a min-heap to track the next smallest element.
Common Use Cases
• Merge k sorted linked lists.
• Find smallest number range containing elements from k lists.
• Kth smallest number from multiple sorted lists or a sorted matrix.
Greedy Algorithms
Definition
At each step, make the locally optimal choice with the hope it leads to a global optimum. Usually no backtracking.
Common Use Cases
• Interval scheduling, max profit in stock trading (simple repeated buys/sells).
• Minimum number of platforms or meeting rooms needed.
• Valid palindrome with limited removals (some are greedy).
0/1 Knapsack (Dynamic Programming)
Definition
Classic DP approach where we decide to include or exclude each item from a subset to achieve some target (like max value or exact sum).
Common Use Cases
• Subset sum, equal partition.
• Target sum (rearranging plus/minus to match a goal).
• Minimum subset difference or the general knapsack problem.
Backtracking
Definition
Systematically build all possible solutions by exploring partial solutions, then backtrack if constraints aren’t met.
Common Use Cases
• Generate permutations/combination sums.
• N-Queens, sudoku solver, word search.
• Expression operators (e.g., “Expression Add Operators”).
Trie
Definition
A tree-like data structure for storing strings (or sequences) character by character, enabling prefix-based lookups.
Common Use Cases
• Prefix searches, auto-complete suggestions.
• Implementing dictionary lookups.
• Storing large sets of strings efficiently.
Topological Sort (Graph)
Definition
A linear ordering of vertices in a directed acyclic graph (DAG) such that for every directed edge u -> v, node u comes before v in the ordering.
Common Use Cases
• Scheduling tasks with dependencies.
• Alien dictionary (derive order of letters from words).
• Course schedule problems.
Union Find / Disjoint Set
Definition
Data structure to keep track of elements partitioned into disjoint sets. Allows quick unions and finds of sets.
Common Use Cases
• Detect cycles in undirected graphs.
• Counting connected components (e.g., number of provinces, dynamic islands).
• Merging accounts or grouping objects.
Ordered Sets
Definition
A set (or balanced BST structure) that keeps elements in a sorted order, allowing queries like “find next higher element” or “range queries.”
Common Use Cases
• Scheduling or calendar problems (inserting intervals, finding overlaps).
• Finding rank of an element in real-time.
• Storing unique elements with the ability to do ordered iteration.
Multi-Thread
Definition
Patterns for concurrency: dividing tasks among multiple threads, ensuring safety and synchronization, or distributing work.
Common Use Cases
• Parallelizing large computations.
• Producer-consumer or readers-writers patterns.
• Synchronized iteration through shared data.
