Coding Patterns Explorer

Core operations used to maintain the heap property in a binary heap. `siftUp` is used after insertion, moving a new element up the tree until its correct position is found. `siftDown` is used after removing the root, moving a replacement element down the tree to restore the heap order. Both operations have a time complexity of O(log N), ensuring the efficiency of the heap.

A specific tree traversal strategy where the current node is processed first, followed by the recursive traversal of its left subtree, and then its right subtree. This 'Root-Left-Right' order is useful for tasks like creating a copy of a tree or serializing it for later reconstruction.

This pattern uses a hash map (dictionary) to group elements from a collection based on a shared, computed property. Each key in the map represents a unique property value, and the corresponding value is a collection of all elements sharing that property. This is extremely useful for problems where you need to find pairs or groups of items with a common characteristic, transforming a search problem into an efficient lookup.

A coding pattern where variables intended to hold a minimum or maximum are initialized to the largest or smallest possible value for their data type (e.g., `infinity`, `INT_MAX`). This simplifies loop logic by ensuring the first element processed will always satisfy the initial comparison, eliminating the need for special conditional checks for the first iteration or an empty state.

This technique uses a variable to track the upper bound of a continuous range of values (e.g., from 1 to 'reach') that can be formed. The algorithm's main loop iteratively extends this range by incorporating elements from the input or adding new ones. The process continues until the range is large enough to satisfy the problem's condition, such as covering all numbers up to a target 'n'.

An algorithmic pattern for finding the number of disjoint subgraphs (components) in an undirected graph. It involves iterating through all vertices. If a vertex has not yet been visited, it signifies a new component. A counter is incremented, and a graph traversal (like DFS or BFS) is initiated from that vertex to find and mark all vertices belonging to the same component.

A conditional statement placed at the beginning of a function to handle edge cases or invalid inputs, such as a null tree root. If the condition is not met, the function returns immediately with a default or empty result. This pattern improves code readability by separating edge case handling from the main logic and avoiding deeply nested conditional blocks.

A pattern for computing a single aggregate value over an array using an associative binary operation (e.g., sum, product, min, max, GCD, LCM). It initializes a result with the first element and then iterates through the remaining elements, repeatedly applying the operation between the current result and the next element.

Iterates through the digits of an integer using a loop. In each iteration, the modulo operator (`% 10`) extracts the last digit, and integer division (`/ 10`) removes it. This process continues until the number becomes zero. This is a fundamental technique for problems requiring manipulation of individual digits, such as reversing a number or summing its digits.

A behavioral design pattern that provides a way to access the elements of an aggregate object (like a collection or sequence) sequentially without exposing its underlying representation. It encapsulates the state and logic of traversal into a separate iterator object. This pattern is fundamental for creating generators and processing sequences, especially when the sequence is infinite or computationally expensive to generate all at once.

A coding practice where edge cases and invalid conditions are checked at the beginning of a function, leading to an early exit. This de-clutters the main logic by handling preconditions upfront. The use of `guard n > 1` and `guard effectiveK != 0` makes the code cleaner and more robust by separating the core algorithm from the handling of trivial cases.

A custom implementation of a priority queue, often using a binary heap, when one is not available in a language's standard library. It provides efficient logarithmic time complexity for insertion (enqueue) and extraction of the minimum element (dequeue). This data structure is fundamental for implementing efficient versions of algorithms like Dijkstra's, A*, and Prim's.

A technique using two pointers to traverse two sorted arrays concurrently. By comparing elements at the current pointer positions, one can efficiently merge, compare, or process elements from both arrays in a single pass. This pattern is used to iterate through the sorted horizontal and vertical cuts, selecting the greater of the two at each step.

Initializing a data structure with a special 'sentinel' value (e.g., -1) that acts as a base or boundary marker. This simplifies logic within a loop by handling edge cases (like the beginning of a sequence or an empty state) without requiring separate conditional checks. It helps create a uniform calculation logic for all cases.

Transforming numbers into a more structured representation based on their mathematical properties, such as prime factors or, in this case, an odd part and a power-of-two exponent. This often reveals underlying patterns and simplifies comparisons and relationships between numbers.

An approach where decisions are made to find a local optimum at each step, hoping it leads to a global solution. In this code, it's used to pack as many words as possible onto a single line by adding them one by one as long as they fit within a constraint (maxWidth). This is common in optimization, scheduling, and partitioning problems.

The practice of checking for and handling unexpected, empty, or invalid inputs at the beginning of a function. This prevents runtime errors and ensures the algorithm behaves correctly for all possible inputs, such as an empty array or null values. Using guard clauses or initial `if` checks is a common implementation.

Converting an undirected tree into a rooted, directed tree by performing a Depth First Search (DFS) from a designated root node. During traversal, a `parent` parameter is passed to recursive calls to avoid traversing edges backward, thus establishing a clear parent-child hierarchy.

Maintaining an aggregate value (like a sum or count) in a separate variable rather than re-calculating it from a collection on each access. This variable is updated incrementally whenever an element is added to or removed from the collection, typically reducing the complexity of fetching the aggregate from O(N) to O(1).

A technique used to process a continuous stream of data by maintaining a buffer or 'window' of a fixed maximum size. As new elements arrive, they are added to one end of the window, and if the size limit is exceeded, the oldest elements are removed from the other. This is useful for focusing computations on the most recent data, such as finding patterns in suffixes of a stream, and helps optimize memory by not storing the entire data history.

A strategy where an expensive, one-time setup phase is performed to build a data structure (like a graph). This structure is then used to answer multiple subsequent queries efficiently. This amortizes the initial setup cost over all queries, improving overall performance when the number of queries is large.

After reducing a problem to the standard linear equation form `Ax = B`, this pattern involves a systematic case analysis based on the coefficients. It checks if `A` is zero or non-zero. If `A` is zero, it further checks the value of `B` to distinguish between infinite solutions (`0x = 0`) and no solution (`0x = C`). This is the fundamental logic for solving any single-variable linear equation.

A performance optimization for search algorithms where only one solution is needed. Once a complete solution is found, a success signal (e.g., a boolean `true`) is propagated up the recursion stack. This immediately terminates all active recursive calls, preventing the algorithm from wasting time searching for other potential solutions after one has already been secured.

A modification of a standard shortest path algorithm, like Dijkstra's, to find not just the minimum path but the k-th shortest path. This is achieved by storing the 'k' best-known distances for each node instead of just one. When a new path to a node is found, its cost is compared against the stored distances, and the set of best distances is updated. A priority queue is essential to efficiently explore paths in increasing order of cost.

A common coding pattern for converting characters from a fixed-size alphabet (e.g., lowercase English letters) into integer indices (e.g., 0-25). This is typically done by subtracting the ASCII/Unicode value of the first character of the alphabet. It enables the use of arrays for efficient, O(1) lookups based on character values, which is faster than using hash maps.

A fundamental technique where an array or list is first sorted based on a specific criterion. This pre-processing step arranges the data in a way that allows for efficient processing in a subsequent linear scan. The sorted order often reveals properties or relationships that simplify the problem's logic, enabling greedy or single-pass solutions.

The algorithm inspects one or more upcoming elements in a sequence without advancing the main pointer. This 'peek' operation helps in making decisions about how to process the current element. It's fundamental in parsing, allowing the algorithm to differentiate between patterns that share a common prefix.

A design pattern where a public-facing function provides a clean, simple interface, while a private helper function handles the complex recursive logic. The helper often requires additional state-tracking parameters (e.g., depth, index, accumulator) that would clutter the public API. This encapsulates complexity and improves code usability and maintainability by separating the 'what' from the 'how'.

Performing date and time calculations (like adding days, months, or years) using a dedicated calendar object or library. This approach correctly handles complex rules such as leap years, different numbers of days in months, and daylight saving time transitions. It is a robust and safe alternative to manual calculations which are often error-prone.

A spatial partitioning strategy that recursively divides a two-dimensional area into four equal quadrants. This method is a specific form of Divide and Conquer, commonly used for problems involving spatial queries, such as finding objects within a region or analyzing spatial data. It efficiently narrows down the search space by focusing only on relevant areas.

Use a boolean variable (a 'flag') to track the state of an item or condition within a loop. The flag is initialized to a default value (e.g., `true`) and is updated only when a specific condition is met. After the loop completes or exits early, the final value of the flag is used to make a decision. This pattern simplifies logic by separating the state-checking process from the final action.

This pattern leverages the properties of arithmetic progressions. For a sequence of 'k' consecutive integers, their sum 'S' is related to their average. If 'k' is odd, the middle term is exactly the average, S/k. This implies that for a solution to exist, the sum 'S' must be perfectly divisible by 'k'. This property allows for direct calculation of the sequence's terms, transforming a potential search problem into a simple arithmetic check and calculation.

Using two pointers (or indices) to define and process a contiguous sub-array or 'chunk' of a larger sequence. One pointer marks the start of the current chunk, and the second pointer advances to find its end based on a specific condition. The main loop then processes this chunk and advances the start pointer to the end of the processed chunk for the next iteration.

A technique to rapidly calculate combinations (nCr) by pre-calculating and storing factorials and their modular inverses in arrays. After an initial O(N) precomputation step, where N is the maximum required value, any nCr can be computed in O(1) time. This time-space tradeoff is highly effective in problems requiring many combinatorial calculations.

An efficient method for counting the number of set bits (1s) in an integer's binary representation, also known as population count or Hamming weight. The core operation `n &= (n - 1)` clears the least significant set bit. The loop continues until the number is zero, and the number of iterations gives the total count of set bits.

Encapsulates synchronization primitives, such as semaphores or mutexes, as private members within a class. The class's public methods provide a controlled interface for concurrent operations, hiding the complex synchronization logic from the caller. This approach improves code organization and safety by managing the state transitions required for correct concurrent execution internally.

