Definitions

0-1 BFS: 0-1 BFS is graph traversal for edge weights 0 and 1, where a weight-0 transition puts the vertex at the front of the deque and a weight-1 transition puts it at the back.
ALGORITHM: An algorithm is a finite description of steps that transforms a valid input into an output.
ALGORITHMIC PROBLEM: An algorithmic problem is a description of valid inputs, required outputs, and the condition that connects every correct output with its input.
AMORTIZED COMPLEXITY: Amortized complexity is an estimate of the average operation cost in the worst case for the whole operation sequence, not a probabilistic average over random inputs.
BACK OF DEQUE: Back of deque is the side where push_back, pop_back, and back operate.
BACK OF QUEUE: Back of queue is the side where a new item is inserted.
BIG O NOTATION: Big O notation gives an asymptotic upper bound: f(n) = O(g(n)) if, from some point onward, f(n) is no larger than a constant times g(n).
BIG OMEGA NOTATION: Big Omega notation gives an asymptotic lower bound: f(n) = Ω(g(n)) if, from some point onward, f(n) is at least a constant times g(n).
CIRCULAR BUFFER: A circular buffer is an array where the next index after the last cell becomes index 0 again.
CIRCULAR QUEUE: A circular queue is a fixed-capacity FIFO queue that stores elements in an array and reuses free cells in a circle.
DEQUE: A deque is a data structure that inserts and removes items at both ends.
DEQUEUE: dequeue is the operation that removes and returns the item at the front of a queue.
DEQUEUE: dequeue in a circular queue is the operation that reads the item at head, removes it from the logical queue, and moves head forward.
DISJOINT SETS Open article: Disjoint sets are sets that have no common elements.
DOUBLE-ENDED QUEUE: A double-ended queue is a queue whose front and back are both working sides.
DOUBLY LINKED LIST: A doubly linked list is a data structure that stores elements in nodes, where each node contains a value, a prev link to the previous node, and a next link to the next node.
DOUBLY LINKED LIST NODE: A doubly linked list node is an object or structure that stores a value, a prev link to the previous node, and a next link to the next node.
DYNAMIC ARRAY: A dynamic array is a data structure that stores elements in a contiguous buffer, supports fast access by index, and increases its capacity when needed.
DYNAMIC ARRAY CAPACITY: Dynamic array capacity is the number of elements that the current buffer can hold without a new memory allocation.
DYNAMIC ARRAY SIZE: Dynamic array size is the number of elements available to the user.
EMPTY SET Open article: The empty set is a set that contains no elements.
ENQUEUE: enqueue is the operation that adds a new item to the back of a queue.
ENQUEUE: enqueue in a circular queue is the operation that writes a new item at tail and moves tail to the next write position.
FIFO: FIFO is the first in, first out rule: the first inserted item is removed first.
FNV-1A: FNV-1a is a deterministic teaching hash function used in this article for string keys.
FRONT OF DEQUE: Front of deque is the side where push_front, pop_front, and front operate.
FRONT OF QUEUE: Front of queue is the side where the next item is read or removed.
HALF-OPEN RANGE: A half-open range includes the left boundary and excludes the right boundary, so its length is the right boundary minus the left boundary.
HASH COLLISION: A hash collision happens when different keys lead to the same table index.
HASH FUNCTION: A hash function turns a string key into a number that is then compressed into an array index.
HASH TABLE: A hash table is a data structure for key/value pairs where lookup, insertion, and deletion follow a route built from the key.
HEAD: head is the link to the first node in the list.
HEAD: head is the link to the first user node in the chain.
HEAD INDEX: The head index points to the first logical queue item when size is greater than 0.
HYPERRECTANGLE QUERY: A hyperrectangle query is a k-dimensional query where each dimension has its own half-open range.
IDEMPOTENT OPERATION: An idempotent operation is an operation where repeating one value does not change the result: op(x, x) = x.
IDEMPOTENT OPERATION: An idempotent operation in a multidimensional sparse table makes overlapping blocks safe to combine because op(x, x) = x.
LIFO: LIFO is the last in, first out rule: the last inserted item is removed first.
LIST NODE: A list node is an object or structure that stores a user value and a link to the next node.
LITTLE O NOTATION: little o notation gives a strict upper bound: f(n) = o(g(n)) if the ratio of f(n) to g(n) tends to zero.
LITTLE OMEGA NOTATION: little omega notation gives a strict lower bound: f(n) = ω(g(n)) if the ratio of f(n) to g(n) tends to infinity.
LOAD FACTOR: Load factor measures how full a hash table is and is used as a signal for resize or rehash.
LOOP INVARIANT: A loop invariant is a statement that is true before the loop starts and remains true after every iteration.
MONOTONIC DEQUE: A monotonic deque is a deque with an additional element order that helps read the minimum or maximum of a window from an end.
MULTIDIMENSIONAL SPARSE TABLE: A multidimensional sparse table is a sparse table generalized to k dimensions, where each block is described by a vector of power-of-two sizes.
NEXT LINK: The next link is the node field that points to the next node or to an empty link when the node is last.
NEXT LINK: The next link is the node field that points to the next node or to an empty link when the node is last.
OPEN ADDRESSING: Open addressing stores entries directly in the slot array and searches for another slot on collision through a probe sequence.
OVERFLOW: Overflow is an attempt to add an item when size equals capacity.
OVERLAP QUERY: An overlap query answers a range by using two equal power-of-two blocks that together cover the query.
OVERLAP QUERY: A multidimensional overlap query combines the corner blocks of a query; repeated cell coverage is correct only for an idempotent operation.
PARTIAL CORRECTNESS: Partial correctness means: if the algorithm terminates on a valid input, then its result satisfies the postcondition of the problem.
PEEK: peek is the operation that reads the top item of a stack without removing it.
PEEK: peek is the operation that reads the front of a queue without removing it.
POP: pop is the operation that removes and returns the top item of a stack.
POP_BACK: pop_back is the operation that removes and returns the item at the back of a deque.
POP_FRONT: pop_front is the operation that removes and returns the item at the front of a deque.
PREV LINK: The prev link is the node field that points to the previous node or to an empty link when the node is first.
PROPER SUBSET Open article: A proper subset is a subset that is not equal to the original set and therefore contains fewer elements.
PUSH: push is the operation that adds a new item to the top of a stack.
PUSH_BACK: push_back is the operation that adds a new item to the back of a deque.
PUSH_FRONT: push_front is the operation that adds a new item to the front of a deque.
QUADRATIC PROBING: Quadratic probing builds the next attempt with index_i = (h + c1 * i + c2 * i * i) mod capacity.
QUEUE: A queue is a data structure where the first inserted item is removed first.
QUEUE CAPACITY: Queue capacity is the length of the fixed buffer, and the structure does not grow it automatically.
RANGE QUERY: A range query asks about array values between two given boundaries.
RECTANGULAR RANGE QUERY: A rectangular range query asks about all matrix cells inside the product of one row range and one column range.
RECURRENCE RELATION: A recurrence relation is a formula that expresses the cost of a problem through the cost of smaller problems of the same kind and the work done outside those subproblems.
REHASH: Rehashing moves entries to a table with another capacity and recomputes their indices.
RESIZE: Resize is the operation of replacing the current buffer with a buffer of another capacity while preserving the active elements.
RMQ: RMQ is a range minimum query on an array.
SENTINEL NODE: A sentinel node is a dummy node that participates in list links but is not a user element.
SEPARATE BUCKETS: Separate buckets store, in each array cell, a bucket with a dynamic array of key/value entries.
SET Open article: A set in mathematics is a collection of unique elements, which may be numbers, symbols, or other objects.
SET DIFFERENCE Open article: The difference of sets A and B is the set of elements that belong to A but do not belong to B.
SET EQUALITY Open article: Two sets are equal if they contain exactly the same elements.
SET INTERSECTION Open article: The intersection of sets is the set that contains only the elements that belong to both sets.
SET UNION Open article: The union of sets is the set that contains all elements from both sets.
SINGLY LINKED LIST: A singly linked list is a data structure that stores elements in nodes, where each node contains a value and a next link to the next node in the chain.
SPACE COMPLEXITY: Space complexity is a function that estimates the extra memory used by an algorithm as a function of input size.
SPARSE TABLE: A sparse table is a data structure for a static array that precomputes answers for power-of-two blocks.
STACK: A stack is a data structure where the last inserted item is removed first.
SUBSET Open article: A subset is a set whose every element also belongs to another set.
TAIL: tail is the link to the last node in the list when the implementation stores it for fast appends.
TAIL: tail is the link to the last user node in the chain.
TAIL INDEX: The tail index points to the next free write position, not to the last item.
TERMINATION: Termination means: the algorithm finishes on every valid input.
THETA NOTATION: Theta notation gives a tight asymptotic estimate up to constant factors: f(n) = Θ(g(n)) if both f(n) = O(g(n)) and f(n) = Ω(g(n)) hold.
TIME COMPLEXITY: Time complexity is a function that estimates the number of elementary operations performed by an algorithm as a function of input size.
TOMBSTONE SLOT: A tombstone slot is a deleted open-addressing slot that stores no entry but does not stop search.
TOP OF STACK: Top of stack is the only item that can be read or removed directly.
TOTAL CORRECTNESS: Total correctness means partial correctness together with termination.
TWO-DIMENSIONAL SPARSE TABLE: A two-dimensional sparse table is a data structure for a static matrix that precomputes answers for rectangular blocks of size 2^kr x 2^kc.
UNDERFLOW: Underflow is an attempt to remove or read an item when size equals 0.
WRAP-AROUND: Wrap-around is the transition from the last array cell back to the first cell by (index + 1) % capacity.