Recognize the pattern.
Skip the memorization.

Summary: Expand the right pointer to grow the window; shrink from the left when a constraint is violated. Total work is still O(n) because each pointer moves forward at most n times.

Identification Signals - "Longest/shortest substring/subarray with condition X" (no repeats, at most K distinct, sum ≤ target) - Condition is monotonic — once violated, shrinking only helps

Core Strategy 1. Expand right, update window state (hashmap/count/sum). 2. While the window violates the constraint, shrink left and update state. 3. Update the answer (usually right - left + 1) once the window is valid.

C# Pseudo-code Template

// PSEUDO-CODE: Dynamic Window with Constraint
public int LengthOfLongestSubstringKDistinct(string s, int k)
{
    var freq = new Dictionary<char, int>();
    int left = 0, best = 0;

    for (int right = 0; right < s.Length; right++)
    {
        char c = s[right];
        freq[c] = freq.GetValueOrDefault(c, 0) + 1;      // expand

        while (freq.Count > k)                            // shrink while invalid
        {
            char leftChar = s[left];
            freq[leftChar]--;
            if (freq[leftChar] == 0) freq.Remove(leftChar);
            left++;
        }
        best = Math.Max(best, right - left + 1);          // record valid window
    }
    return best;
}

Benchmarks (Medium/Hard-weighted) - Warmup (optional): 1876. Substrings of Size Three with Distinct Characters - Medium: 3. Longest Substring Without Repeating Characters, 209. Minimum Size Subarray Sum, 424. Longest Repeating Character Replacement, 1004. Max Consecutive Ones III - Hard: 76. Minimum Window Substring, 992. Subarrays with K Different Integers

Pitfalls - Forgetting to fully clean up map entries (leaving zero-count keys skews freq.Count). - Using while vs if for shrinking — must be while since one expansion can require multiple shrinks. - Confusing "at most K" with "exactly K" (exactly K = atMost(K) - atMost(K-1) trick — this itself is a common senior-level follow-up).

Summary: When the answer itself is monotonic (if X works, everything "easier" than X also works), binary search over the range of possible answers, not the array indices. This is the variant senior interviewers use to test whether you can recognize a problem as binary-searchable rather than just execute a memorized template.

Identification Signals - "Minimize the maximum," "maximize the minimum" - "Find the smallest value such that a feasibility check passes" - Problem mentions capacity, speed, days, or distance thresholds

Core Strategy 1. Define low and high as the plausible answer range. 2. Write a Feasible(mid) predicate (usually greedy or simulation, O(n)). 3. Binary search: if feasible, try smaller (high = mid); else low = mid + 1.

C# Pseudo-code Template

// PSEUDO-CODE: Binary Search on Answer Space
public int MinEatingSpeed(int[] piles, int h)
{
    int low = 1, high = piles.Max();
    while (low < high)
    {
        int mid = low + (high - low) / 2;
        if (CanFinish(piles, h, mid)) high = mid;   // feasible -> try smaller
        else low = mid + 1;                          // infeasible -> need bigger
    }
    return low;
}

private bool CanFinish(int[] piles, int h, int speed)
{
    long hours = 0;
    foreach (var p in piles) hours += (p + speed - 1) / speed;  // ceil division
    return hours <= h;
}

Benchmarks (Medium/Hard-weighted) - Warmup (optional): 1283. Find the Smallest Divisor Given a Threshold - Medium: 875. Koko Eating Bananas, 1011. Capacity To Ship Packages Within D Days, 1552. Magnetic Force Between Two Balls - Hard: 410. Split Array Largest Sum, 1231. Divide Chocolate

Pitfalls - Failing to prove monotonicity before applying this pattern — articulate this proof out loud in interviews, it's a strong signal. - Integer overflow in the feasibility check (use long for accumulations).

Summary: Maintain a stack where elements are kept in strictly increasing or decreasing order, popping elements that violate the order to answer "next greater/smaller element" queries in O(n) total.

Identification Signals - "Next greater/smaller element," "daily temperatures" - "Largest rectangle," "trapping rain water" (stack variant)

Core Strategy 1. Iterate through the array, maintaining a stack of indices. 2. While the current element violates the stack's order, pop and resolve the answer for the popped index. 3. Push the current index.

C# Pseudo-code Template

// PSEUDO-CODE: Monotonic Decreasing Stack
public int[] DailyTemperatures(int[] temperatures)
{
    int n = temperatures.Length;
    int[] result = new int[n];
    var stack = new Stack<int>(); // stores indices, decreasing temps

    for (int i = 0; i < n; i++)
    {
        while (stack.Count > 0 && temperatures[i] > temperatures[stack.Peek()])
        {
            int idx = stack.Pop();
            result[idx] = i - idx;   // resolve distance for popped index
        }
        stack.Push(i);
    }
    return result;
}