Explicitly identifying and implementing separate logic for special conditions that don't fit the general processing algorithm. Common edge cases include the first or last element, single-item collections, or empty inputs. Here, the last line and single-word lines are handled with a simpler formatting rule, which simplifies the main justification logic.

Reduces a large or infinite state space to a smaller, finite one by using the properties of the modulo operator. Instead of tracking actual numeric values, the state is defined by their remainders with respect to a modulus `k`. This is highly effective when problem constraints depend on sums, differences, or products modulo `k`, allowing for a fixed-size DP table or lookup map (e.g., size `k` or `k*k`) regardless of the magnitude of the input numbers.

A defensive programming technique where a result variable is initialized to a valid default or fallback value before a search or loop begins. This handles edge cases where the loop might not find a suitable answer, ensuring that the function always returns a predictable and valid result as defined by the problem's constraints (e.g., returning the first element for wrap-around behavior).

An algorithmic strategy where the input data is iterated over twice. The first pass typically collects summary information or builds an auxiliary data structure (e.g., a frequency map, prefix sums). The second pass then uses this pre-computed information to make decisions or calculate the final result. This separates the data gathering phase from the processing phase, simplifying logic.

A principle from graph theory used to validate a structure. For a valid tree, the sum of all nodes' in-degrees must equal the sum of all out-degrees. This can be adapted to validate serialized trees by tracking the 'degree balance' in a single pass. A non-null node consumes one in-degree and provides two out-degrees, while a null node consumes one in-degree and provides zero.

A strategy for handling key collisions when building a map that associates keys with multiple values. When inserting a key-value pair, if the key already exists and its value is a single item, that single item is 'promoted' into a collection (like an array) containing both the old and new values. If the value is already a collection, the new value is simply appended. This avoids overwriting data and handles one-to-many relationships dynamically.

Analyzing problem constraints (e.g., value ranges) to precisely determine the required size of the state space, such as a DP table. This avoids allocating excessive memory by finding the tightest possible bounds on state values, which is crucial for making solutions efficient and feasible within memory limits.

An efficient algorithm to iterate through all subsets (submasks) of a given bitmask. Using the expression `submask = (submask - 1) & mask`, one can traverse from a given mask down through all of its submasks. This is significantly faster than generating all possible numbers and checking if they are submasks, making it a key technique in dynamic programming on subsets and other combinatorial problems.

Using a hash map (or dictionary) to store the states of a dynamic programming solution. This is ideal when DP state keys are non-contiguous, sparse, or represent large numbers, making a traditional array-based DP table impractical. It provides O(1) average time for state lookups and updates, optimizing space and maintaining performance.

A decision-making algorithm, often used in game theory, for finding an optimal move. It works by minimizing the possible loss in a worst-case scenario. For each possible move, it considers the opponent's best possible response (which maximizes their gain and your loss) and chooses the move that leads to the minimum of these maximum losses.

A common method to determine if a sequence, such as a string, is a palindrome. It works by creating a reversed version of the sequence and comparing it for equality with the original. This approach is often very concise and readable, especially in languages with built-in or simple reversal capabilities for data structures.

Builds a collection of solutions, such as combinations or subsets, step-by-step. The process starts with a base case (e.g., a list containing an empty list). It then iterates through each input element, and for each one, it generates new solutions by adding that element to all previously constructed solutions. This 'cascading' method systematically creates all possible outcomes without using recursion.

An algorithmic strategy where input items representing events are first sorted by their timestamp. By processing events in chronological order, the algorithm can simulate a process over time and determine the state of the system at any given moment. This is essential for problems that ask for the 'earliest' or 'first' time a certain condition is met.

A dynamic programming approach to find the longest sequence of elements that are in increasing order, adapted for multi-dimensional data. The state `dp[i]` represents the length of the longest increasing path ending at element `i`. It's calculated by iterating through preceding elements `j` and updating `dp[i]` based on `dp[j]` if element `j` can extend the sequence.

A common application of topological sorting. If a topological sort is attempted on a graph with 'N' nodes and the resulting sorted list contains fewer than 'N' nodes, it confirms the presence of at least one cycle. Nodes within a cycle will never have their in-degrees reduced to zero.

A top-down parsing strategy where a set of mutually recursive functions is used to process an input stream. Each function corresponds to a rule in a formal grammar, making it a direct implementation of that grammar. This approach is highly effective for parsing structured text like code or expressions, as the function call hierarchy naturally handles nested structures.

An algorithmic approach where an initial assumption or deduction imposes constraints on other parts of the problem. The algorithm propagates these constraints through the system and then verifies that no contradictions arise. In this solution, fixing the first row's state determines all column flips, and the algorithm then verifies if this configuration is consistent for all other rows.

Uses a bitwise left shift operation (e.g., `1 << k`) to calculate powers of two (2^k). This is a highly efficient, low-level operation that is often faster than using standard exponentiation functions. This technique is common in problems involving binary representations, bit manipulation, or when calculating the size of a state space based on binary combinations.

A technique using multiple pointers to iterate through one or more sorted arrays. In this solution, one pointer iterates through tasks (implicitly via a for-loop from hardest to easiest) while another pointer iterates through workers (from strongest to weakest) to find eligible candidates, reducing the search space at each step.

An algorithmic technique for solving problems by exploring all potential candidates incrementally. When a path is determined to not lead to a solution, the algorithm 'backtracks' by undoing the last choice and trying the next alternative. It's implemented recursively, where each call explores a new state. If a dead end is reached, the function returns, effectively undoing the state change made before the call.

A loop includes a conditional check to terminate early if a certain condition is met, such as the final result being determined or the input being exhausted. This avoids redundant iterations and improves performance. Here, the loop breaks once `remainingIncome` is zero, as no further tax can be calculated.

Using a hash map (or dictionary) to store the frequency of occurrences of items. The item itself, or a unique representation of it, acts as the key, and its count is the value. This provides efficient O(1) average time complexity for lookups and updates, making it ideal for counting problems where the number of unique items is much smaller than the total search space.

An algorithmic approach where a data collection is repeatedly transformed in discrete steps. In each step, a new, smaller collection is generated based on the elements of the previous one. This process continues until a base case is reached, such as the collection being reduced to a single element, which represents the final result. This is common in simulation problems.

A problem-solving technique that systematically enumerates all possible candidates for the solution and checks whether each candidate satisfies the problem's statement. The solution iterates through all pairs of numbers and all valid arithmetic operations, representing a complete exploration of the search space for a small, fixed input size.

Before starting the main algorithm, perform simple checks based on the problem's properties to determine if a solution is impossible. This avoids expensive computations for unsolvable cases. Examples include verifying the total sum is divisible by the number of partitions and ensuring no single element is larger than the target partition size.

A common technique for finding the maximum value that meets a specific criterion within a dataset. A variable is initialized to a sentinel value (e.g., -1, or `Int.min`) that is guaranteed to be smaller than any valid result. As the data is processed, any valid item that is greater than the current tracked maximum replaces it. If the variable remains unchanged, it indicates no valid item was found.

A problem-solving approach that makes the locally optimal choice at each stage with the hope of finding a global optimum. In this solution, the earliest possible valid match between two entities is always taken. This strategy is effective when a local choice does not negatively impact the potential for future optimal choices, which is often true when dealing with sorted data.

A graph traversal algorithm that explores nodes level by level using a queue. It starts at a source node and explores all its immediate neighbors. Then, for each of those neighbors, it explores their unvisited neighbors, and so on. This approach is ideal for finding the shortest path in an unweighted graph or for checking reachability between two nodes, as it guarantees finding the path with the fewest edges first.

After pre-computing frequencies, this pattern calculates the final result by combining these counts based on combinatorial rules. It identifies the valid combinations of properties (e.g., even-even-even, odd-odd-even) and multiplies their respective counts to determine the total number of valid arrangements. This avoids a brute-force enumeration of all triplets.

A strategy where the input data is first processed and organized into a more convenient structure before the main algorithm runs. This often involves separating elements into different groups or lists based on their properties. This initial transformation simplifies the core logic, making the subsequent steps more efficient and easier to implement. In this case, indices are segregated by player type.

A powerful approach for solving problems that can be framed in terms of flows and capacities. It involves constructing a flow network with a source, a sink, and intermediate nodes, where edge capacities represent constraints. The problem is then solved by calculating the maximum flow, which often corresponds to an optimal allocation, connectivity, or matching.

Encapsulating multiple, related return values from a recursive function into a single data structure (like a struct or class). This pattern, exemplified by the `BSTInfo` struct, enhances code clarity by bundling state (e.g., min/max values, size, validity) that needs to be passed up the call stack.

An efficient implementation of a queue using a standard array and an index pointer for the 'head'. Elements are enqueued by appending to the array. Dequeuing is simulated by incrementing the head pointer, which is an O(1) operation, avoiding the O(N) cost of removing the first element from an array. This is a common performance optimization in languages where native queue data structures are less efficient.

The process of breaking a single string into an array of substrings using a specific character or sequence of characters as a delimiter. This is a fundamental first step in parsing structured text data, allowing individual components to be processed separately. For example, splitting a sentence into words using a space, or a CSV line into fields using a comma.

A representation of a graph where each vertex is associated with a collection of its neighboring vertices. Typically implemented using a hash map (dictionary) or an array of lists, it provides efficient O(degree(v)) access to a vertex's neighbors. This structure is ideal for sparse graphs and is a foundational pattern for most graph traversal algorithms like BFS, DFS, and Dijkstra's.

Using a hash map (dictionary) to store the frequency of each unique element in a collection. This is a common preprocessing step to aggregate data, often reducing the problem from operating on N items to D unique items, where D is the number of distinct elements.

A problem-solving strategy for 'count exactly k' problems. Instead of directly counting occurrences that match a condition `== k`, the problem is transformed into finding the difference between two counts: `count(<= k) - count(<= k-1)`. This is particularly useful when the 'at most' version of the problem is much easier to solve, for example, with a sliding window.

