Pattern Recognition

1. Introduction: Cracking the Code

When you sit down for a technical interview, the interviewer will rarely say, "Please write a Binary Search algorithm." Instead, they will give you a convoluted story about a monkey eating bananas, or a security guard checking cameras.

The secret to passing FAANG interviews is not memorizing 1000 LeetCode solutions. The secret is Pattern Recognition. Every problem is just a disguise for one of about 15 core algorithmic patterns. If you learn to map specific words, phrases, and constraints to their underlying data structures, you can deduce the optimal solution before you even fully understand the problem.

2. The Golden Rule of Constraints

Before reading the problem description, look at the Constraints at the bottom of the problem. The constraints mathematically dictate the time complexity you must achieve, which instantly narrows down your options.

Note: Modern servers do about $10^8$ operations per second. Your algorithm must finish in under 1 second.

| Constraint (Max $N$) | Required Big-O | Algorithm Categories | | :--- | :--- | :--- | | $N \le 12$ | $O(N!)$ | Backtracking (Permutations, N-Queens) | | $N \le 25$ | $O(2^N)$ | Backtracking (Subsets), Bitmask DP | | $N \le 100$ | $O(N^3)$ | 3D DP, Floyd-Warshall (All-Pairs Shortest Path) | | $N \le 1000$ | $O(N^2)$ | 2D DP, Nested Loops, Matrix Traversal | | $N \le 10^5$ | $O(N \log N)$ | Sorting, Binary Search, Heaps, Divide & Conquer | | $N \le 10^6$ | $O(N)$ | Two Pointers, Sliding Window, HashMaps, Greedy, Stack | | $N \ge 10^9$ | $O(\log N)$ or $O(1)$ | Binary Search on Math, Math formulas |

Example: If the problem asks for the maximum subarray sum, and $N \le 10^5$, you CANNOT use an $O(N^2)$ nested loop (which would be $10^{10}$ operations). You MUST use an $O(N)$ approach (Kadane's Algorithm).

3. Mapping Keywords to Patterns

Listen carefully to the phrasing of the problem. Specific words are massive red flags for specific algorithms.

1. "Top K", "Kth Largest", "K Closest"

• The Pattern: Heap (Priority Queue).
• Why: Sorting takes $O(N \log N)$. A Heap of size K takes $O(N \log K)$. Whenever you see "Top K", immediately write PriorityQueue on the whiteboard.

2. "Sorted Array", "Search in $O(\log N)$"

• The Pattern: Binary Search.
• Why: A sorted array is the universal prerequisite for Binary Search. Even if the problem doesn't ask you to search, if the array is sorted, think Binary Search (or Two Pointers).

3. "Subarray", "Substring", "Contiguous"

• The Pattern: Sliding Window (if positive integers) or Prefix Sum Hash (if negative integers).
• Why: A subarray must be strictly connected. A sliding window perfectly models a contiguous block of elements expanding and shrinking.

4. "Combinations", "Permutations", "All Possible Ways"

• The Pattern: Backtracking (DFS).
• Why: "All possible" implies an exhaustive search of a decision tree. Backtracking explores every path and reverses choices to explore alternatives.

5. "Minimum / Maximum Ways", "Optimal Substructure"

• The Pattern: Dynamic Programming.
• Why: If you have overlapping subproblems and are asked for the optimal (max/min/total) value, it is DP. (e.g., "Minimum coins to make change", "Max profit from stocks").

6. "Shortest Path" (Unweighted)

• The Pattern: Breadth-First Search (BFS).
• Why: BFS expands level-by-level. The first time it hits the target, it is mathematically guaranteed to be the shortest path.

7. "Dependencies", "Prerequisites", "Order of Execution"

• The Pattern: Topological Sort (Graph).
• Why: "Course A must be taken before Course B" forms a Directed Acyclic Graph. Kahn's Algorithm or DFS Post-Order builds the execution chain.

8. "Connected Components", "Islands", "Grouping"

• The Pattern: DFS/BFS on Matrix or Union-Find.
• Why: Grouping touching elements requires traversing through all connected nodes. Union-Find is specifically optimized for dynamically joining sets.

9. "Next Greater Element", "Nearest Smaller Element"

• The Pattern: Monotonic Stack.
• Why: A stack that strictly maintains increasing or decreasing order can find the "next largest" element in $O(N)$ time instead of an $O(N^2)$ brute force.

4. The Interview Workflow

When faced with a new problem, run through this flowchart:

1. Understand the constraints: Is $N = 100$ or $10^5$? This dictates the algorithm.
2. Identify the Data Structure: Are we parsing a String? A Matrix? A Tree?
3. Keyword Scan: Look for the keywords listed above.
4. Brute Force: Orally explain the naive solution immediately. "I could use two loops to check every subarray, taking $O(N^2)$."
5. Optimize via Pattern: "However, since we need a contiguous subarray and the numbers are positive, I can use a Sliding Window to drop it to $O(N)$."
6. Code and Test: Write the template for that pattern, and dry-run a small example to check boundary conditions.

5. Common Traps & Deceptions

Interviewers love to disguise problems or bait you into using the wrong pattern.

1. The "Unsorted" Binary Search Bait

   • The Trap: You are given an unsorted array and asked for a specific value. You think you need $O(N)$.
   • The Reality: Problems like "Find Peak Element" or "Search in Rotated Sorted Array" allow Binary Search $O(\log N)$ even when the whole array isn't perfectly sorted, because you can still eliminate half the search space based on a local mathematical condition.

2. The "Graph" Array Bait

   • The Trap: You are given an array like [2, 3, 1, 1, 4] (Jump Game) and try to use DP.
   • The Reality: Arrays can represent implicit graphs. The indices are nodes, and the values are the edges. You can often use Greedy or BFS algorithms on 1D arrays!

3. The "Matrix" Tree Bait

   • The Trap: "Number of Islands" looks like a 2D Array problem.
   • The Reality: It's a Graph problem. The grid cells are nodes, and their 4 neighbors are the edges. Use Graph DFS/BFS.

6. Practice Identifying Patterns

Test your intuition. Don't write code, just name the pattern:

Problem 1: Given an array of integers, find the sum of all elements in a contiguous subarray of size K. Pattern: Fixed Sliding Window.

Problem 2: Given a string, find all permutations of the string. Pattern: Backtracking.

Problem 3: Given an array of strings, group the anagrams together. Pattern: Hash Map (Group/State Hashing using sorted strings as keys).

Problem 4: Given a schedule of tasks with start and end times, find the minimum number of rooms required. Pattern: Interval Greedy (Sweepline / Min-Heap).

Problem 5: Find the 10th most frequent word in a massive document. Pattern: Hash Map (for frequencies) + Min-Heap of size 10.

7. Summary

• Never jump into code. Spend 2 minutes analyzing the constraints and keywords.
• Constraints are cheat codes. If $N=20$, it's Backtracking. If $N=10^5$, it's $O(N)$ or $O(N \log N)$.
• Memorize the triggers. "Top K" = Heap. "Shortest Path" = BFS. "Contiguous" = Sliding Window. "Prerequisites" = Topological Sort.

Advanced Code Implementations

// Example: Fast and Slow Pointers (Cycle Detection)
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; next = null; }
}