Benchmarks (Medium/Hard-weighted) - Warmup (optional): 496. Next Greater Element I - Medium: 739. Daily Temperatures, 503. Next Greater Element II, 907. Sum of Subarray Minimums, 1130. Minimum Cost Tree From Leaf Values - Hard: 84. Largest Rectangle in Histogram, 85. Maximal Rectangle

Pitfalls - Pushing values instead of indices — indices let you compute distances and check window bounds. - Choosing the wrong strict/non-strict inequality — affects handling of duplicate values (a common follow-up question).

Summary: Extend BFS/DFS to general graphs (adjacency lists) with explicit visited tracking; topological sort orders nodes in a DAG such that every edge goes from earlier to later in the order.

Identification Signals - "Course schedule," "build order," "dependencies" - "Detect cycle in directed graph" - Explicit graph given as edge list or adjacency list

Core Strategy (Kahn's Algorithm — BFS-based Topo Sort) 1. Compute in-degree for every node. 2. Push all zero in-degree nodes into a queue. 3. Pop a node, add to result, decrement in-degree of neighbors; enqueue any that hit zero. 4. If result size < total nodes, a cycle exists.

C# Pseudo-code Template

// PSEUDO-CODE: Kahn's Algorithm (BFS Topological Sort)
public int[] FindOrder(int numCourses, int[][] prerequisites)
{
    var graph = new List<int>[numCourses];
    var inDegree = new int[numCourses];
    for (int i = 0; i < numCourses; i++) graph[i] = new List<int>();

    foreach (var p in prerequisites)
    {
        graph[p[1]].Add(p[0]);
        inDegree[p[0]]++;
    }

    var queue = new Queue<int>();
    for (int i = 0; i < numCourses; i++)
        if (inDegree[i] == 0) queue.Enqueue(i);

    var order = new List<int>();
    while (queue.Count > 0)
    {
        int node = queue.Dequeue();
        order.Add(node);
        foreach (var next in graph[node])
        {
            inDegree[next]--;
            if (inDegree[next] == 0) queue.Enqueue(next);
        }
    }

    return order.Count == numCourses ? order.ToArray() : Array.Empty<int>();  // cycle check
}

Benchmarks (Medium/Hard-weighted) - Warmup (optional): 997. Find the Town Judge - Medium: 207. Course Schedule, 210. Course Schedule II, 133. Clone Graph, 785. Is Graph Bipartite? - Hard: 269. Alien Dictionary (premium), 1462. Course Schedule IV

Pitfalls - Forgetting the cycle check (order.Count == numCourses) — without it, a cyclic graph silently returns an incomplete order. - Using a visited set alone for DFS-based topo sort without distinguishing "currently in recursion stack" vs "fully processed" (needed to detect cycles correctly) — a frequent senior-level gotcha.

Summary: Use a min-heap of size K (for "top K largest") or max-heap of size K (for "top K smallest") to avoid sorting the entire dataset — O(n log k) instead of O(n log n).

Identification Signals - "K-th largest/smallest," "top K frequent elements" - "K closest points to origin"

Core Strategy 1. Maintain a heap of size K. 2. For each new element, push it; if heap size exceeds K, pop the "worst" element. 3. At the end, the heap contains exactly the top K elements.

C# Pseudo-code Template

// PSEUDO-CODE: Min-Heap for Top-K Largest
public int FindKthLargest(int[] nums, int k)
{
    var minHeap = new PriorityQueue<int, int>();
    foreach (var num in nums)
    {
        minHeap.Enqueue(num, num);
        if (minHeap.Count > k) minHeap.Dequeue();   // evict smallest, keep top k
    }
    return minHeap.Peek();
}

Benchmarks (Medium/Hard-weighted) - Warmup (optional): 1046. Last Stone Weight - Medium: 215. Kth Largest Element in an Array, 347. Top K Frequent Elements, 973. K Closest Points to Origin, 692. Top K Frequent Words - Hard: 23. Merge k Sorted Lists, 502. IPO

Pitfalls - C#'s PriorityQueue<TElement, TPriority> is a min-heap by default — for max-heap behavior, negate priorities or use a custom comparer (call this out proactively, interviewers like seeing awareness of language-specific gotchas). - Forgetting to pop when heap size exceeds K (defeats the O(log k) benefit).

Summary: Choose a subset of items (each used at most once) to maximize/minimize a value subject to a capacity constraint — classic "include or exclude" decision at each step.

Identification Signals - "Each item used at most once" - "Subset sum," "partition equal subset sum," "target sum" - Capacity/weight constraint explicitly given

Core Strategy 1. dp[i][w] = best value using first i items with capacity w. 2. Transition: dp[i][w] = max(dp[i-1][w], dp[i-1][w - weight[i]] + value[i]) if weight[i] <= w. 3. Optimize to 1D array, iterating w in reverse to avoid reusing an item twice.

C# Pseudo-code Template

// PSEUDO-CODE: 0/1 Knapsack (1D optimized)
public bool CanPartition(int[] nums)
{
    int sum = nums.Sum();
    if (sum % 2 != 0) return false;
    int target = sum / 2;

    bool[] dp = new bool[target + 1];
    dp[0] = true;

    foreach (var num in nums)
        for (int w = target; w >= num; w--)   // REVERSE iteration: no item reuse
            dp[w] = dp[w] || dp[w - num];

    return dp[target];
}

Benchmarks (Medium/Hard-weighted) - Warmup (optional): 70. Climbing Stairs (intro to DP thinking) - Medium: 416. Partition Equal Subset Sum, 494. Target Sum, 1049. Last Stone Weight II - Hard: 879. Profitable Schemes, 474. Ones and Zeroes (2D knapsack variant)

Pitfalls - Iterating the weight loop forward instead of backward for the 1D optimization — this accidentally allows item reuse (turns it into unbounded knapsack). This is the #1 senior-level DP bug to watch for. - Off-by-one on the capacity array size (target + 1, not target).

Summary: Same as 0/1 knapsack, but each item can be used unlimited times — coin change and rod cutting are canonical examples.

Identification Signals - "Unlimited supply," "as many times as needed" - "Coin change," "minimum number of coins/squares"

Core Strategy 1. dp[w] = best way to make amount w. 2. Iterate weight forward (not backward) since reuse is allowed.

C# Pseudo-code Template

// PSEUDO-CODE: Unbounded Knapsack
public int CoinChange(int[] coins, int amount)
{
    int[] dp = new int[amount + 1];
    Array.Fill(dp, amount + 1);   // sentinel for "unreachable"
    dp[0] = 0;

    foreach (var coin in coins)
        for (int w = coin; w <= amount; w++)   // FORWARD iteration: reuse allowed
            dp[w] = Math.Min(dp[w], dp[w - coin] + 1);

    return dp[amount] > amount ? -1 : dp[amount];
}

Benchmarks (Medium/Hard-weighted) - Warmup (optional): 70. Climbing Stairs - Medium: 322. Coin Change, 518. Coin Change II, 279. Perfect Squares - Hard: 983. Minimum Cost For Tickets

Pitfalls - Confusing this with 0/1 knapsack's reverse iteration — be ready to explain why the direction differs, interviewers frequently ask this directly. - Not initializing dp to a sentinel value representing "unreachable."

Summary: Compare two sequences to find the longest subsequence (not necessarily contiguous) common to both, via a 2D grid of matches/mismatches.

Identification Signals - "Two strings," "edit distance," "longest common subsequence" - "Interleaving strings," "distinct subsequences"

Core Strategy 1. dp[i][j] = LCS length of text1[0..i) and text2[0..j). 2. If characters match: dp[i][j] = dp[i-1][j-1] + 1. 3. Else: dp[i][j] = max(dp[i-1][j], dp[i][j-1]).

C# Pseudo-code Template

// PSEUDO-CODE: LCS 2D Table
public int LongestCommonSubsequence(string text1, string text2)
{
    int m = text1.Length, n = text2.Length;
    int[,] dp = new int[m + 1, n + 1];

    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            dp[i, j] = text1[i - 1] == text2[j - 1]
                ? dp[i - 1, j - 1] + 1
                : Math.Max(dp[i - 1, j], dp[i, j - 1]);

    return dp[m, n];
}

Benchmarks (Medium/Hard-weighted) - Medium: 1143. Longest Common Subsequence, 583. Delete Operation for Two Strings, 97. Interleaving String - Hard: 72. Edit Distance, 115. Distinct Subsequences, 10. Regular Expression Matching

Pitfalls - Off-by-one: dp table is (m+1) x (n+1), and string indices are i-1, j-1 when comparing. - Forgetting the base case row/column (dp[0][*] = 0, dp[*][0] = 0) represents "empty string" comparisons.

Summary: Explore all candidate solutions by building them incrementally, abandoning ("backtracking" from) a path as soon as it's determined invalid — a DFS over the decision tree.

Identification Signals - "Generate all subsets/permutations/combinations" - "N-Queens," "Sudoku solver," "word search" - "Return all valid arrangements satisfying constraints"

Core Strategy 1. Define a recursive function that takes the current partial solution. 2. At each step, iterate over choices; make a choice, recurse, then undo the choice (backtrack). 3. Add pruning conditions early to cut off invalid branches (constraint checks before recursing).

C# Pseudo-code Template

// PSEUDO-CODE: Subsets Backtracking
public IList<IList<int>> Subsets(int[] nums)
{
    var result = new List<IList<int>>();
    var current = new List<int>();

    void Backtrack(int start)
    {
        result.Add(new List<int>(current));    // copy, don't reference
        for (int i = start; i < nums.Length; i++)
        {
            current.Add(nums[i]);              // choose
            Backtrack(i + 1);
            current.RemoveAt(current.Count - 1); // un-choose (backtrack)
        }
    }

    Backtrack(0);
    return result;
}

// PSEUDO-CODE: Permutations Backtracking
public IList<IList<int>> Permute(int[] nums)
{
    var result = new List<IList<int>>();
    var used = new bool[nums.Length];
    var current = new List<int>();

    void Backtrack()
    {
        if (current.Count == nums.Length)
        {
            result.Add(new List<int>(current));
            return;
        }
        for (int i = 0; i < nums.Length; i++)
        {
            if (used[i]) continue;
            used[i] = true;
            current.Add(nums[i]);
            Backtrack();
            current.RemoveAt(current.Count - 1);  // backtrack
            used[i] = false;
        }
    }

    Backtrack();
    return result;
}

Benchmarks (Medium/Hard-weighted) - Warmup (optional): 78. Subsets - Medium: 46. Permutations, 39. Combination Sum, 79. Word Search, 22. Generate Parentheses, 40. Combination Sum II - Hard: 51. N-Queens, 37. Sudoku Solver, 212. Word Search II

Pitfalls - Forgetting to undo the choice after recursing (mutating a shared list without removing the last addition corrupts subsequent branches). - Not skipping duplicates properly in inputs with repeated values (sort first, then skip nums[i] == nums[i-1] at the same recursion depth) — a very common interview trip-up. - Copying the list (new List<int>(current)) when adding to results — otherwise all results reference the same mutated list.

Summary: A data structure that tracks a partition of elements into disjoint sets, supporting near-O(1) Find (which set does X belong to) and Union (merge two sets) via path compression and union by rank/size.

Identification Signals - "Number of connected components," "redundant connection" - "Accounts merge," "friend circles," "check if graph has a cycle (undirected)" - Dynamic connectivity queries (edges added over time)

Core Strategy 1. parent[i] initially points to itself; rank[i] (or size[i]) tracks tree depth/size for balancing. 2. Find(x): follow parent pointers to the root, compressing the path along the way. 3. Union(x, y): find both roots; if different, attach the smaller-rank tree under the larger one.

C# Pseudo-code Template

// PSEUDO-CODE: Union-Find with Path Compression + Union by Rank
public class UnionFind
{
    private int[] parent;
    private int[] rank;

    public UnionFind(int n)
    {
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
    }

    public int Find(int x)
    {
        if (parent[x] != x)
            parent[x] = Find(parent[x]);  // path compression
        return parent[x];
    }

    public bool Union(int x, int y)
    {
        int rootX = Find(x), rootY = Find(y);
        if (rootX == rootY) return false;  // already connected -> would form a cycle

        if (rank[rootX] < rank[rootY]) (rootX, rootY) = (rootY, rootX);
        parent[rootY] = rootX;             // union by rank
        if (rank[rootX] == rank[rootY]) rank[rootX]++;
        return true;
    }
}

Benchmarks (Medium/Hard-weighted) - Warmup (optional): 1971. Find if Path Exists in Graph - Medium: 547. Number of Provinces, 684. Redundant Connection, 721. Accounts Merge, 200. Number of Islands (DSU variant) - Hard: 685. Redundant Connection II, 1319. Number of Operations to Make Network Connected, 928. Minimize Malware Spread

Pitfalls - Skipping path compression or union by rank — degrades to O(n) per operation on adversarial inputs (linear chains). Being able to articulate the amortized complexity (inverse Ackermann) is a strong senior signal. - Off-by-one when mapping problem-specific IDs (e.g., 1-indexed accounts) to 0-indexed array positions.