Solves a problem by starting from the target state and applying inverse operations to reach the initial state. This is effective when forward operations are ambiguous or have many branches, while reverse operations are more deterministic. It simplifies the problem by reversing the flow of logic, turning a construction problem into a deconstruction one.

A stack that maintains a monotonic (increasing or decreasing) order of elements. When adding a new element, items are popped from the top until the monotonic property is restored. This is efficient for finding the next/previous greater/smaller element or the next relevant state for each item in a sequence, often achieving O(N) time complexity.

The formula `(x % M + M) % M` is used to compute the modulo of a number `x` with respect to `M`. This pattern guarantees a non-negative result, which is crucial in languages where the `%` operator can return negative values for negative inputs. It ensures correctness in algorithms that rely on positive remainders for array indexing or further calculations.

An efficient O(N) technique to determine if one string is a subsequence of another. Two pointers are used: one for the main string and one for the subsequence. The main string's pointer always advances, while the subsequence's pointer only advances when a character match is found. If the subsequence pointer reaches the end of its string, it confirms that a valid subsequence was found in order.

Converts an immutable string into a mutable array of characters to allow for efficient, index-based modifications. This is a common preparatory step in string manipulation problems, as direct character replacement in strings can be inefficient or disallowed. After modification, the array is converted back to a string. This avoids creating many intermediate string objects during manipulation.

A defensive coding practice to ensure numerical correctness by anticipating and preventing overflow errors. This is typically done by casting operands to a larger data type (e.g., from a 32-bit to a 64-bit integer) before performing arithmetic operations like multiplication or addition whose results might exceed the maximum value of the original type.

Utilizes a Set data structure to efficiently store and count unique elements. By inserting items into a Set, duplicates are automatically discarded. This is ideal for problems that require finding the number of distinct items that satisfy a condition, as the final count is simply the size of the Set. The average O(1) time complexity for insertions makes this approach highly performant.

A method for merging solutions from two independent subproblems in knapsack-like scenarios. Given two collections of (weight, value) pairs, a new combined collection is generated by summing the weights and values of every possible pair, one from each collection, while respecting problem constraints.

A function parameter that accepts zero or more arguments of a specified type, denoted by `...`. These arguments are automatically collected into an array within the function body. This pattern is useful for creating flexible APIs where the number of inputs is not known beforehand, such as in formatting functions, aggregators, or mimicking dynamic function calls.

Representing a tree structure, typically a complete binary tree, using a flat array instead of explicit node objects with pointers. Parent-child relationships are determined arithmetically based on array indices (e.g., for a 1-indexed parent at `i`, children are at `2*i` and `2*i+1`). This technique is space-efficient and can improve performance by leveraging cache-friendly contiguous memory layouts. It is the standard representation for binary heaps.

Leverages mathematical formulas for the sum of the first N integers and the sum of their squares to efficiently find discrepancies in a sequence. This method is commonly used to identify missing or duplicated numbers in a given range without requiring extra space for frequency counting. It operates in a single pass, making it highly efficient for large datasets.

A common pattern in grid-based problems that uses a pre-defined array of coordinate offsets to represent possible movements (e.g., `[[-1, 0], [1, 0], [0, -1], [0, 1]]` for up, down, left, right). This simplifies the logic for exploring neighboring cells by allowing iteration over the directions array, which makes the code cleaner, more readable, and less prone to errors compared to hardcoding each directional check.

A linear-time string processing algorithm that computes a Z-array. For a string `S`, the Z-array stores at each index `i` the length of the longest common prefix between `S` and the suffix of `S` starting at `i`. It cleverly uses a sliding window `[L, R]` representing the rightmost prefix-match to reuse previous calculations and achieve O(n) time complexity. It is highly effective for pattern searching and other prefix/suffix related problems.

A technique to ensure correct state transitions in iterative DP. When processing a new element, potential updates to the DP table are first calculated and stored in a temporary data structure based on the table's state from the *previous* step. After all calculations for the current element are complete, the main DP table is updated from this temporary storage. This prevents a state from being used for calculation in the same iteration it was created.

A helper function uses two pointers, one at the start ('left') and one at the end ('right') of a subarray, to reverse its elements. The pointers move towards the center, swapping elements until they meet. This is a classic and efficient O(N) time and O(1) space technique for reversing sequences in-place, widely applicable to array and string manipulations.

A final step after populating a DP table to find the required answer. This often involves a search over the table, such as iterating backwards from the maximum possible state to find the largest achievable value, or scanning the last row/column for an optimal solution. It translates the computed DP states into the final result.

An iterative method for solving DP problems by filling a table. It starts by solving the smallest base-case subproblems and then systematically builds up solutions for larger subproblems. This approach avoids recursion and the associated overhead, often using nested loops to control the order of computation.

A standard method to prevent integer overflow when intermediate or final results of a calculation can become extremely large. By applying a modulo operation with a large prime number (e.g., 10^9 + 7) at each step of an accumulation (like addition), the result is kept within the bounds of standard integer types. This is crucial for many competitive programming problems.

Avoids computationally expensive and potentially imprecise floating-point operations (like square roots) by working with squared values. When comparing distances, checking if d^2 <= r^2 is equivalent to d <= r (for non-negative d, r) but is much faster. This is a standard optimization in graphics, physics engines, and geometric algorithms where only relative distance comparisons are needed.

A fundamental component of any recursive algorithm that defines a simple condition under which the recursion stops, preventing an infinite loop. For tree problems, the base case is often reaching a null or leaf node, which allows the call stack to unwind and the final result to be computed.

Using a special value, often outside the normal range of valid data, to mark an element's state, such as 'processed' or 'invalidated'. In this solution, setting an asteroid to 0 marks it as exploded. This technique avoids the need for separate boolean flags or complex data structures to track state, simplifying the conditional logic that determines whether an element should be added to the final result.

Transforming a 2D coordinate pair `(row, col)` into a single, unique scalar key, typically using the formula `key = row * width + col`. This allows 2D grid locations to be used as keys in data structures like hash maps or sets. This is essential when a single, hashable key is required to represent a multi-dimensional position.

A graph representation using a V x V matrix (where V is the number of vertices). The cell at `matrix[i][j]` stores information about the edge from vertex `i` to vertex `j`, such as its existence (boolean) or weight. This provides O(1) time complexity for checking the existence of a direct edge between two vertices, but requires O(V^2) space, making it suitable for dense graphs or when V is small.

An efficient algorithm for finding a majority element in a sequence. It operates in linear time and constant space. The core idea is to maintain a candidate and a counter, incrementing for matching elements and decrementing for non-matching ones. When the counter reaches zero, a new candidate is chosen. This pattern can be extended to find elements appearing more than n/k times by maintaining k-1 candidates and counters.

Logic that changes based on the state of a node's children (e.g., whether left, right, both, or neither child exists). Using conditional statements to check for the presence of children allows for handling different structural cases, such as leaf nodes versus nodes with one or two children.

This pattern involves finding all occurrences of a specific substring or character within a larger string and replacing them with a different substring. It is a fundamental operation for data cleaning, formatting, and transformation tasks. Many programming languages provide highly optimized built-in functions for this purpose, abstracting away the complexities of iterating through the string and building a new one. This approach is often more efficient and readable than manual character-by-character processing.

A combinatorial method used to count the number of ways to distribute 'k' identical items into 'n' distinct bins. The problem is visualized as arranging 'k' stars and 'n-1' bars in a sequence. The formula for this is given by the binomial coefficient C(k + n - 1, n - 1), providing a powerful and direct solution for a common class of counting problems.

Using a `typealias` to give a more meaningful and domain-specific name to a complex or generic type, such as `[String: Any]`. This enhances code clarity and makes it easier to understand the purpose of the type within the given context. It also simplifies future modifications if the underlying type needs to change across the codebase.

An algorithmic structure that iterates through a list of queries, performing a self-contained computation for each one against a shared, immutable dataset. The results from each independent query are collected into a final result list. This pattern is common when multiple, separate questions must be answered about the same initial data.

A specific logical check used to verify if a single swap between two positions (i and j) in one sequence (s1) can make it identical to another (s2). The condition confirms that the element at s1[i] matches s2[j] and, symmetrically, the element at s1[j] matches s2[i]. This is a core pattern for problems involving a single swap operation.

An efficient algorithm to find the longest path (diameter) in an unweighted tree. It consists of two BFS traversals. The first BFS starts from an arbitrary node to find one endpoint of a diameter. The second BFS starts from that endpoint, and the maximum distance it finds is the tree's diameter.

A specific, self-contained piece of logic—calculating the bit parity of a number—is encapsulated in a private helper function. This improves code readability and modularity by separating the 'what' (getting parity) from the 'how' (counting set bits). The main function becomes cleaner and easier to understand as it operates at a higher level of abstraction.

For problems with a large input range but a small number of significant constraints or events, this pattern focuses computation only on these 'critical points'. By collecting, sorting, and processing only these points, it avoids large memory allocations and reduces time complexity from O(N) to O(K log K) or O(K), where K is the number of critical points.

A technique used to efficiently solve problems involving subarray sums. It works by creating a running total of elements in an array. The sum of any subarray can then be calculated in constant time by taking the difference between two prefix sum values. This solution uses a running prefix sum variable instead of a full array, optimizing space by only tracking the current sum.

An algorithmic approach where each element in an array is considered a 'pivot' or a key element for a potential solution. The algorithm then expands outwards from this pivot to find the largest valid range or subarray that satisfies certain conditions relative to the pivot. This is common in problems like 'Largest Rectangle in Histogram' where each bar is treated as the minimum height of a potential rectangle.

Employs nested loops to systematically visit every point in a discrete 2D grid or matrix. This fundamental traversal pattern is used to process data that can be represented by integer coordinates (x, y). It is a standard approach for problems involving image processing, game boards, or any scenario requiring exhaustive examination of cells within a rectangular region.