public class FastSlowPointer {
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) return false;
        ListNode slow = head;
        ListNode fast = head.next;
        while (slow != fast) {
            if (fast == null || fast.next == null) return false;
            slow = slow.next;
            fast = fast.next.next;
        }
        return true;
    }
}

// Example: Merge Intervals Pattern
import java.util.*;

public class MergeIntervals {
    public int[][] merge(int[][] intervals) {
        if (intervals.length <= 1) return intervals;
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
        
        List<int[]> merged = new ArrayList<>();
        int[] currentInterval = intervals[0];
        merged.add(currentInterval);
        
        for (int[] interval : intervals) {
            int currentEnd = currentInterval[1];
            int nextBegin = interval[0];
            int nextEnd = interval[1];
            
            if (currentEnd >= nextBegin) {
                currentInterval[1] = Math.max(currentEnd, nextEnd);
            } else {
                currentInterval = interval;
                merged.add(currentInterval);
            }
        }
        return merged.toArray(new int[merged.size()][]);
    }
}

Expanded Interview Q&A

Q1: How do you identify a sliding window problem?

Answer: The problem asks for the longest/shortest/optimal subarray or substring, and the elements must be contiguous.

Q2: When should you use the Two Pointer pattern?

Answer: When dealing with sorted arrays (searching for a pair) or trying to detect cycles in linked lists.

Q3: What is the Top 'K' Elements pattern?

Answer: When asked to find the top/smallest/most frequent 'K' elements, using a Heap (Priority Queue) is usually the optimal approach.

Q4: Why sort intervals before merging them?

Answer: Sorting by the start time ensures that overlapping intervals are strictly adjacent to each other in the array, making a single pass sufficient.

Q5: How do you know when to use Monotonic Stack?

Answer: When you need to find the "Next Greater Element" or "Next Smaller Element" for elements in an array.