A quick reference guide for recognizing and solving common Data Structures & Algorithms patterns.
Description: Using two pointers (e.g., left and right) to traverse an array or string. Pointers can move in the same direction or opposite directions. This often helps reduce time complexity from quadratic to linear.
left = 0 (or start) and right = array.length - 1 (or end), or left = 0 and right = 1 depending on problem.left < right, right < array.length).// Example: Check if string is palindrome
function isPalindrome(s) {
let left = 0;
let right = s.length - 1;
while (left < right) {
if (s[left] !== s[right]) {
return false;
}
left++;
right--;
}
return true;
}Description: Used on arrays or strings to find a subarray/substring that satisfies a condition, often optimizing problems that would otherwise require nested loops. It involves maintaining a "window" of elements and moving it across the data.
left = 0 (start of window), currentSum/count = 0, result = 0/Infinity.right from 0 to array.length - 1 (expand window).
array[right] to currentSum/count.currentSum/count violates a condition (or window size is fixed):
array[left] from currentSum/count (shrink window).left.result with current window properties (e.g., `max/min length`, `max/min sum`).result.// Example: Max sum subarray of size K
function maxSubarraySum(arr, k) {
let maxSum = 0;
let windowSum = 0;
let windowStart = 0;
for (let windowEnd = 0; windowEnd < arr.length; windowEnd++) {
windowSum += arr[windowEnd]; // Expand window
if (windowEnd >= k - 1) { // Window size reached
maxSum = Math.max(maxSum, windowSum);
windowSum -= arr[windowStart]; // Shrink window
windowStart++;
}
}
return maxSum;
}Description: Precomputing sums of elements up to each index in an array (or matrix) to quickly find the sum of any subarray/range in $O(1)$ time. This avoids re-calculating sums for every query.
// Example: Calculate prefix sums
function getPrefixSums(arr) {
let prefixSums = new Array(arr.length + 1).fill(0);
for (let i = 0; i < arr.length; i++) {
prefixSums[i + 1] = prefixSums[i] + arr[i];
}
return prefixSums;
}
// Sum of arr[i...j] is prefixSums[j+1] - prefixSums[i]Description: Using hash-based data structures (objects/Maps/Sets) for efficient $O(1)$ average time lookups, insertions, and deletions. They provide quick access to data based on a key.
// Example: Two Sum
function twoSum(nums, target) {
const numMap = new Map(); // Stores number -> index
for (let i = 0; i < nums.length; i++) {
const complement = target - nums[i];
if (numMap.has(complement)) {
return [numMap.get(complement), i];
}
numMap.set(nums[i], i);
}
return [];
}Description:
// Example: Valid Parentheses (Stack)
function isValid(s) {
const stack = [];
const map = { '(': ')', '[': ']', '{': '}' };
for (let char of s) {
if (map[char]) { // If it's an opening bracket
stack.push(char);
} else { // If it's a closing bracket
if (stack.length === 0 || map[stack.pop()] !== char) {
return false;
}
}
}
return stack.length === 0;
}// Example: Basic BFS (for graph traversal)
function bfs(startNode) {
const queue = [startNode];
const visited = new Set();
visited.add(startNode);
while (queue.length > 0) {
const node = queue.shift(); // Dequeue
// Process node (e.g., print node.value)
for (let neighbor of node.neighbors) { // Assuming node has a 'neighbors' array
if (!visited.has(neighbor)) {
visited.add(neighbor);
queue.push(neighbor); // Enqueue
}
}
}
}Description: Using two pointers that traverse a linked list (or sometimes an array/sequence) at different speeds (e.g., one moves one step at a time, the other two steps). This is effective for problems where you need to find relative positions or detect cycles.
// Example: Detect Cycle in Linked List
function hasCycle(head) {
if (!head || !head.next) return false; // Need at least two nodes for a cycle
let slow = head;
let fast = head.next; // Start fast one step ahead
while (slow !== fast) {
if (!fast || !fast.next) { // If fast reaches end, no cycle
return false;
}
slow = slow.next;
fast = fast.next.next;
}
return true; // Cycle detected
}Description: A tree-like data structure used to store a dynamic set of strings, where nodes represent characters and paths from the root represent prefixes. It's highly optimized for prefix-based searches and string operations.
// Basic TrieNode structure
class TrieNode {
constructor() {
this.children = {}; // Map of char -> TrieNode
this.isEndOfWord = false;
}
}
// (Insert/Search methods would be added to a Trie class that holds the root node)Description: A specialized tree-based data structure that satisfies the heap property: parent nodes are always greater than or equal to (Max Heap) or less than or equal to (Min Heap) their children. This structure enables efficient extraction of the minimum or maximum element ($O(1)$ peek, $O(\log N)$ extract/insert).
Description: Traverses a graph or tree by exploring as far as possible along each branch before backtracking. It goes deep into one path before exploring other branches. Typically implemented with recursion (which uses the call stack) or an explicit stack data structure.
function dfs(node, visited, target) {
// Base Case 1: If node already visited in current path (prevents cycles in undirected graphs)
if (visited.has(node)) return false;
visited.add(node); // Mark current node as visited
// Base Case 2: If target found
if (node === target) return true;
// Recursive Step: Explore neighbors
for (let neighbor of node.neighbors) { // Assuming graph nodes have a 'neighbors' property
if (dfs(neighbor, visited, target)) {
return true; // If target found in any child branch, propagate true upwards
}
}
// Backtrack (if needed for state changes, like in Word Search)
// visited.delete(node); // Uncomment if problem requires backtracking on visited state
return false; // Target not found in this branch
}Description: Traverses a graph or tree level by level. It explores all neighbors at the current depth before moving on to nodes at the next depth level. Typically implemented with a queue.
function bfs(startNode, target) {
const queue = [{ node: startNode, distance: 0 }]; // Store node and its distance/level
const visited = new Set();
visited.add(startNode);
while (queue.length > 0) {
const { node, distance } = queue.shift(); // Dequeue
if (node === target) return distance; // Target found, return distance/level
for (let neighbor of node.neighbors) { // Assuming node has a 'neighbors' array
if (!visited.has(neighbor)) {
visited.add(neighbor);
queue.push({ node: neighbor, distance: distance + 1 }); // Enqueue with incremented distance
}
}
}
return -1; // Target not reachable
}Description: An efficient algorithm for finding an item from a sorted list of items by repeatedly dividing the search interval in half. It works by comparing the target value to the middle element of the array.
// Example: Standard Binary Search
function binarySearch(arr, target) {
let low = 0;
let high = arr.length - 1;
while (low <= high) {
let mid = low + Math.floor((high - low) / 2);
if (arr[mid] === target) {
return mid;
} else if (arr[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1;
}Description: Solving complex problems by breaking them down into simpler, overlapping subproblems and storing the results of these subproblems (memoization or tabulation) to avoid redundant calculations. It's about optimizing recursive solutions.
// Example: Fibonacci (Tabulation)
function fib(n) {
if (n <= 1) return n;
const dp = new Array(n + 1);
dp[0] = 0;
dp[1] = 1;
for (let i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}Description: Making the locally optimal choice at each step with the hope that this sequence of local optimal choices will lead to a globally optimal solution. This strategy does not always work, and often requires proof of correctness.
Description: A refined brute-force approach used to explore all possible solutions to a problem. It builds a solution incrementally, and if a partial solution cannot lead to a valid complete solution, it "backs up" (undoes the last choice) and tries another path. Often implemented using recursion.
// Pseudo-code structure for Backtracking
function backtrack(combination, candidates, results) {
// 1. Base Case: If a complete solution is found
if (isSolution(combination)) {
results.push([...combination]); // Add a copy of the solution
return;
}
// 2. Explore choices
for (let i = 0; i < candidates.length; i++) { // Or iterate through available choices
let choice = candidates[i];
// Pruning: Check if the current choice can lead to a valid solution
if (isValid(choice, combination)) {
// 3. Make choice
combination.push(choice);
// (Optionally: adjust candidates for next recursion, e.g., candidates.slice(i+1))
// 4. Recurse
backtrack(combination, candidates, results);
// 5. Unmake choice (backtrack): Restore state for next iteration
combination.pop();
// (Optionally: restore candidates if they were modified)
}
}
}