Interview Coding Patterns — Reference Glossary

Why this matters in interviews

Senior engineers are expected to recognize the underlying algorithmic pattern within the first minute of reading a problem — not rediscover it from scratch. This glossary gives you a canonical name, definition, and trigger condition for every major pattern so you can quickly map any LeetCode-style problem to the right approach, then reason about its complexity trade-offs with precision.

Concept

Array & String Patterns

Linked List Patterns

Stack & Queue Patterns

Tree Patterns

Graph Patterns

Binary Search Patterns

Dynamic Programming Patterns

Backtracking

---

Complexity Reference

---

Key rules / gotchas

• Sliding window shrink condition: Always shrink from the left when the window violates the constraint — never skip this or the window grows unboundedly and gives wrong answers.
• Two pointers vs sliding window: Two pointers work best when you're comparing elements at two positions simultaneously (pair sum, palindrome). Sliding window is for a contiguous subarray/substring property (max, min, count).
• Prefix sum HashMap trick: sum[0..j] - sum[0..i-1] == k → store prefix sums in a map and look up currentSum - k in O(1). Handles negative numbers unlike sliding window.
• Monotonic stack: what to store: Usually store indices, not values — you need indices to compute widths (histogram) or positions.
• Floyd's cycle start: After fast and slow meet inside the cycle, reset one pointer to head and advance both one step at a time — they meet at the cycle entry.
• Binary search mid overflow: Use mid = lo + (hi - lo) / 2 or (lo + hi) >>> 1; never (lo + hi) / 2 when both are large positives.
• Union-Find path compression: parent[x] = find(parent[x]) flattens the tree on every find call — without this, DSU degrades to O(log n) or worse.
• DP state before recurrence: Define dp[i] in plain English before writing the transition. Wrong state definition is the #1 source of incorrect DP solutions.
• 0/1 knapsack 1D space: Iterate capacity w from maxW down to wt[i] when collapsing to 1D — going forward would allow using the same item twice (unbounded).
• Backtracking with duplicates: Sort the input first, then skip candidates[i] == candidates[i-1] at the same recursion depth to avoid duplicate result sets (subsets II, combination sum II).
• Topological sort cycle detection: With Kahn's algorithm, if the number of nodes in the topological order is less than the total number of nodes, a cycle exists.

Code example

import java.util.*;

public class JavaLabRunner {

    // ── 1. SLIDING WINDOW ──────────────────────────────────────────────────
    // Longest substring without repeating characters — O(n) time, O(charset) space
    static int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> lastSeen = new HashMap<>();
        int best = 0;
        int left = 0;

        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            // If c was seen inside the current window, shrink from the left
            if (lastSeen.containsKey(c) && lastSeen.get(c) >= left) {
                left = lastSeen.get(c) + 1;
            }
            lastSeen.put(c, right);
            best = Math.max(best, right - left + 1);
        }
        return best;
    }

    // ── 2. MONOTONIC STACK ─────────────────────────────────────────────────
    // Next greater element — O(n) time, O(n) space
    // For each element, find the first element to its right that is greater.
    // Returns -1 if none exists.
    static int[] nextGreaterElement(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];
        Arrays.fill(result, -1);

        // Stack stores indices of elements waiting for their "next greater"
        Deque<Integer> stack = new ArrayDeque<>(); // monotonic decreasing (values)

        for (int i = 0; i < n; i++) {
            // Pop all indices whose value is smaller than nums[i] — nums[i] is their answer
            while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
                result[stack.pop()] = nums[i];
            }
            stack.push(i);
        }
        return result;
    }

    // ── 3. BINARY SEARCH ON ANSWER ─────────────────────────────────────────
    // Minimum number of days to make m bouquets.
    // You need m bouquets; each bouquet needs k adjacent bloomed flowers.
    // flowers[i] = day on which flower i blooms. Find minimum day, or -1 if impossible.
    // O(n log(maxDay)) time, O(1) space
    static int minDays(int[] bloomDay, int m, int k) {
        int n = bloomDay.length;
        if ((long) m * k > n) return -1; // impossible even if all flowers bloom

        int lo = 1, hi = 0;
        for (int d : bloomDay) hi = Math.max(hi, d);

        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (canMakeBouquets(bloomDay, m, k, mid)) {
                hi = mid;          // mid works — try fewer days
            } else {
                lo = mid + 1;      // mid doesn't work — need more days
            }
        }
        return lo;
    }

    // Feasibility predicate: can we make m bouquets by day `day`?
    private static boolean canMakeBouquets(int[] bloomDay, int m, int k, int day) {
        int bouquets = 0, consecutive = 0;
        for (int d : bloomDay) {
            if (d <= day) {
                consecutive++;
                if (consecutive == k) {
                    bouquets++;
                    consecutive = 0;
                }
            } else {
                consecutive = 0; // gap — reset streak
            }
        }
        return bouquets >= m;
    }

    // ── MAIN ───────────────────────────────────────────────────────────────
    public static void main(String[] args) {

        // 1. Sliding window
        String input = "abcabcbb";
        System.out.println("=== Sliding Window ===");
        System.out.println("Input: \"" + input + "\"");
        System.out.println("Longest substring without repeating chars: "
                + lengthOfLongestSubstring(input)); // expected: 3 ("abc")

        // 2. Monotonic stack
        int[] nums = {2, 1, 5, 3, 6, 4};
        int[] nge  = nextGreaterElement(nums);
        System.out.println("\n=== Monotonic Stack ===");
        System.out.println("Input:           " + Arrays.toString(nums));
        System.out.println("Next greater:    " + Arrays.toString(nge));
        // expected:        [5, 5, 6, 6, -1, -1]

        // 3. Binary search on answer
        int[] bloomDay = {1, 10, 3, 10, 2};
        int m = 3, k = 1;
        System.out.println("\n=== Binary Search on Answer ===");
        System.out.println("bloomDay: " + Arrays.toString(bloomDay)
                + "  m=" + m + "  k=" + k);
        System.out.println("Minimum days: " + minDays(bloomDay, m, k)); // expected: 3

        int[] bloomDay2 = {1, 10, 3, 10, 2};
        m = 3; k = 2;
        System.out.println("bloomDay: " + Arrays.toString(bloomDay2)
                + "  m=" + m + "  k=" + k);
        System.out.println("Minimum days: " + minDays(bloomDay2, m, k)); // expected: -1
    }
}

