Learn how to choose data structures, analyze complexity, and solve common programming problems using arrays, strings, hash maps, stacks, queues, linked lists, trees, graphs, recursion, searching, and sorting.
Analyze algorithm time and space complexity
Choose data structures based on required operations
Solve common array, string, and hash-map problems
Use stacks, queues, linked lists, trees, and graphs
Apply recursion, searching, sorting, and traversal strategies
Recognize reusable problem-solving patterns such as two pointers and sliding windows
Big O notation describes how an algorithm's resource usage grows as the input becomes larger. It is commonly used to compare time and space complexity.
When analyzing complexity, focus on the dominant growth term rather than exact execution time or small constant factors.
O(1) is constant growth
O(log n) commonly appears when the search space is repeatedly divided
O(n) grows linearly with input size
Nested full-input loops commonly produce O(n²)
function firstItem(values) {
// O(1)
return values[0];
}
function contains(values, target) {
// O(n)
for (const value of values) {
if (value === target) return true;
}
return false;
}
function allPairs(values) {
// O(n²)
for (const a of values) {
for (const b of values) {
console.log(a, b);
}
}
}Arrays provide ordered indexed storage and are one of the most common structures used in algorithm problems. Strings can often be treated as sequences of characters.
Many problems become easier when you understand indexing, traversal, mutation costs, and how to build results without unnecessary nested loops.
Array access by index is typically O(1)
Searching an unsorted array is typically O(n)
Insertion near the beginning can require shifting elements
Strings are commonly processed character by character
function reverseString(value) {
const chars = [...value];
let left = 0;
let right = chars.length - 1;
while (left < right) {
[chars[left], chars[right]] = [
chars[right],
chars[left],
];
left += 1;
right -= 1;
}
return chars.join("");
}
console.log(reverseString("hello"));
// "olleh"Hash-based structures provide fast average-case lookup by key. They are especially useful for frequency counting, duplicate detection, membership checks, and mapping one value to another.
Using extra memory can often reduce an algorithm from nested-loop time complexity to a single traversal.
Use Set for fast membership checks
Use Map for key-value relationships
Frequency maps are common in string and array problems
Hashing often trades additional space for faster lookup
function containsDuplicate(values) {
const seen = new Set();
for (const value of values) {
if (seen.has(value)) {
return true;
}
seen.add(value);
}
return false;
}
console.log(containsDuplicate([1, 2, 3, 2]));
// trueThe two-pointer pattern uses two indexes that move through a collection according to a relationship between values.
It is especially useful for sorted arrays, palindrome checks, in-place transformations, and problems that compare elements from opposite ends.
Pointers can move toward each other
Pointers can also move in the same direction at different speeds
Sorted input often makes two-pointer solutions possible
Two pointers can reduce unnecessary nested iteration
function isPalindrome(value) {
let left = 0;
let right = value.length - 1;
while (left < right) {
if (value[left] !== value[right]) {
return false;
}
left += 1;
right -= 1;
}
return true;
}
console.log(isPalindrome("racecar"));
// trueSliding-window algorithms maintain information about a contiguous region of an array or string while moving that region through the input.
Instead of recomputing the entire region each time, the algorithm updates the current window as values enter and leave.
Use sliding windows for contiguous subarrays or substrings
Fixed-size windows maintain a constant width
Variable-size windows expand and shrink based on a condition
Reuse previous window work instead of recomputing it
function maxWindowSum(values, size) {
if (values.length < size) return null;
let sum = 0;
for (let i = 0; i < size; i += 1) {
sum += values[i];
}
let best = sum;
for (let right = size; right < values.length; right += 1) {
sum += values[right];
sum -= values[right - size];
best = Math.max(best, sum);
}
return best;
}Stacks follow last-in, first-out ordering. They are useful when the most recently encountered item needs to be processed first.
Stacks commonly appear in parsing, undo systems, expression evaluation, recursion simulation, and matching-delimiter problems.
Stacks use LIFO ordering
Push adds to the top
Pop removes the most recently added item
Stacks are useful for nested structures
function isValidParentheses(value) {
const stack = [];
const pairs = {
")": "(",
"]": "[",
"}": "{",
};
for (const char of value) {
if (char === "(" || char === "[" || char === "{") {
stack.push(char);
continue;
}
if (stack.pop() !== pairs[char]) {
return false;
}
}
return stack.length === 0;
}Queues follow first-in, first-out ordering. The earliest added item is processed before newer items.
Queues are commonly used for task processing, breadth-first traversal, scheduling, buffering, and event systems.
Queues use FIFO ordering
Enqueue adds items to the back
Dequeue removes items from the front
Breadth-first search commonly uses a queue
const queue = [];
queue.push("task-a");
queue.push("task-b");
queue.push("task-c");
while (queue.length > 0) {
const task = queue.shift();
console.log(`Processing ${task}`);
}A linked list stores values in nodes connected through references. Each node typically contains a value and a reference to the next node.
Linked lists do not provide direct indexed access, but insertion or removal can be efficient when the relevant node position is already known.
Nodes store values and links
Linked-list lookup is typically O(n)
Insertion at the head can be O(1)
Pointer manipulation is central to linked-list problems
function reverseList(head) {
let previous = null;
let current = head;
while (current) {
const next = current.next;
current.next = previous;
previous = current;
current = next;
}
return previous;
}Recursion solves a problem by reducing it to smaller versions of itself. Every recursive solution needs a reachable base case.
Backtracking explores possible choices and reverses a choice when it cannot lead to a valid solution.
Every recursive algorithm requires a base case
Recursive calls should move toward the base case
Backtracking follows choose, explore, and undo steps
Recursion uses the call stack
function permutations(values) {
const result = [];
function backtrack(path, remaining) {
if (remaining.length === 0) {
result.push([...path]);
return;
}
for (let i = 0; i < remaining.length; i += 1) {
path.push(remaining[i]);
backtrack(
path,
[...remaining.slice(0, i), ...remaining.slice(i + 1)],
);
path.pop();
}
}
backtrack([], values);
return result;
}Trees model hierarchical relationships through nodes and child connections. Binary trees limit each node to at most two children.
Tree problems commonly require recursive traversal, iterative traversal with a stack or queue, or reasoning about subtrees.
Trees represent hierarchical relationships
Preorder, inorder, and postorder are depth-first traversals
Breadth-first traversal processes levels
Binary search trees maintain an ordering relationship
function inorder(node, result = []) {
if (!node) return result;
inorder(node.left, result);
result.push(node.value);
inorder(node.right, result);
return result;
}Graphs model relationships between vertices connected by edges. They can represent social networks, roads, dependencies, web links, and many other systems.
Depth-first search and breadth-first search are foundational techniques for exploring reachable nodes.
Graphs consist of vertices and edges
Graphs can be directed or undirected
Visited tracking prevents repeated traversal
DFS commonly uses recursion or a stack, while BFS uses a queue
function bfs(graph, start) {
const queue = [start];
const visited = new Set([start]);
while (queue.length > 0) {
const node = queue.shift();
console.log(node);
for (const neighbor of graph[node] ?? []) {
if (!visited.has(neighbor)) {
visited.add(neighbor);
queue.push(neighbor);
}
}
}
}Binary search repeatedly removes half of a sorted search space by comparing the target to a midpoint.
The broader binary-search pattern can also be used to find boundaries or the smallest or largest value satisfying a monotonic condition.
Ordinary binary search requires sorted data
Each comparison removes about half of the remaining search space
Typical time complexity is O(log n)
Carefully maintain left and right boundaries
function binarySearch(values, target) {
let left = 0;
let right = values.length - 1;
while (left <= right) {
const middle = Math.floor((left + right) / 2);
if (values[middle] === target) {
return middle;
}
if (values[middle] < target) {
left = middle + 1;
} else {
right = middle - 1;
}
}
return -1;
}Sorting arranges values according to an ordering rule and can simplify later searching, grouping, or comparison operations.
Different sorting algorithms have different performance and memory characteristics. Comparison-based efficient general-purpose algorithms commonly target O(n log n) time.
Simple algorithms such as selection sort are useful for learning
Merge sort divides and combines sorted subproblems
Quicksort partitions around a pivot
Built-in sorting is usually preferred in application code unless implementing the algorithm is itself the goal
function mergeSort(values) {
if (values.length <= 1) return values;
const middle = Math.floor(values.length / 2);
const left = mergeSort(values.slice(0, middle));
const right = mergeSort(values.slice(middle));
const result = [];
let i = 0;
let j = 0;
while (i < left.length && j < right.length) {
if (left[i] <= right[j]) {
result.push(left[i++]);
} else {
result.push(right[j++]);
}
}
return [...result, ...left.slice(i), ...right.slice(j)];
}