Glossary
51 standard terms used throughout the algorithm practice section.
| Term | Explanation |
|---|---|
| Adjacency List | A way to store a graph where each vertex keeps a list of its neighbors — memory-efficient for sparse graphs. |
| algorithm | A clear sequence of steps that solves a problem. |
| amortized | The average cost per operation across a long sequence of operations. |
| Anagram | Two strings made of the same characters in the same counts, differing only in order. |
| array | A list of elements laid out contiguously in memory, indexed in O(1). |
| Backtracking | Try every option; when a constraint is violated, undo the last step and try another. |
| BFS | Traverse a graph/tree level by level using a queue — handy for shortest paths in an unweighted graph. |
| Big-O | Notation describing complexity as n → ∞, dropping constant factors. |
| Binary Search | Halve the search space each step on a sorted array, reaching O(log n). |
| Binary Search Tree | A binary tree where every left node is smaller and every right node is larger — O(log n) search/insert/delete when balanced. |
| brute force | A naive approach that tries every possibility, usually O(n²) or worse. |
| data structure | A way of organizing data so it can be operated on efficiently. |
| DFS | Traverse a graph/tree by going as deep as possible down one branch before backtracking, using a stack or recursion. |
| Divide and Conquer | Split a problem into independent parts, solve each, then combine the results — e.g. merge sort, quick sort. |
| DP-1D | Store sub-problem results in a one-dimensional dp[] array to avoid recomputation. |
| Dynamic Programming | Break a problem into overlapping sub-problems and store their results to avoid recomputation — usually built with recursion + memoization or a dp table. |
| edge case | An unusual input at the boundary (empty, single element, maximum). |
| Fast & Slow Pointers | Two pointers moving at different speeds over a linked list — detects cycles and finds the middle (Floyd's algorithm). |
| graph | A set of vertices connected by edges. |
| greedy | At each step pick the locally best choice without looking ahead. |
| hash collision | When two distinct keys hash to the same index. |
| Hash Map | A data structure storing key→value pairs with average O(1) lookup. |
| Hash Set | A set of unique elements with average O(1) membership checks. |
| Heap | A binary tree with the min/max at its root, supporting O(log n) operations. |
| In-place | Transform data directly in the original structure using O(1) extra memory, without making a copy. |
| Intervals | Problems over a list of [start, end] pairs — sort by start, then merge or insert overlapping intervals. |
| Invariant | A condition that always holds at each step of a loop or algorithm — the key to proving correctness. |
| iteration | Repeating steps through a for/while loop. |
| Kadane's Algorithm | Finds the contiguous subarray with the largest sum in O(n) by accumulating and resetting when the running sum goes negative. |
| linked list | A chain of nodes pointing to one another — O(1) insert/remove at the head but O(n) indexed access. |
| Memoization | Cache the result of each recursive call by its arguments so every state is computed only once (top-down). |
| monotonic stack | A stack whose elements stay strictly increasing or decreasing, used for next-greater-element problems. |
| optimal | The best solution by a given criterion (usually time or space). |
| Palindrome | A string that reads the same forward and backward, e.g. "level". |
| pointer | A variable that points to a position in an array/string. |
| Prefix Sum | A running-total array that returns the sum of any range [i, j] in O(1) after O(n) preprocessing. |
| Priority Queue | A queue that always removes the highest-priority (smallest or largest) element, usually backed by a heap with O(log n) push/pop. |
| queue | A FIFO structure — first in, first out. |
| recursion | A function that calls itself on a smaller input. |
| Sliding Window | Maintain a contiguous sub-window that slides across the array/string, updating its state in O(1) per step. |
| space complexity | The auxiliary memory an algorithm requires. |
| stack | A LIFO structure — last in, first out. |
| Subarray | A contiguous segment of elements within an array. |
| Subsequence | A sequence that keeps the original order but may skip elements — not necessarily contiguous. |
| time complexity | How the number of steps grows with input size. |
| Topological Sort | Order the vertices of a directed acyclic graph so that for every edge u→v, u comes before v. |
| trade-off | A balance struck between two criteria (usually time vs space). |
| tree | A connected acyclic graph; in the rooted form every node except the root has exactly one parent. |
| Trie | A prefix tree where each node is a character, used for autocomplete and prefix search. |
| Two Pointers | Use two pointers moving toward or alongside each other to scan a sorted array or find a pair that meets a condition. |
| Union-Find | A structure managing disjoint sets, supporting union and find in near O(1) thanks to path compression and union by rank. Also called DSU. |
Showing 51 of 51 terms