For a number 'a' and a modulus 'm', its modular multiplicative inverse is a number 'x' such that `(a * x) % m = 1`. It is the equivalent of division in modular arithmetic. For a prime modulus, it can be efficiently calculated using Fermat's Little Theorem and modular exponentiation.

A counting technique used to find the number of elements in the union of multiple sets. It works by summing the sizes of individual sets, subtracting the sizes of all pairwise intersections, adding back the sizes of all three-way intersections, and so on. This is the primary method for implementing complementary counting when the undesired case is a union of multiple failure conditions.

A method used within a search algorithm where a single 'move' involves repeatedly applying an action until a boundary condition is met. In this problem, the ball rolls in one direction until it hits a wall or the edge of the maze. The final stopping point becomes a new node in the search space. This pattern is useful when state transitions are not single-step but rather continuous until a constraint is violated.

A multi-step pattern for sorting complex objects. First, 'decorate' each item by creating a temporary structure that includes its original form (or index) and a computed sort key. Second, 'sort' this decorated collection based on the key. Finally, 'undecorate' by extracting the original items from the sorted collection. This preserves original data while allowing sorting by a derived value.

Models a problem as a directed acyclic graph (DAG) where nodes are tasks and edges represent dependencies. It finds a valid sequence by iteratively processing nodes with no incoming dependencies using a queue. As a node is processed, its dependencies on other nodes are resolved. This solution implicitly models windows as nodes and un-stamping prerequisites as dependencies, finding a valid reverse operational order.

A tree-based data structure for storing information about intervals or segments. It allows for efficient querying of aggregate values (like sum, min, max) over a range and updating individual elements. Operations like range queries and point updates are typically performed in O(log n) time, making it ideal for problems with frequent range queries and point updates on an array.

Uses the individual bits of an integer to represent a set of boolean flags or the presence/absence of items from a small collection. This is highly efficient for storing, updating (with bitwise OR), and checking for items (with bitwise AND and shifts). It is often used to manage complex state in graph search or dynamic programming.

A straightforward approach to finding the 'K' smallest or largest elements in a collection. The method involves sorting the entire collection based on the desired criteria and then selecting the first 'K' elements from the sorted result. While simple, it may be less efficient than heap-based solutions for very large collections.

The practice of sorting smaller, localized subsets of data as needed, rather than performing a large, global sort. For instance, sorting only the incident edges for each individual node. This is effective when decisions are based on local context and can be more efficient than sorting all elements together.

A performance optimization technique used when building a new collection, such as an array. Before adding elements one by one, memory for the expected number of elements is reserved in a single operation. This avoids multiple, inefficient reallocations and copying of the underlying data structure as it grows, leading to significant speed improvements, especially for large collections.

An approach where a candidate solution is first constructed based on a primary set of rules or heuristics. Afterwards, a separate, comprehensive validation step is performed to ensure the candidate solution satisfies all problem constraints. This separates the logic of construction from the logic of verification.

Uses a hash map (dictionary) to store the frequency of occurrences of elements in a collection. This pattern is highly efficient for problems involving finding duplicates, anagrams, or analyzing the distribution of items. By iterating through the input once, a map of each element to its count is built, allowing for constant-time lookups of an element's frequency.

A structural pattern where the input is split by a delimiter into two distinct parts (e.g., left and right sides of an equation). A single, reusable function is applied to process each part independently. The results are then combined or compared to derive the final answer. This approach promotes code reuse and simplifies problems with symmetric structures.

An optimization for search algorithms where the exploration proceeds in a monotonic fashion (e.g., always moving forward through indices). A pointer tracks the furthest point reached in the search space. Subsequent searches for new candidates begin from this pointer, eliminating the need to re-scan previously considered ranges. This effectively turns a series of overlapping searches into a single linear scan.

A function that processes a tree node and then calls itself for the node's children. This approach naturally mirrors the hierarchical structure of the tree, simplifying logic for tasks like searching, insertion, or serialization. The function's state at each call corresponds to its position in the tree.

A pattern where a problem's solution is defined in terms of solutions to smaller instances of the same problem. In code, this is often implemented using loops or recursion. For dynamic programming, a recurrence relation defines how to compute the value for a state `dp[i]` using the values of previously computed states (e.g., `dp[j]` where `j < i`). This solution uses nested loops to sum up products of subproblem solutions.

A dynamic programming approach where state transitions depend on element values rather than their indices. The DP state, such as `dp[value]`, stores a computed property for subsequences ending with that specific `value`. This pattern is effective when the sequence of operations depends on the numeric relationship between elements, like `current_num` and `current_num - 1`.

Instead of iterating through all possible configurations (e.g., all 2x2 blocks), iterate only through the given 'active' input elements (e.g., black cells). For each active element, calculate its contribution to all the configurations it affects. This is highly efficient when the input data is sparse compared to the total problem space, avoiding a brute-force check of every possibility.

An algorithmic strategy that makes a locally optimal choice at each stage with the hope of finding a global optimum. In this solution, the decision to process the side with the lower boundary wall is a greedy choice. It guarantees that the water level at that position is determined by its local maximum, simplifying the calculation without needing to consider the entire array.

After sorting a collection of points or boundaries, iterate through the sorted elements to calculate the difference or 'gap' between each consecutive pair. This technique is essential for problems that require finding the maximum distance, identifying missing elements in a range, or analyzing intervals defined by the points.

An extension of the standard find-minimum algorithm. It involves maintaining a variable for the minimum value found so far (e.g., `minDifference`) and another variable to store the state or items that produced that minimum (e.g., `resultPair`). When a new minimum is found, both the minimum value and the associated state are updated.

Encapsulates an existing object or function within a new object (the wrapper or adapter). The wrapper provides a modified or different interface to the wrapped object, allowing it to be used in a new context or to add functionality. In this case, a Swift closure is wrapped in a struct to provide a `call`-like interface, adapting the closure's invocation mechanism.

The solution calculates the total cost by summing the minimum costs for each individual element to meet a global condition. For each element that violates a property (e.g., an element in the lower half is greater than a target value), it's adjusted by the minimum amount necessary. This greedy approach works because the adjustments for one element do not affect the required adjustments for others, leading to a globally optimal solution.

A preprocessing step where input data is sorted to optimize a subsequent search algorithm. In backtracking, processing larger elements first can lead to failed states more quickly, thus pruning the search tree more effectively. The code sorts matchsticks in descending order to test the most restrictive items first.

Utilizing the final result array not just for storing answers, but also as a cache or lookup table during computation. As results for subproblems are calculated, they are stored in the array. Later computations can then access these stored results in O(1) time to solve larger problems, avoiding redundant calculations.

A technique in graph traversal where the cost of traversing an edge is not a fixed value but is calculated dynamically based on the current state. For instance, the cost might depend on the arrival time at a node due to factors like traffic signals or time-dependent tolls. The algorithm must compute the actual traversal cost on-the-fly before exploring subsequent nodes.

A design strategy where computational complexity is intentionally shifted between a data structure's operations. Here, the `push` operation is made expensive (O(n)) to ensure that `pop` and `top` operations are extremely cheap (O(1)). This trade-off is made to optimize for an expected usage pattern where reads or removals are more frequent or time-sensitive than insertions.

A graph traversal algorithm that explores as far as possible along each branch before backtracking. It is often implemented recursively or with an explicit stack. A `visited` set or array is used to keep track of visited nodes to avoid infinite loops and redundant processing. It is fundamental for tasks like finding paths, detecting cycles, and exploring connected components.

Calculating the middle index in a binary search or other divide-and-conquer algorithms using `low + (high - low) / 2` instead of `(low + high) / 2`. This standard practice prevents potential integer overflow if the sum of the boundary indices exceeds the maximum value for the integer type. It is a robust and portable way to ensure correctness in search algorithms.

Utilizes a stack to manage operands and intermediate results when evaluating postfix (Reverse Polish Notation) expressions. When an operand is encountered, it is pushed onto the stack. When an operator is found, the required number of operands are popped, the operation is performed, and the result is pushed back onto the stack. This approach naturally handles the order of operations defined by the expression's structure.

A coding pattern where shared data, configurations, or large inputs are stored as class member variables instead of being passed down through every recursive function call. This simplifies function signatures, especially in complex recursive algorithms like DFS, but requires careful state management.

In a dynamic programming solution where the input is sorted, this pattern optimizes the process of finding a compatible previous state. Instead of a linear scan to find the last valid subproblem to build upon (e.g., the last non-overlapping interval), binary search is used. This reduces the time complexity of finding the prerequisite from O(N) to O(log N) for each DP state, significantly improving the overall algorithm's performance from O(N^2) to O(N log N).

A fundamental pattern where a variable is initialized to a starting value (e.g., zero) and is iteratively updated within a loop to aggregate a result. This is used to compute a total sum, count, or other cumulative value over a collection of items. In this code, `totalWater` acts as an accumulator.

Solve a problem with a range constraint `[low, high]` by first generating all possible valid items up to the upper bound `high`. After the generation is complete, filter the collected results to include only those that also meet the lower bound `low`. This simplifies the generation logic by decoupling the two boundary conditions.

A common nested loop structure for problems involving contiguous subarrays. The outer loop iterates through each possible ending index `i` of a subarray. An inner loop then iterates backwards through all possible starting indices `p` (from `i` down to 0), allowing for the systematic evaluation of every contiguous subarray `[p...i]`.

Encapsulating state and behavior within a class to handle a sequence of operations. The class maintains internal data structures (e.g., lists of bookings and overlaps) that persist and are modified across multiple method calls. This pattern is crucial for 'online' problems where input arrives incrementally and the system must maintain a consistent state to process each new piece of data correctly based on the history of previous inputs.