Interview questions you should be able to answer

• Q: When should you use a sliding window versus two pointers?

  Use two pointers when comparing or matching two elements at separate positions simultaneously — e.g., sorted pair sum, palindrome check, or merging two arrays. Use a sliding window when you need a property over a contiguous subarray or substring — e.g., maximum sum, longest valid window, minimum covering window. The key distinction: two pointers doesn't require contiguity; sliding window does. Both are O(n), but sliding window maintains a range with explicit left/right boundaries and a shrink condition.

• Q: How do you recognize a dynamic programming problem versus one that can be solved greedily?

  A problem is a DP candidate when: (1) it asks for an optimal value (max/min/count), (2) it has overlapping subproblems (the same sub-computation recurs), and (3) it has optimal substructure (the global optimum is built from local optima). A greedy solution works when a locally optimal choice at each step always leads to the global optimum — provable via an exchange argument. If you can swap a non-greedy choice with a greedy one and never make things worse, greedy is correct. When in doubt: try greedy, find a counterexample, then fall back to DP.

• Q: How does path compression work in Union-Find, and why does it matter?

  Without path compression, find(x) walks up the parent chain one node at a time — O(log n) with union by rank, or O(n) in the worst case without it. Path compression rewires every node on the path directly to the root during find: parent[x] = find(parent[x]). This flattens the tree so future find calls on the same nodes are O(1). Combined with union by rank (always attach the shorter tree under the taller one), the amortized cost per operation drops to O(α(n)) — the inverse Ackermann function, effectively a constant below 5 for any realistic input size.

• Q: What is the invariant of a monotonic stack, and how do you decide when to use one?

  A monotonic stack maintains a strict ordering property (increasing or decreasing) from bottom to top at all times. When a new element violates the property, elements are popped until the property is restored — and those pops are precisely the answers for "next greater / next smaller" queries. Use a monotonic stack whenever the problem involves finding, for each element, the first element to its left or right that satisfies a comparison condition: next greater element, largest rectangle in histogram (pop when a shorter bar arrives), daily temperatures, trapping rainwater. The amortized cost is O(n) because each element is pushed and popped at most once.

• Q: How do you recognize that a problem calls for binary search on the answer rather than binary search on an array?

  Look for these signals: (1) the problem asks for a minimum or maximum value that satisfies some constraint, (2) the answer space is a contiguous numeric range (e.g., days, capacity, speed), and (3) you can write a monotone feasibility function — canAchieve(mid) returns true for all values above (or below) some threshold. Once you identify that predicate, binary search on the range [lo, hi] to find the boundary. Classic examples: "minimum capacity to ship packages in D days" (search capacity 1..sum), "koko eating bananas" (search speed 1..max), "minimum days to make m bouquets" (search days 1..maxDay).

• Q: How do you reason about the time complexity of a backtracking algorithm?

  Model the recursion as a state space tree: each level represents one decision point and each branch represents one choice. If the branching factor is b (choices per level) and the maximum depth is d (length of a complete solution), the tree has at most O(b^d) nodes — giving a worst-case time complexity of O(b^d × work per node). For permutations of n elements: b starts at n and decreases (n! total leaves), so complexity is O(n · n!). Pruning cuts entire subtrees before exploring them — it doesn't change the worst case but dramatically reduces the average case. Always state the un-pruned upper bound first, then explain how pruning improves it in practice.

Further reading

• LeetCode Explore — "Learn" section patterns (Two Pointers, Sliding Window, Binary Search, Dynamic Programming, Backtracking)
• Grokking the Coding Interview — pattern-first approach with categorized problems
• Introduction to Algorithms (CLRS) Ch. 15 (DP), Ch. 16 (Greedy), Ch. 21 (Union-Find), Ch. 22–26 (Graph algorithms)
• NeetCode.io — 150 curated problems organized by pattern with video explanations
• cp-algorithms.com — rigorous write-ups on monotonic stack, DSU, topological sort, and binary search on answer
• William Fiset's Union-Find series on YouTube — visual walkthrough of path compression and union by rank