Knowing how sliding window or binary search works is one skill. Recognizing when to use it in a new problem, under time pressure, is a different skill.

This is where many candidates struggle. They may know the technique well, but fail to connect it to the problem in front of them.

This chapter focuses on that recognition step. We will build a repeatable way to narrow a problem down to one or two likely patterns using three signals: the input type, the constraints, and the keywords in the problem statement.

Every problem carries a few signals that point toward likely patterns before any code is written. Reading those signals deliberately, rather than guessing, is what makes the selection process repeatable.

Signal 1: Input Type

The data structure in the input is usually the strongest single hint. Each data structure has a small set of patterns that show up disproportionately often with it, and identifying the input type collapses a long list of candidate patterns down to a handful.

The mapping is not exhaustive. Some problems combine multiple patterns or sit outside this table entirely. As a starting filter, though, the input type usually points to the right neighborhood.

Signal 2: Constraints (What n Tells You)

Constraints bound the complexity class that can pass within the time limit, which in turn eliminates large groups of patterns before any of them are tried.

The rough rule is that modern systems handle around 10⁸ simple operations per second. Working backwards from the time limit, that gives a usable mapping between input size and the complexity class that is feasible:

So if a problem says n ≤ 10^5, you immediately know that O(n^2) will not work. That eliminates brute force nested loops and points you toward O(n log n) or O(n) techniques.

Signal 3: Keywords in the Problem Statement

Problem statements often contain phrases that have a strong correspondence with specific patterns. The mapping below captures the most reliable cases:

A keyword does not guarantee a specific pattern; it narrows the candidate set to a few strong options. Combined with the input type and constraints, that is usually enough to converge on the right approach.

The three signals combine into a single decision process. Working through the questions below is faster than scanning every pattern in memory:

The flow is a starting point, not a complete decision tree. Its purpose is to convert the open-ended "which of the 20 patterns?" question into a sequence of narrowing questions:

That sequence is what converts pattern selection from guesswork into a process.

The next five examples apply the three signals to common interview problems. The aim is to make the recognition step concrete.

Example 1: Maximum Subarray Sum

Problem: Given an integer array, find the contiguous subarray with the largest sum.

Signal 1 (Input type): Array. This puts us in the array bucket.

Signal 3 (Keywords): "Contiguous subarray" usually suggests sliding window or prefix sum. The variable-size sliding window is ruled out here because values can be negative, so shrinking the window does not necessarily improve the sum.

Signal 2 (Constraints): n ≤ 10^5 typically, so we need O(n) or O(n log n).

Pattern: This is Kadane's algorithm, a one-dimensional dynamic programming approach. The keyword "contiguous subarray" plus "largest sum" is the classic Kadane's trigger. You could also solve it with prefix sums (at each index, subtract the smallest prefix sum seen so far), but Kadane's is the standard approach.

Example 2: Number of Islands

Problem: Given a 2D grid of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and formed by connecting adjacent lands horizontally or vertically.

Signal 1 (Input type): Matrix/Grid. This points toward BFS or DFS.

Signal 3 (Keywords): "Connected" and "adjacent" are graph traversal keywords, and "count the number of" points to counting connected components.

Signal 2 (Constraints): Grid dimensions up to 300x300, so O(m*n) is fine.

Pattern: DFS or BFS flood fill. For each unvisited '1', start a traversal to mark all connected '1's as visited. Each traversal discovers one island. You could also use Union Find, but DFS/BFS is more straightforward here.

Example 3: Course Schedule

Problem: There are n courses labeled 0 to n-1. Some courses have prerequisites: to take course a, you must first take course b. Given the total number of courses and a list of prerequisite pairs, determine if you can finish all courses.

Signal 1 (Input type): This is a directed graph (courses are nodes, prerequisites are edges).

Signal 3 (Keywords): "Prerequisites" implies ordering. "Can you finish all courses" is asking if a valid ordering exists.

Signal 2 (Constraints): n ≤ 2000, edges ≤ 5000. O(V+E) is fine.

Pattern: Cycle detection on a directed graph. The "can you finish all courses" question reduces to "does the directed graph have a cycle?" A cycle means no valid ordering exists. The full topological order is not strictly required for the boolean version; cycle detection via DFS (or Kahn's algorithm checking that all nodes get processed) is enough.

Example 4: Find Median from Data Stream

Problem: Design a data structure that supports adding numbers and finding the median of all numbers added so far.

Signal 1 (Input type): Stream of numbers, with no fixed array to work with.

Signal 3 (Keywords): "Median" means the middle element. We need quick access to the middle of a dynamic, growing dataset.

Signal 2 (Constraints): Up to 5 * 10^4 calls, so each operation should be efficient.

Pattern: Two heaps (a max-heap for the lower half and a min-heap for the upper half). The tops of both heaps give you the middle elements. This is the classic "kth element in a stream" family, and the keyword "median" maps directly to the two-heap pattern.

Example 5: Word Break

Problem: Given a string s and a dictionary of words, determine if s can be segmented into a space-separated sequence of dictionary words.

Signal 1 (Input type): String.

Signal 3 (Keywords): "Can be segmented" means "is it possible," which hints at DP. We are making choices (where to break the string) and earlier choices affect later options.

Signal 2 (Constraints): String length up to 300. O(n^2) is acceptable.

Pattern: Dynamic programming. Define dp[i] = "can the first i characters be segmented?" For each position, check all possible last words. This has optimal substructure (dp[i] depends on dp[j] for j < i) and overlapping subproblems.

The table below is a reference for the most common pattern-to-problem mappings. It is best used as a lookup during practice rather than something to memorize in one sitting.

Many problems leave two or three candidate patterns standing after the first pass. The filters below usually break the tie.

1. Use Constraints to Eliminate Options

Constraints are the cheapest filter. Apply them before anything else:

2. Look at What the Problem Is Optimizing

The kind of optimization the problem asks for narrows the pattern further:

3. Look at the Output Type

The shape of the expected output is another reliable filter:

4. Start Simple and Improve

When the direction is still ambiguous, a correct but slower solution is a stronger starting point than no solution at all. Optimizing an existing approach is usually easier to reason about than designing the optimal one from a blank page.

Pattern recognition handles most interview problems, but not every one. Some problems will not map cleanly to anything you have seen before. The next chapter covers what to do when the usual signals fail and you need to build a solution from scratch.