This technique uses the properties of the bitwise XOR operation (A ^ A = 0, A ^ 0 = A) to find a single element that appears an odd number of times in a collection, while all other elements appear an even number of times. By XORing all elements together, pairs of identical elements cancel each other out, leaving only the unique element. This is an efficient approach with O(n) time complexity and O(1) space complexity.

Using a hash map (or dictionary) to store the frequencies of elements or properties within a dynamic range, such as a sliding window. This allows for efficient updates (additions/removals) and queries about the composition of the current range, which is crucial for determining if the window's state is valid.

An optimization technique that stores the results of expensive function calls and returns the cached result when the same inputs occur again. It avoids redundant computations, trading space for time. Here, it's used to cache the results of primality tests (`isPrime`), which are frequently called for the same numbers during the graph traversal.

An efficient algorithm, also known as exponentiation by squaring, to compute large integer powers (base^exp) in O(log exp) time. It works by repeatedly squaring the base and selectively multiplying it into the result based on the binary representation of the exponent. It is a fundamental tool for modular arithmetic, often used to compute (base^exp) % mod.

A common calculation pattern used when selecting items under constraints. The number of items that can be selected from a group is determined by the minimum of the number of available items and the remaining capacity or quota. This is expressed as `min(available_count, remaining_capacity)`. It's fundamental in resource allocation and knapsack-style problems.

Encapsulating a distinct, reusable piece of logic into a separate function. The `getBoxes` function isolates the complex logic of partitioning a single count, making the main algorithm cleaner, more readable, and easier to reason about.

Utilizing a Set (or Hash Set) to store a collection of elements for fast membership testing. Checking if an element exists in a set is, on average, a constant-time (O(1)) operation. This is significantly more efficient than searching for an element in a list or array, which typically takes linear time (O(n)). It is ideal for checking against a fixed collection of items, like vowels or special characters.

A sorting strategy where elements are ordered based on a primary criterion. If a tie occurs, a secondary criterion is used to resolve it. This process continues through multiple levels of criteria until a definitive order is established or a final tie-breaker (like natural alphabetical order) is applied. This is common in leaderboards and ranking systems.

The algorithm operates directly on a mutable copy of the input array, modifying it step-by-step to reach the solution without allocating significant extra memory for intermediate results. Using `inout` parameters (in Swift) or passing by reference allows functions to alter the original data structure, which is a key strategy for optimizing space complexity.

A tree-like data structure used for efficient retrieval of keys in a dataset of strings. Each node represents a character, and paths from the root to a node represent prefixes. It is highly effective for problems involving prefix matching, dictionary lookups, and autocomplete features. Operations like insertion and search have a time complexity proportional to the key length, making it faster than hash maps for certain string operations.

Constructing a new sequence by taking elements from two or more source collections in an alternating fashion. This pattern is useful for merging data while maintaining a specific interleaved structure. The core logic involves iterating and selecting from the appropriate source based on the index (e.g., even/odd) of the target position.

The solution iterates through a conceptual 2D grid (words and their characters) by swapping the conventional order of loops. The outer loop iterates through column indices (character position) and the inner loop iterates through row indices (word position). This technique effectively reads the data column-by-column instead of row-by-row, which is the essence of transposing a matrix or a grid-like data structure.

An efficient, classic algorithm for computing the Greatest Common Divisor (GCD) of two integers. It is based on the principle that the GCD of two numbers does not change if the larger number is replaced by its remainder when divided by the smaller number. This process is repeated until the remainder is zero, with the last non-zero remainder being the GCD.

A method of visiting nodes in a tree using a loop and an explicit pointer or data structure (like a stack), rather than recursion. This approach avoids the risk of stack overflow errors with very deep trees. In this specific case, a single pointer is updated at each step to navigate a path down the tree, which is a memory-efficient form of iterative traversal.

Encapsulating validation logic, such as checking if coordinates are within the grid's bounds, into a separate helper function. This practice improves code modularity and readability. It separates the core traversal algorithm from the boilerplate condition checks, making the main recursive function cleaner and more focused on the problem's logic.

Employing a Doubly Linked List to represent a sequence where frequent insertions or deletions in the middle are required. Unlike arrays, these operations can be performed in O(1) time once the target node is located, as only a few pointers need to be updated, avoiding the O(N) cost of shifting elements.

This iterative pattern uses variables to accumulate a result (like a sum or count) while processing a collection. A conditional check is performed in each iteration to see if a constraint has been met or violated. If so, the loop terminates prematurely using a 'break' statement. This is particularly effective on sorted data, as it avoids redundant checks once a solution is no longer possible.

An algorithmic technique that uses two pointers (left and right) to maintain a dynamic subarray or substring, known as a 'window'. The window slides over the data by expanding from one end and shrinking from the other. This approach efficiently processes contiguous segments of data, avoiding redundant computations for overlapping parts, and is often used for problems involving finding optimal subarrays or substrings.

A method for building a graph from a collection of items. It involves iterating through all unique pairs of items in the collection. For each pair, a custom condition or similarity function is evaluated. If the condition is met, an edge is created between the corresponding nodes in the graph. This is a common way to model relationship-based problems.

A core component of dynamic programming and simulations where the system's state for a future step (e.g., `t+1`) is computed based on its current state (`t`). This is typically implemented inside a loop that advances the state one step at a time. For each element in the current state, a set of rules or transitions is applied to determine its contribution to the elements of the next state.

A technique to efficiently apply updates to all nodes on multiple paths in a tree. By making sparse updates at the path endpoints and their LCA, a single tree traversal (like DFS) can accumulate the final values for all nodes. This avoids iterating over each path individually, significantly improving performance.

A data structure that maintains a collection of elements and allows for efficient retrieval of the minimum element. It is used here to manage a pool of available workers who can complete a task without a pill. By always selecting the weakest worker from this pool (the minimum value), stronger workers are preserved for more demanding future tasks.

For iterative or recursive generation algorithms, start the process by populating the initial data structure (like a queue or stack) with a set of 'seed' or 'base' cases. These are the simplest valid instances of the target items. The algorithm then builds more complex instances from these initial seeds, ensuring the entire solution space is explored.

An optimization technique for problems seeking to minimize a maximum value or maximize a minimum value. It transforms the problem into a series of decision problems (e.g., "is a solution possible with value at most `x`?"). A binary search is then performed on the range of possible answers to find the optimal one that satisfies the decision problem's predicate.

A technique to efficiently answer queries about subarrays. It involves pre-calculating aggregate values from the start of the array to every index (prefix array) and from the end of the array to every index (suffix array). This allows for O(1) calculation of properties of a subarray, such as the array excluding element `i`, by combining `prefix[i-1]` and `suffix[i+1]`. This often reduces overall complexity from O(N^2) to O(N).

An algorithmic strategy for optimization problems that involve combining multiple items into a single result. The core idea is to repeatedly merge the two 'best' or 'cheapest' items available. A priority queue (a min-heap in this case) is used to efficiently retrieve these two items at each step. The result of the merge is then placed back into the priority queue. This process continues until only one item remains, representing the optimal solution.

An optimization where elements are not immediately removed or updated from a data structure where such operations are costly (e.g., a heap). Instead, they are marked as 'stale' or 'invalid' in a separate, fast-access structure like a hash map. The actual removal is deferred until the element is accessed, amortizing the cleanup cost over time.

An algorithmic paradigm that builds up a solution piece by piece, always choosing the next piece that offers the most obvious and immediate benefit. At each step, a locally optimal choice is made in the hope of finding a global optimum. In this solution, the smallest available unique even numbers are chosen sequentially to maximize the count of elements.

A technique that uses a sentinel node (dummy head) placed before the actual head of a linked list. This simplifies list manipulation logic, especially for insertions or deletions at the beginning, by eliminating the need for special conditional checks for the head node. The final list is returned by accessing `dummyHead.next`.

An arithmetic trick to compute `ceil(a / b)` for positive integers `a` and `b` using only integer operations. The formula `(a + b - 1) / b` avoids floating-point arithmetic, which can be faster and prevents potential precision errors. This is a common and efficient pattern in competitive programming and performance-critical integer calculations.

A language feature that adds new functionality to an existing type (like a class, struct, or primitive) without modifying its original source code. This is used to create cohesive and reusable helper methods that are directly related to the type's purpose. It helps in organizing code and improving readability by grouping related logic with the data type it operates on.

A programming technique used to handle heterogeneous collections where elements can have different runtime types. The code inspects an element's type and then conditionally casts it to a more specific type to perform type-specific operations. This is fundamental when working with loosely-typed data structures like JSON objects, mixed-type arrays, or nodes in an abstract syntax tree, enabling polymorphic behavior.

A method to represent a graph using an array of lists. Each index `i` corresponds to a vertex, and the list at that index stores all vertices adjacent to `i`. This is memory-efficient for sparse graphs, like trees, and allows for quick iteration over a node's neighbors.

A common looping pattern for processing ordered collections like arrays. Instead of just accessing each element, the loop provides both the element and its corresponding numerical index. This is essential when the position or order of an element is required for the algorithm's logic, such as when creating mappings from indices to values or performing calculations based on an element's position.

Converts a list of items into a hash set to achieve near-constant time complexity (O(1) on average) for membership checks. This is a common space-time tradeoff, using extra memory for the set to significantly speed up repeated lookups, which would otherwise require linear scans (O(n)) of an array.

A defensive programming practice of checking for and handling trivial or invalid inputs at the beginning of a function. Using a guard clause or an early return statement cleans up the main algorithm's logic by ensuring it only operates on valid, non-trivial data. This improves code readability and robustness.

A variation of the greedy approach where an initial solution is built using locally optimal choices. After the main iterative process, a final correction or adjustment step is performed to handle any remaining value or to ensure the solution perfectly meets all constraints. Here, the leftover sum is added to the last element to maintain the element count and uniqueness.

Uses two hash maps to enforce a strict one-to-one (bijective) relationship between elements of two collections. The first map handles the forward mapping (e.g., key A to value B), while the second handles the reverse mapping (key B to value A). This ensures that each key in one collection maps to a unique key in the other and vice-versa. It is commonly used to check for isomorphic structures, permutations, or any problem requiring a consistent, two-way correspondence.

