Learning Roadmap

An array is a contiguous block of memory storing elements of the same type. It is the most fundamental data structure and the backbone of many algorithms. Random access in O(1) makes arrays ideal for index-based lookups, but insertions and deletions in the middle are costly.

Strings are sequences of characters — effectively arrays of chars. Most languages treat them as immutable, which means every concatenation creates a new allocation. Mastering string manipulation requires understanding character encoding, frequency counting, and pattern matching.

A hash map (dictionary) maps keys to values using a hash function to compute an index into a backing array. It provides average-case O(1) for insert, delete, and lookup — making it the most versatile tool for trading space for speed. Hash sets offer the same performance for membership testing.

Sliding window is a technique for reducing a nested loop over subarrays/substrings to a single O(n) pass. You maintain a window defined by two pointers (left, right) and expand or shrink it based on a constraint. It is the go-to pattern whenever the problem asks for a contiguous subarray or substring satisfying some condition.

A stack is a Last-In-First-Out (LIFO) data structure. Elements are pushed onto the top and popped from the top. Stacks are essential for problems involving nested structures, backtracking, and maintaining a running context — such as matching brackets, evaluating expressions, and tracking the next greater element.

A queue is a First-In-First-Out (FIFO) data structure. Elements are enqueued at the rear and dequeued from the front. Queues are indispensable for Breadth-First Search (BFS), level-order tree traversal, and any problem where processing order must follow arrival order.

A linked list is a sequence of nodes where each node holds a value and a pointer to the next node. Unlike arrays, nodes are scattered in memory, so random access is O(n). However, insertion and deletion at a known position are O(1) — no shifting needed. Two-pointer (fast/slow) techniques solve many linked-list problems elegantly.

A tree is a connected, acyclic graph with a designated root. Binary trees (at most 2 children) are the most common interview topic. Binary Search Trees (BSTs) maintain the invariant left < node < right, enabling O(log n) operations on balanced trees. DFS and BFS are the two fundamental traversal strategies.

A graph is a set of nodes (vertices) connected by edges. Edges can be directed or undirected, weighted or unweighted. Graphs model networks, dependencies, and spatial problems. DFS and BFS are the core traversal algorithms; topological sort and union-find are essential for directed and connectivity problems respectively.

A heap is a complete binary tree satisfying the heap property: in a min-heap, every parent is ≤ its children; in a max-heap, every parent is ≥ its children. This guarantees O(1) access to the minimum (or maximum) element and O(log n) insertion/deletion. Heaps power priority queues and the top-K family of problems.

Binary search eliminates half the search space with each comparison, achieving O(log n). It works on any monotonic function — not just sorted arrays. The key insight is: if you can define a predicate that is false for a prefix and true for a suffix (or vice versa), binary search finds the boundary.

Backtracking is a systematic trial-and-error search that builds candidates incrementally and abandons (backtracks) a path as soon as it determines the path cannot lead to a valid solution. It explores a decision tree via DFS, pruning branches early to avoid unnecessary work.

Dynamic programming (DP) solves complex problems by breaking them into overlapping sub-problems and storing their results to avoid redundant computation. It applies when a problem has optimal substructure (the optimal solution contains optimal solutions to sub-problems) and overlapping sub-problems (the same sub-problem is solved more than once).