// Pattern Recognition: See X, Think Y

core idea

You don’t derive the right pattern under interview pressure — you recognize it, and recognition runs on signals: a handful of words and constraints that name the pattern before you’ve written a line of code. This page is the lookup table for that skill. Read every problem statement in three passes:

• input shape — sorted array? tree? grid? linked list? intervals? a stream?
• question shape — find one thing, find the longest/shortest, count the ways, enumerate all of them, or order by dependency?
• constraints — “contiguous”, “in-place”, O(log n) demanded, the size of n. Constraints are the strongest signal of the three: they exist to rule patterns out.

the master table

One row per pattern: the signal that names it, the first question that starts your solution, and the cleanest problem to re-read when the row feels shaky.

When two rows fire at once — sorted input and a pair question lights up both Two Pointers and Binary Search — the first-question column is the tiebreak: whichever question you can actually answer is your pattern. The most common collision, pointers vs hashmap on pair sums, is big enough to have its own page.

keyword quick-scan

The master table works top-down from structure. This one works bottom-up from vocabulary — the give-away words that appear verbatim in statements:

worked examples

Three problems with no page on this site, classified cold using nothing but the tables above. This is the loop to run on every problem you meet from now on.

1 — squares of a sorted array (LC 977)

Given an array sorted ascending — possibly containing negatives — return the squares of all elements, also sorted ascending, in O(n).

nums = [-4, -1, 0, 3, 10]  →  [0, 1, 9, 16, 100]

Signal extraction: “sorted” fires two rows — but we aren’t searching for anything, so binary search is out and Two Pointers is in. “O(n)” kills the lazy answer (square everything, Array.Sort — O(n log n)); the follow-up is the real question. The wrinkle is the negatives: squaring scrambles the middle of the array but not the ends — the largest square must sit at one end of the input. That’s the opposite-ends discard argument from the Two Pointers template: compare the two end squares, and the larger one can be committed immediately, because nothing between the pointers can beat it.

public int[] SortedSquares(int[] nums)
{
    int n = nums.Length;
    var result = new int[n];
    int left = 0, right = n - 1;

    for (int write = n - 1; write >= 0; write--)   // biggest square sits at an END — fill backward
    {
        int l = nums[left] * nums[left], r = nums[right] * nums[right];
        if (l > r) { result[write] = l; left++; }
        else       { result[write] = r; right--; }
    }
    return result;
}

O(n) time, O(n) for the output you were asked to produce. The recognition took three signals and about twenty seconds; the code is the opposite-ends skeleton writing into an output array instead of returning a pair.

2 — minimum size subarray sum (LC 209)

Given an array of positive integers and a target, return the length of the shortest contiguous subarray whose sum is at least target, or 0 if none exists.

nums = [2, 3, 1, 2, 4, 3], target = 7  →  2   (the subarray [4, 3])

Signal extraction: “shortest contiguous subarray” is the Sliding Window row almost verbatim — and “shortest” selects the discipline: shrink while VALID, record while shrinking. Now the first question — is validity monotonic? Yes, and the word doing the work is “positive”: expanding can only raise the sum, shrinking can only lower it, so sum >= target flips cleanly as the window moves. That word is load-bearing. Allow one negative number and monotonicity dies — the window pattern would silently return wrong answers, and you’re in prefix-sum territory: the Subarray Sum Equals K world for the equals-k question. The at-least-k version with negatives (LC 862) is a step further still — prefix sums alone aren’t enough, it needs a monotonic deque on top.

public int MinSubArrayLen(int target, int[] nums)
{
    int best = int.MaxValue, sum = 0, left = 0;

    for (int right = 0; right < nums.Length; right++)
    {
        sum += nums[right];                        // expand — every element enters once
        while (sum >= target)                      // shortest → shrink while VALID
        {
            best = Math.Min(best, right - left + 1);
            sum -= nums[left++];                   // record, then give up the left edge
        }
    }
    return best == int.MaxValue ? 0 : best;
}

On the example, the first valid window is [2, 3, 1, 2]; the answer [4, 3] is found during the final shrink — which is exactly why the record-then-shrink order matters. Every element enters and leaves the window at most once: O(n) time, O(1) space.

3 — find peak element (LC 162)

Given an array where nums[i] != nums[i + 1] for all neighbors, return the index of any peak — an element greater than both neighbors (treat the edges as having −∞ outside). Required: O(log n).

nums = [1, 2, 1, 3, 5, 6, 4]  →  5   (nums[5] = 6 beats both neighbors)

Signal extraction: the array is not sorted, yet the constraint demands O(log n) — this is the row-four signal that trips almost everyone, because the table’s phrasing is “sorted or a yes/no question with a flip”, and the second half is what fires here. Ask the first question: what can I check at mid that tells me which half to keep? The slope. If nums[mid] < nums[mid + 1] you’re on an uphill — and an uphill must end in a peak before the array runs out, so a peak certainly exists to the right. Otherwise mid is on a downhill or is itself a peak, so a peak certainly exists at or left of mid. Either way one comparison discards half the array while the invariant “a peak lies in [left, right]” survives — the same boundary form as Find Minimum in Rotated Sorted Array.

public int FindPeakElement(int[] nums)
{
    int left = 0, right = nums.Length - 1;

    while (left < right)                           // boundary template: converge on the flip
    {
        int mid = left + (right - left) / 2;
        if (nums[mid] < nums[mid + 1])
            left = mid + 1;                        // uphill to the right — a peak is that way
        else
            right = mid;                           // mid may BE the peak — never discard it
    }
    return left;
}

On the example this converges to index 5. Note right = mid, not mid - 1 — the classic boundary-template detail, because mid might be the answer; and left = mid + 1 is safe precisely because nums[mid] is strictly smaller than its right neighbor, so mid cannot be a peak. O(log n) time, O(1) space.

That’s the whole skill: signals in, pattern out, first question answered — then code. The master cheat sheet is this page compressed to one screen for the night before; day 7 of the study plan is where you come back and run the drill for real.