DSA Atlas

BFS — Breadth-First Search

Explore a graph level by level using a queue. BFS finds the shortest path in unweighted graphs and is fundamental to many graph algorithms.

DFS — Depth-First Search

Dive as deep as possible before backtracking. DFS is essential for detecting cycles, topological sorting, and exploring all paths in a graph.

Graph Fundamentals

Learn the core language of nodes, edges, paths, and cycles. Graphs are the broad container that trees, BFS, DFS, Dijkstra, and MST all live inside.

0-1 BFS

Find shortest paths in graphs whose edge weights are only 0 or 1 using a deque instead of a heap.

Dijkstra's Algorithm

Find the shortest path in weighted graphs with non-negative edges. Dijkstra is BFS with a priority queue — it processes nodes in order of cumulative distance.

Minimum Spanning Tree

Find the subset of edges that connects all vertices with minimum total weight. Kruskal's and Prim's are the two classic approaches.

Topological Sort

Order the nodes of a DAG so that every edge points forward. Essential for dependency resolution, build systems, and scheduling.

Union-Find (Disjoint Set)

Track connected components efficiently with near-constant time union and find operations. The backbone of Kruskal's MST and dynamic connectivity.

Bridges and Articulation Points

Use DFS timestamps and low-link values to find the edges and vertices whose removal disconnects an undirected graph.

DSU Rollback

Add an undo stack to Union-Find so merges can be reversed during offline divide-and-conquer or time-travel style processing.

Eulerian Path

Traverse every edge exactly once by checking degree conditions and then building the walk with Hierholzer's algorithm.

Floyd-Warshall

Compute all-pairs shortest paths by gradually allowing more intermediate vertices. This is the clean dynamic-programming answer to dense shortest-path queries.

Tarjan SCC

Find strongly connected components in one DFS by tracking discovery times, low-link values, and the active stack.

Tree Fundamentals

Understand roots, parents, children, depth, height, and traversal orders. A tree is a graph with enough structure to make many problems much simpler.

Trees is a special case of Graphs.

Binary Search Tree (BST)

A sorted tree structure enabling O(log n) search, insert, and delete. Foundation for balanced trees, sets, and maps.

Trees is a special case of Graphs.

Heap & Priority Queue

A complete binary tree where every parent is smaller (or larger) than its children. The backbone of Dijkstra, event scheduling, and top-k problems.

Trees is a special case of Graphs.

Binary Lifting

Jump upward in a rooted tree by powers of two to answer k-th ancestor and many LCA-style queries quickly.

Trees is a special case of Graphs.

Euler Tour Technique

Flatten a rooted tree into an array so subtree problems become range problems. This is the bridge between trees and range-query structures.

Trees is a special case of Graphs.

Heavy-Light Decomposition

Break tree paths into O(log n) heavy-chain segments so path queries can ride on top of a segment tree instead of walking edge by edge.

Trees is a special case of Graphs.

Lowest Common Ancestor

Find the deepest shared ancestor of two nodes in a rooted tree. LCA is a core tree-query problem that ties together DFS, binary lifting, and Euler tours.

Trees is a special case of Graphs.

Treap

Combine binary-search-tree ordering with heap priorities to get a balanced randomized tree with elegant split and merge operations.

Trees is a special case of Graphs.

Prefix Sum

Precompute cumulative totals so any range sum becomes one subtraction. Prefix sums are the first serious range-query idea everyone should know.

Difference Array

Apply many range updates in O(1) each, then rebuild the final values with one prefix pass. Difference arrays are the update-side twin of prefix sums.

Fenwick Tree (Binary Indexed Tree)

Maintain prefix sums with O(log n) updates and queries using one tiny bit trick. Fenwick trees are the lightest dynamic range-query structure worth knowing.

Li Chao Tree

Maintain dynamic line insertion and min/max queries by storing line candidates in a segment tree over x-values.

Mo's Algorithm

Reorder offline range queries so a moving window can answer them with small pointer adjustments instead of rebuilding from scratch.

Persistent Segment Tree

Keep every version of a segment tree by path-copying only the changed nodes.

Segment Tree

Answer range queries and point updates in O(log n). Segment trees are the go-to structure for range sum, range min, and similar problems.

Sparse Table

Answer static range minima, maxima, or gcd queries in O(1) after O(n log n) preprocessing. Sparse tables are pure precomputation power.

Deque (Double-Ended Queue)