A fundamental pattern for linked lists where the list is traversed from head to tail using a single pointer to count the total number of nodes. This count is often a prerequisite for subsequent operations that depend on the list's size, such as finding the middle node, splitting the list, or rotating it.

A common preprocessing step in graph problems that involves calculating and storing the degree of each node in an array or map. This provides O(1) access to a node's degree, avoiding repeated computations and simplifying logic that relies on node connectivity.

After constructing a new string or sequence, the code iterates backward from the end to locate the last significant element (e.g., a non-whitespace character). A new, shorter string is then created by slicing the original array up to that point. This is a common post-processing step to clean up results and adhere to specific output formatting rules that forbid trailing placeholders.

Defining custom comparison logic for a class or struct by implementing a 'Comparable' interface. This encapsulates complex, multi-level sorting criteria within the object itself. Data structures like priority queues and sorted collections can then use these objects generically, leading to cleaner, more reusable code.

A technique used in problems with moving entities to determine collision or meeting times. It simplifies calculations by focusing on the relative distance and relative speed between two entities. The time to meet is found by dividing the initial distance between them by their relative speed of approach.

The practice of identifying and handling inputs or conditions that represent special cases or impossible scenarios. This often involves an initial check at the beginning of a function to return early (e.g., checking if the sum is odd), which simplifies the main logic and prevents errors for invalid inputs.

An algorithmic paradigm that makes the locally optimal choice at each stage with the hope of finding a global optimum. This approach is effective for problems with the greedy-choice property. In this solution, the locally optimal choice is to always perform the available cut with the highest cost, as this minimizes its impact by applying it when the number of resulting pieces is smallest.

A straightforward method to examine all unique pairs of elements from a set of size N. It involves using nested loops where the outer loop iterates from `i = 0 to N-1` and the inner loop from `j = i + 1 to N-1`. This O(N^2) approach is fundamental for problems requiring comparison between all distinct pairs and is often a starting point before further optimization.

A method for representing multiple distinct types of entities within a single, contiguous array-based data structure. Each entity type is assigned a unique, non-overlapping range of indices, often by applying an offset to one type's natural identifiers. This allows algorithms designed for simple integer indices (like DSU) to manage relationships between different kinds of objects.

Calculates the 2D cross product of two vectors (formed by three consecutive points) to determine the orientation or turn direction. The sign of the result (positive, negative, or zero) indicates a left turn, right turn, or collinearity, respectively. This is a fundamental technique in computational geometry for analyzing the relationships between points, lines, and polygons.

Utilizing a hash map (or dictionary) to store key-value pairs for efficient data conversion. This pattern provides a clean and performant alternative to lengthy conditional logic (if-else or switch statements) when mapping a fixed set of inputs to corresponding outputs. The lookup operation has an average time complexity of O(1), making it highly efficient for static data translation.

When a problem provides multiple parallel arrays representing different attributes of the same entities (e.g., start times, end times, values), it's a good practice to combine them into a single array of custom objects or structs. This encapsulates the data, making it easier to manage, sort, and pass around, thereby improving code clarity and reducing the risk of synchronization errors between the arrays.

A problem-solving technique where abstract entities and their relationships are represented as vertices and edges in a graph. This transformation allows the application of well-known graph algorithms (like traversal, shortest path, or finding connected components) to solve the original problem. It is particularly useful for problems involving connections, dependencies, or transitive relationships.

An optimization technique used when performing a cumulative calculation over a sequence of numbers (e.g., 1 to N). Instead of iterating one by one, elements are grouped based on a shared property that affects the calculation. In this case, numbers are grouped by their number of digits (e.g., 1-9, 10-99) to perform calculations in chunks, significantly reducing the number of iterations from O(N) to O(log N).

An algorithmic technique that uses two pointers to iterate through a data structure, often an array. By moving the pointers based on certain conditions (often exploiting monotonicity), it can efficiently find pairs or subsegments that satisfy a property. This approach often reduces a nested loop's complexity from O(N^2) to an amortized O(N) by avoiding redundant computations.

This pattern adapts the classic Kadane's algorithm, which finds the maximum sum of a contiguous subarray. The core logic of maintaining a running total and resetting it if it becomes non-beneficial is preserved. It is applied to problems that can be mapped to finding a maximum 'score' in a sequence, where elements contribute positively or negatively. The `dp0` variable, which resets to zero when the running total drops below it, is a direct application of this principle.

A problem-solving approach that simplifies logic by focusing on the even/odd property (parity) of numbers. The solution leverages the rules of parity arithmetic (e.g., odd - even = odd, even - odd = odd) to determine the nature of a subarray sum without needing its exact value. This reduces the problem to tracking transitions between even and odd states.

Converting a string into a character array before processing. This is a common pre-computation step in languages where direct indexed access on strings is inefficient (not O(1)). It trades a one-time setup cost for faster, constant-time access to characters by their index within the main algorithm.

Terminating a loop or recursive search path as soon as it's determined that it cannot lead to a valid or optimal solution. The code stops checking counts for a given 'k' once it's found to be invalid for any single count, avoiding unnecessary work.

A method for creating a complete, independent copy of a graph or a complex linked structure. A recursive function traverses the original structure, while a hash map stores (memoizes) mappings from original nodes to their copies. This prevents re-creating nodes that have already been visited and correctly wires up pointers, especially in structures with cycles or multiple paths to the same node.

A problem-solving strategy for partitioning a sequence into multiple contiguous segments. The approach involves iterating through all possible positions for one split point, and for each position, efficiently determining the number of valid positions for the other split points. This systematically explores the solution space, often combined with other techniques like two-pointers or binary search for efficiency.

Using a fixed-size array to store the frequency of elements, where the array index maps directly to an element's value (e.g., 'a' maps to index 0). This is highly efficient for small, contiguous character sets like 'a'-'z' or ASCII characters, offering O(1) access time and often better performance and memory usage than a hash map for these specific cases.

A loop that continues to execute as long as a specific set of conditions representing a volatile state is true. In this case, the `while` loop runs as long as there are asteroids on the stack moving in the opposite direction of the current one. This pattern is used to process an element against a maintained state until that state becomes stable, allowing for multiple resolutions for a single input element before moving on.

A method of building a complex result, such as a list or a string, incrementally within a loop. An empty or initial data structure is created, and in each iteration, new elements are added or modified based on the current state. This continues until the final result is fully constructed according to the problem's rules.

A method of iterating through a sequence by processing elements in pairs, taking one from the beginning and one from the end (e.g., array[i] and array[n-1-i]). This is commonly used for problems involving palindromic properties, reversals, or any analysis that requires comparing or combining elements symmetrically positioned around the center of the sequence.

An algorithmic technique for solving tree-based problems by breaking them down into subproblems on subtrees. The solution for a node is computed by combining the optimal solutions of its children, which are calculated recursively. This bottom-up approach, often implemented with post-order traversal, is efficient for problems with optimal substructure.

Leveraging the mathematical properties of bitwise operators (XOR, AND, OR) to simplify complex expressions. Identities like associativity, commutativity, and distributivity (e.g., `(a & c) ^ (b & c) = (a ^ b) & c`) can refactor expressions to cancel terms or reduce the number of required operations, leading to highly optimized solutions.

An efficient search algorithm that works on sorted data structures by repeatedly dividing the search interval in half. It compares the target value to the middle element of the array. If they are not equal, the half in which the target cannot lie is eliminated, and the search continues on the remaining half. This process continues until the value is found or the interval is empty.

Using variables to maintain and update the state of the problem as the algorithm progresses. These counters are modified based on the decisions made in each iteration. In this code, `hPieces` and `vPieces` track the number of segments the cake has been divided into, which is essential for calculating the cost of subsequent cuts.

Instead of tracking absolute values, elements are classified relative to a chosen pivot or initial state (e.g., 'same as the first element' vs. 'different'). This simplifies problems where only the relationships between elements matter, especially in interactive or hidden information scenarios. All subsequent logic operates on these relative states.

A recursive strategy where each function call solves a smaller or simpler version of the original problem. The state passed to the next recursive call is reduced in size or complexity. In this solution, a list of 'n' numbers is reduced to a list of 'n-1' numbers in each recursive step, simplifying the problem until a base case is reached.

A technique to determine if objects are equivalent under a set of transformations (e.g., rotation, reflection). It involves defining a process that maps every object in an equivalence class to a single, standard 'canonical' form. By converting objects to their canonical form, equality checks become simple value or string comparisons, which is ideal for deduplication.

Representing a shape or structure using coordinates relative to a common anchor point, often the top-leftmost point. This is achieved by finding the minimum row and column coordinates and subtracting this offset from all points in the shape. This makes the representation independent of its absolute position, enabling direct comparison of shapes.

A variation of binary search used to find the first element (the one with the smallest index) that satisfies a given condition. When a potential answer is found at the midpoint, it is stored, and the search space is narrowed to the lower half (e.g., by setting `right = mid - 1`) to find an even earlier element that also meets the condition. This is also known as finding the lower bound.

A pattern for handling operations on a finite, ordered set where incrementing the last element wraps around to the first (e.g., 'z' becomes 'a'). This is often implemented using a conditional check for the boundary element or by applying modular arithmetic. It is a common requirement in problems involving alphabets, circular arrays, or time calculations.

A dynamic programming algorithm to find the shortest paths between all pairs of vertices in a weighted graph. It iteratively considers each vertex as an intermediate point in paths between any two other vertices. Its O(V^3) complexity makes it practical for small to medium-sized graphs. It can also be adapted to find the transitive closure of a graph, determining all-pairs reachability.

Detects a cycle in a sequence generated by repeatedly applying a transformation (e.g., x -> f(x)). A hash set is used to store all previously seen values. The process terminates if a value is generated that is already in the set, indicating a loop. This is an effective method for problems involving state transitions where memory usage is acceptable, offering a straightforward implementation compared to pointer-based approaches like Floyd's Tortoise and Hare.

To determine the necessary dimensions for processing, the code iterates through a collection of elements (words) to find a maximum value (the length of the longest word). A variable is initialized and then repeatedly updated within a loop whenever a larger value is found. This is a fundamental algorithmic building block for establishing bounds or limits.

A problem-solving strategy that involves breaking down the logic into a set of distinct, manageable scenarios. The overall solution is then constructed by handling each case individually and combining the results, often by taking the maximum or minimum value. This simplifies complex problems by isolating different conditions.

Converting a numerical value into a string that conforms to a fixed-width format by adding padding characters, typically leading zeros. This technique is essential for creating standardized textual representations, such as ensuring days and months in a date are always two digits (e.g., '7' becomes '07'). It guarantees consistent string length and proper alphabetical sorting.

An optimization for dynamic programming problems where the calculation of the current state `dp[i]` only depends on a fixed number of recent states (e.g., `dp[i-1]`). Instead of storing the entire DP table, only the states necessary for the next iteration are kept. This reduces space complexity, for example from O(N*K) to O(K), by reusing memory for the DP table.

A strategy used when filtering or transforming tree-like data structures. After recursively processing a container (like a sub-array or sub-dictionary), a check determines if it has become empty. If so, the container itself is removed from its parent (e.g., by returning null or omitting it). This simplifies the final structure by ensuring it does not contain empty, vestigial containers.

Verifying if a given coordinate (row, column) is within the valid dimensions of a grid before attempting to access an element at that position. This is typically done with a condition like `row >= 0 && row < height && col >= 0 && col < width`. It is a critical safety measure to prevent out-of-bounds errors in any grid-based algorithm.

Implementing a fundamental data structure (e.g., Heap, Trie, Segment Tree) from scratch. This is often necessary when a language's standard library does not provide the required structure or when a customized version is needed for specific functionality or performance characteristics, giving the developer full control over its behavior.

Iterate through a collection and segregate its elements into distinct groups based on a specific property or condition. This is often a preprocessing step to handle different categories of data separately. In this solution, characters are partitioned into 'letters' and 'digits' arrays.

Reduces the search space by defining a simple geometric boundary (e.g., a rectangle) that fully encloses the area of interest. Instead of iterating over an entire or infinite space, the algorithm only considers candidates within this smaller, well-defined bounding box. This technique is common in computational geometry and spatial algorithms to prune irrelevant candidates and improve efficiency.

A coding practice where the DP table is allocated with an extra row and/or column (e.g., size `(m+1) x (n+1)` for inputs of size `m` and `n`). This padding simplifies loop boundaries and index calculations. The extra row/column serves as a natural base case for empty prefixes, allowing array access like `dp[i-1]` without explicit boundary checks inside the main loop, resulting in cleaner code.

Using one or more pointers (indices) to navigate a data structure that represents a stream, such as a compressed array. The pointers are advanced based on consumption logic, often skipping over irrelevant or already-processed segments. This avoids creating an intermediate, expanded data structure and allows for efficient, in-place processing of the raw data format.

A fundamental concept in DP where the value for the current state is determined by selecting the optimal result from several possible transitions. Each transition represents a different decision (e.g., take an element, skip it, match it with another). The final state value is typically the maximum or minimum of the outcomes of these choices, reflecting the core recurrence relation of the optimization problem.

A data structure that tracks a partition of a set into disjoint subsets. It efficiently supports two main operations: `find`, which determines the subset an element belongs to, and `union`, which merges two subsets. It is highly effective for solving problems involving connectivity, equivalence classes, or partitioning.

Constructing a final string by iterating through a collection of components and appending them sequentially. This often involves a loop that adds data elements, delimiters, and padding to build a formatted string. In many languages, using a dedicated StringBuilder class is a more performant implementation of this pattern.

A pattern used within algorithms like sliding window where the validity of a state (e.g., a window) depends on satisfying multiple distinct conditions. A counter is maintained to track how many conditions are currently met. The main logic is triggered only when the counter reaches the total number of required conditions, simplifying the validity check to a single integer comparison.

Employing a hash set to efficiently store a collection of unique items. The set's properties automatically prevent duplicate entries, which is ideal for aggregating candidates from multiple sources (like different nodes marking the same edge for removal) while ensuring each is counted only once.

A final step often required after a search algorithm (like binary search) identifies a boundary index. The search finds the correct 'region' or 'interval' for the answer, but not the exact value. This pattern involves using the state at the identified boundary (e.g., the element before the crossover point) and the original search target to perform a final calculation and derive the precise answer.

Solving a problem by systematically enumerating all possible values for a key parameter. The search space for this parameter is carefully constrained by analyzing the problem's rules, making an exhaustive search computationally feasible. The solution iterates through all valid 'k' values from 1 to the minimum frequency.

The process of converting a complex problem description into a precise mathematical formula or inequality. This transformation simplifies the problem by abstracting away irrelevant details and revealing its core structure. The resulting model, often an equation like `TotalSum(t) = BaseSum + t*Rate - Reduction`, can then be optimized using standard algebraic or algorithmic techniques.

A method to find the k-th lexicographical element in a sequence. It constructs the result piece by piece (e.g., character by character). At each step, it calculates the number of combinations possible for each choice. It then uses the rank 'k' to select the correct choice for the current position and updates 'k' by subtracting the counts of the skipped choices. This process is repeated until the entire element is constructed.

An optimization strategy used in search algorithms to reduce the search space. It involves discarding paths that are guaranteed not to lead to an optimal or desired solution. For example, if the current path's cost to reach a node already exceeds the second-best cost found so far for that node, this path can be pruned, as it cannot produce a better first or second minimum path.

The practice of using a special value, such as a very large integer (infinity), to initialize a DP table or distance array. This value represents an impossible or unreachable state. It simplifies the logic for updates, as any valid calculated value will be smaller, making it a standard way to handle base cases and non-existent paths in minimization problems.

Creating a new output matrix with the same dimensions as an input matrix, often initialized with default values. This pattern is used when transformations on the input matrix should not affect subsequent calculations within the same pass. It ensures that each new cell's value is computed based on the original, unmodified input state, preserving data integrity.

A strategy for modifying a data structure where a new, separate structure (a buffer) is created to hold the results of a transformation. The original structure is read from, and the new one is populated. Once the transformation is complete, the new structure replaces the old one. This avoids the complexities of modifying a collection while iterating over it, often leading to simpler code at the cost of temporary memory.

Using a nil-coalescing operator (e.g., `??` in Swift) to provide a fallback or default value when an expression might evaluate to nil/null. This is particularly useful when performing aggregate operations like `max()` or `min()` on collections that could be empty. It simplifies code by avoiding explicit `if-nil` checks, leading to more concise and robust handling of edge cases.