Push and pop from both ends in O(1). A deque can behave like a queue, a stack, or a monotonic window depending on how you use it.

Linked List Operations

Reverse, detect cycles, merge sorted lists. Linked lists test your pointer manipulation skills — every operation is about rewiring next pointers.

Queue

Process work in first-in, first-out order. Queues are the missing linear-structure foundation behind BFS, buffering, and fair scheduling.

Stack & Monotonic Stack

LIFO data structure for expression evaluation, backtracking state, and the powerful monotonic stack pattern for next-greater-element problems.

Two Pointers & Sliding Window

Shrink O(n²) brute force to O(n) by maintaining a window or two converging pointers. The go-to technique for subarray and subsequence problems.

Monotonic Queue

Maintain sliding-window candidates in sorted order inside a deque so each window maximum or minimum is available in O(1).

Binary Search

Halve the search space at every step. Binary search is not just for sorted arrays — it's a general technique for any monotonic predicate.

Merge Sort

Divide the array in half, sort each half, merge them back. Merge sort is the gold standard for stable, predictable O(n log n) sorting.

Quick Sort

Pick a pivot, partition around it, recurse on both sides. Quick sort is the fastest general-purpose sort in practice despite O(n²) worst case.

Backtracking

Systematically explore all possible solutions by building candidates incrementally and abandoning paths that cannot lead to valid solutions.

Greedy Algorithms

Make the locally optimal choice at each step to find a global optimum. Greedy works when the problem has optimal substructure and the greedy choice property.

Convex Hull Trick

Maintain a set of lines so DP transitions of the form m*x + b can be optimized by querying only the best candidate line.

Dynamic Programming

Break a problem into overlapping subproblems, solve each once, reuse the results. DP turns exponential brute force into polynomial time.

KMP (Knuth-Morris-Pratt)

Search for a pattern in linear time by reusing information about its own prefixes instead of restarting after mismatches.

Rabin-Karp

Search with rolling hashes so most windows can be rejected with arithmetic instead of full character comparisons.

Trie (Prefix Tree)

A tree-like data structure for efficient string storage and prefix-based retrieval. Essential for autocomplete, spell checking, and word search problems.

Z-Algorithm

Compute how much of the global prefix matches at every position, then reuse the active Z-box to stay linear.

Aho-Corasick

Match many patterns in one pass by augmenting a trie with failure links. This is multi-pattern search done at scale.

Manacher

Find the longest palindromic substring in linear time by reusing information from the rightmost known palindrome.

Suffix Array

Sort all suffixes of a string once, then answer many substring questions by binary searching the sorted order.

Suffix Automaton

Compress all substrings of a string into a linear-size automaton with suffix links.

Hash Map

O(1) average-case lookups via hashing. Understand collision resolution, load factors, and when hash maps are the right (or wrong) choice.

B-Tree

Store many keys per node so ordered search stays shallow and expensive page reads stay low.

B+ Tree

Keep routing keys in internal nodes and all records in linked leaves so point lookups stay shallow and range scans stay fast.

Cache Eviction Strategies (LRU, LFU, ARC, TinyLFU)

Treat cache eviction as an algorithm choice: recency, frequency, adaptation, and admission all optimize different workloads.

Consistent Hashing

Map keys onto a ring so cluster membership changes move only nearby keys instead of reshuffling the whole keyspace.

External Merge Sort

Sort data larger than RAM by generating sorted runs and merging them with mostly sequential disk I/O.

Hash Join & Merge Join

Compare the two most important database join strategies: build-and-probe hashing versus ordered merge scanning.

LSM Tree

Trade read complexity for write throughput by buffering writes in memory, flushing sorted runs, and compacting them in the background.

Skip List

Layer multiple forward-pointer lists on top of each other so ordered search behaves like a randomized tree while staying list-based.

Bloom Filter & Cuckoo Filter

Use tiny approximate membership structures to reject absent keys cheaply before touching slower storage or larger indexes.

Probabilistic systems is a special case of Systems & storage.

Count-Min Sketch

Estimate item frequencies in a stream with a tiny counter matrix, a few hash functions, and a guaranteed one-sided error.

Probabilistic systems is a special case of Systems & storage.

HyperLogLog

Estimate the number of distinct items in a huge stream with tiny registers and the statistics of rare hash patterns.

Probabilistic systems is a special case of Systems & storage.

Bit Manipulation

Use bitwise operations for efficient computation. XOR tricks, counting bits, power-of-two checks, and bitmask patterns for subsets and flags.