A mechanism to signal that a pending asynchronous operation should be aborted. A 'token' or 'handle' (like Swift's `DispatchWorkItem`) is associated with the task. An external entity can use this token to request cancellation. The task itself can then be prevented from running. This pattern is crucial for managing the lifecycle of long-running or delayed tasks, preventing unnecessary work and resource leaks.

Instead of storing the actual elements in a data structure like a stack, their indices are stored. This technique is powerful for problems that require calculating lengths, distances, or ranges between elements. The indices allow for direct computation of these metrics (e.g., `end_index - start_index`), which is more informative than just knowing the values.

When performing a multi-step operation that can fail, a temporary copy of the state is used for all modifications. The original state is only updated from the temporary copy if the entire operation completes successfully. If it fails, the temporary state is discarded, ensuring the operation is atomic and the original state remains consistent. This is seen in the `withdraw` method with `tempBanknotes`.

Employing built-in, higher-order functions (like `filter`, `map`, `reduce`) to transform collections based on a given condition or logic. This declarative style abstracts the underlying iteration mechanism, leading to more concise, readable, and less error-prone code compared to writing manual loops with conditional checks to build a new collection.

Iterating through a sequence to identify and consolidate consecutive identical elements into a more compact representation, such as a list of (element, count) pairs. This technique, a form of run-length encoding, simplifies logic by allowing operations on contiguous blocks rather than individual items.

A defensive coding technique used when a loop's body modifies the collection it is iterating over. To prevent infinite loops or skipping elements, the collection's size is captured in a variable before the loop begins. The loop then iterates a fixed number of times based on this captured size. This ensures the loop only processes the elements that were present at the start of the iteration, providing predictable behavior.

The process of converting a number's representation from one base to another, such as from hexadecimal (base-16) to decimal (base-10) and vice-versa. This is a fundamental operation when working with data formats that use non-decimal representations, like color codes, memory addresses, or file permissions.

A technique to compute the cumulative effect of values across a grid. The final value at each cell `(r, c)` is calculated by accumulating values from its neighbors (e.g., top and left). This pattern is often used to reconstruct the final grid from a difference array or to enable constant-time range sum queries after an initial preprocessing pass.

A pattern used in recursion where a result is built incrementally in a collection (the accumulator). Each recursive call processes its own data and then merges the results from its sub-problems into its local accumulator. This is common in traversal algorithms that construct a single, flat collection from a hierarchical data source, such as flattening a tree into a list or aggregating values from a nested structure.

A mathematical technique to distribute a total quantity 'Q' as evenly as possible among 'N' slots. The base amount for each slot is calculated using integer division (Q / N), and the remaining items (Q % N) are distributed one by one to the first few slots. This is used here to distribute spaces between words.

A technique for solving problems involving two sequences by building a 2D grid. Each cell `dp[i][j]` stores the optimal solution for subproblems related to the prefixes of the input sequences up to indices `i` and `j`. The value of a cell is computed from previously computed adjacent cells (e.g., `dp[i-1][j]`, `dp[i][j-1]`), representing the solution's dependency on smaller, overlapping subproblems. This is common in problems like Longest Common Subsequence or Edit Distance.

Employing mathematical set operations such as intersection, union, and difference to partition elements from multiple collections into logical groups. This technique simplifies problem-solving by categorizing elements (e.g., common, unique to A, unique to B), allowing for distinct logic to be applied to each group. It's a powerful way to manage complexity when dealing with relationships between collections.

A straightforward method used within algorithms like Dijkstra's or Prim's to find the next node to process. It involves a linear scan through an array of distances to find the unvisited node with the minimum distance value. While simple to implement, this approach has a time complexity of O(N) for each selection, making it suitable for smaller datasets or when a more complex priority queue is not necessary.

A strategy within a recursive solution where a locally optimal choice is made at each step to guide the search towards a global optimum. For example, instead of exploring `n-1`, the algorithm greedily reduces `n` to the nearest multiple of a divisor (e.g., 2 or 3) to apply a more powerful operation. This heuristic simplifies the state transitions and can significantly prune the search space.

Involves a linear scan from the beginning and/or end of an array to find the boundaries of the longest non-decreasing (or non-increasing) prefix and suffix. This is a common preprocessing step for problems on partially sorted arrays, as it isolates the 'correctly ordered' sections from the 'disordered' middle part that needs to be addressed.

Expands the definition of a 'state' in a search algorithm beyond just coordinates. The state includes additional information, such as items collected or other conditions. This is crucial when path validity depends on factors other than position. A 'visited' set must store this entire augmented state to avoid redundant work.

Employing a temporary or secondary data structure to assist in processing or manipulating a primary data structure. The auxiliary structure is used for intermediate storage, reordering elements, or tracking state during an algorithm. In this case, a second queue is used to temporarily hold and reorder elements to maintain the stack's LIFO property.

An approach where the input data is processed in a single pass. During the iteration, an auxiliary data structure (like a map or set) is built up, storing information about elements encountered so far. This state is then used to make decisions for the current and subsequent elements, often reducing time complexity from polynomial to linear time by eliminating nested loops.

Uses an array's indices to directly place elements into their correct final positions. An auxiliary array provides the target indices for each element of a source array. By iterating through the source, each element is placed directly into its correct spot in a result structure. This avoids complex sorting or searching, leading to an efficient O(n) time complexity, but typically requires O(n) extra space for the result.

A variation of the Sieve of Eratosthenes that precomputes the smallest prime factor (SPF) for every number up to a given limit. After an initial O(N log log N) setup, this precomputed table allows for the prime factorization of any number 'k' in the range in O(log k) time, which is significantly faster than trial division.

A strategy to solve complex problems by breaking them into simpler, overlapping subproblems. A recursive function is used to solve subproblems, and results are stored in a cache (memoization table) to avoid redundant calculations. This approach starts from the main problem and recursively breaks it down.

Extract constraints from the input and store them in a Set for efficient validation. Using a Set provides O(1) average time complexity for checking if an element meets the problem's criteria. This is useful in construction or search problems where solutions must be built from a limited pool of components, such as a specific set of digits.

A helper function, typically returning a boolean, used within 'Binary Search on the Answer'. It determines if a given candidate value `x` meets a specific problem constraint. The function must have a monotonic property (e.g., if `check(x)` is true, `check(y)` is also true for all `y > x`), which is essential for the binary search to correctly discard half of the search space.

Processing a sequence from right to left. This approach is useful when the solution for an element `i` depends on the solutions for elements `j > i`. By iterating backward, the results for subsequent elements are already available when processing the current element, which is a common pattern in dynamic programming.

A standard practice where a function returns a specific, pre-defined value (like `null`, `-1`, or `[-1, -1]`) to indicate that no solution could be found after exhausting the search space. This provides a clear signal to the calling code that the search was unsuccessful, allowing it to handle the failure case gracefully.

Maintaining a variable that tracks the optimal value (maximum or minimum) found so far during an iteration. The variable is initialized to a baseline (e.g., 0, -infinity) and is updated inside a loop whenever a new, better value is computed. This is a standard pattern for optimization problems.

A data structure, such as a hash set or a boolean array/matrix, used to keep track of nodes that have already been visited during a graph traversal. This is crucial for preventing infinite loops in graphs containing cycles and for avoiding redundant computations on already processed nodes. By checking if a node has been visited before adding it to the exploration queue or stack, the algorithm ensures efficiency and correctness.

A parsing strategy that consumes input by making a locally optimal choice at each step. It involves looking ahead at subsequent characters to identify and parse a complete token (like a multi-digit number) before moving on. This is common in lexical analysis and string manipulation problems.

An optimization strategy where data is converted into a more access-friendly format before the main algorithm runs. For instance, converting a string to a character array to enable O(1) indexed access, or pre-calculating prefix sums. This trades initial setup time and potentially space for faster execution during the core processing loops.

This pattern separates the core computation from the final result formatting. An algorithm first iterates through data to compute and store an intermediate state (e.g., a maximum value, a count, a boolean flag). After the computation is complete, a final result is constructed based on this stored state. This improves code clarity by decoupling the logic for finding a solution from the logic for presenting it.

A preparatory step where the input grid is scanned once to extract key information, such as the starting positions of entities, target locations, or obstacle layouts. This avoids repeated searches for this static information during the main algorithm.

A control flow technique where a function or loop terminates as soon as a condition is met that makes further processing unnecessary. By returning early from a function (e.g., `return false` on a failed check), the algorithm avoids redundant computations. This is often implemented using guard clauses and improves both performance and code clarity by reducing nested logic.

A pointer-based technique, often used for linked lists, that involves maintaining references to three related nodes: `previous`, `current`, and `next`. This allows for complex manipulations, such as reversing links or reordering nodes, by safely modifying the `current` node's pointers without losing the reference to the rest of the structure. The `next` pointer is often stored in a temporary variable before modification.

An array used to efficiently apply updates to a range of elements. Instead of modifying each element in the range, only the start and end points are updated in the difference array. The final values can then be computed in a single pass using a prefix sum, converting multiple range updates into O(1) operations followed by a final O(N) reconstruction.

A DFS technique where state is maintained specifically for the current path from the root to the current node. When the traversal enters a node, the state is updated. When the traversal backtracks (returns from the recursive call), the state is reverted to its previous value. This is essential for problems involving ancestor-descendant relationships or path-specific properties.

A technique that involves iterating through a data collection, such as an array or list, exactly once to compute a result. This is often the most time-efficient approach (O(n)) for problems that don't require multiple passes or complex data relationships. The solution iterates through the prices array a single time to calculate the total profit.

A system of arithmetic where operations are performed within a fixed range defined by a modulus. Results 'wrap around' upon reaching the modulus. This is essential for problems involving large numbers to prevent integer overflow, especially in combinatorics and number theory. Key operations like addition and multiplication are performed followed by a modulo operation to keep the result in range.

Utilizing a boolean array or set to track reachable states, where `dp[i]` indicates if state `i` (e.g., a sum) is achievable. Transitions update states from false to true based on problem rules. This pattern is fundamental to solving decision problems like Subset Sum, Partition Problem, and other combinatorial optimization tasks.

A mathematical property where for a set of numbers on a line, the point that minimizes the sum of absolute distances to all other numbers is the median of the set. This principle is fundamental for solving problems that involve finding an optimal meeting point or minimizing total movement cost in one dimension.

An extension of Breadth-First Search (BFS) for trees. Before processing each level, the current size of the queue is recorded. A loop then iterates that many times to process all nodes belonging to the current level. This pattern is essential for problems that require aggregating or processing data on a per-level basis, such as finding the maximum value, average, or sum for each level in a binary tree.

A standard formula to determine if two half-open intervals [s1, e1) and [s2, e2) have a non-empty intersection. The condition `max(s1, s2) < min(e1, e2)` evaluates to true if and only if they overlap. This is a foundational technique for problems involving scheduling, geometric collisions, or range queries. It's efficient and avoids complex case-by-case analysis of how intervals might relate to each other.

Utilizes semaphores to enforce a strict order of execution among concurrent threads. A semaphore is initialized with a count of zero, causing any thread that calls `wait()` to block immediately. A preceding thread, upon completing its task, calls `signal()` to increment the count and unblock the next thread in the sequence. This technique can be chained to create a multi-step, ordered workflow across different threads.

Constructing a unique string identifier for each value in a nested data structure by concatenating keys or indices from the root to the value's location. This technique is fundamental for data flattening, allowing any value in the hierarchy to be uniquely addressed in a flat namespace.

A structural pattern for problems involving two datasets. It involves iterating through each element of one dataset and, for each element, performing an efficient search (e.g., binary search, hash map lookup) on the second dataset to find matching or qualifying pairs. This avoids a naive nested loop (O(N*M)) approach, often leading to a more optimal solution like O(N log M).

A problem-solving strategy for 2D grids where the logic is simplified by processing the grid as a collection of independent 1D arrays (either rows or columns). In this solution, the gravity simulation treats each column as a separate 1D array, making the logic much simpler than handling the entire grid at once.

Decomposing a complex problem into smaller, manageable sub-problems, each handled by a dedicated helper function. The main function orchestrates calls to these helpers and combines their results. This improves code modularity, readability, and reusability, as the helper function can be tested independently and potentially reused for other tasks.

An optimization where a mapping or lookup structure is populated lazily, only as needed. Instead of pre-computing and storing all possible key-value pairs, entries are created on-the-fly during operations. This conserves memory and reduces initial setup time, especially when the number of actual operations is significantly smaller than the total potential state space. The solution uses this by only adding entries to the map for swapped indices.

An approach where the algorithm builds a new data structure to store the result instead of modifying the input data structures in-place. This solution creates a new `TreeNode` at each step. This pattern avoids side effects, preserves the original inputs, and can lead to code that is easier to reason about, aligning with functional programming principles.