Subarray vs Subsequence Patterns: The LeetCode Decision Framework

If you have ever picked the wrong algorithm for a LeetCode problem and spent thirty minutes before realizing your entire approach was off, there is a good chance you confused a subarray problem with a subsequence problem. These two concepts sound almost identical, but they demand completely different strategies.

Subarray patterns on LeetCode require contiguous elements, which means sliding window, prefix sum, and Kadane's algorithm are your primary tools. Subsequence problems allow gaps between selected elements, which means dynamic programming is almost always the answer. Mixing these up is the fastest way to waste an interview.

This guide gives you a clear decision framework. By the end, you will know exactly which pattern to reach for the moment you read a problem statement — no more guessing, no more wasted time picking the wrong approach.

A subarray is a contiguous slice of an array. Given [1, 2, 3, 4, 5], the slice [2, 3, 4] is a subarray because the elements sit next to each other with no gaps. You can think of it as dragging a window across the array — everything inside the window is included.

A subsequence is an ordered selection from an array where elements do not need to be adjacent. From the same array [1, 2, 3, 4, 5], the selection [1, 3, 5] is a valid subsequence because the relative order is preserved even though elements 2 and 4 are skipped.

This single distinction — contiguous versus non-contiguous — determines your entire algorithmic approach. Subarray problems can typically be solved in O(n) or O(n log n) using greedy or hash-based techniques. Subsequence problems usually require O(n^2) or O(n log n) dynamic programming because you need to track choices across non-adjacent positions.

Because subarrays are contiguous, you can exploit that structure with three powerful patterns. Each one leverages the fact that expanding or shrinking a contiguous window is an O(1) operation, which keeps overall complexity low.

The sliding window pattern comes in two flavors. Fixed-size windows solve problems like "maximum sum of k consecutive elements" by maintaining a running total and sliding the window one position at a time. Variable-size windows handle problems like "smallest subarray with sum >= target" by expanding the right boundary until a condition is met, then contracting the left boundary to minimize the window.

The prefix sum plus hash map pattern is the go-to for subarray sum problems. You compute a running prefix sum and store previously seen sums in a hash map. When the current prefix sum minus a target value exists in the map, you have found a valid subarray. This is exactly how you solve Subarray Sum Equals K (#560) in O(n) time.

Kadane's algorithm solves the Maximum Subarray problem (#53) — finding the contiguous subarray with the largest sum. The idea is simple: at each position, decide whether to extend the current subarray or start fresh. Keep a running maximum sum and a global maximum. This runs in O(n) time with O(1) space.

Subsequence problems almost always require dynamic programming because you need to make choices about which elements to include, and those choices have consequences that propagate through the rest of the array. There is no contiguous structure to exploit, so greedy sliding window approaches fail.

The Longest Increasing Subsequence (#300) is the poster child for subsequence DP. The classic O(n^2) approach uses a 1D DP array where dp[i] represents the length of the longest increasing subsequence ending at index i. For each element, you check all previous elements and extend the best valid subsequence. An O(n log n) optimization uses patience sorting with binary search.

The Longest Common Subsequence (#1143) requires 2D DP. You build a table where dp[i][j] represents the LCS length for the first i characters of string one and the first j characters of string two. If characters match, you take the diagonal plus one. If they do not match, you take the maximum of the cell above or to the left.

Is Subsequence (#392) is an easier variant that only asks whether one string is a subsequence of another. This can be solved greedily in O(n) with two pointers because you are not optimizing — just checking existence. It is a good warm-up before tackling the harder subsequence DP problems.

The decision process is surprisingly straightforward once you know what to look for. Read the problem statement and scan for specific keywords that immediately narrow your approach.

If the problem says "contiguous", "subarray", or "substring", you are dealing with a subarray problem. Your first instinct should be sliding window for optimization problems or prefix sum plus hash map for counting and sum-target problems. If the problem asks for maximum or minimum of a running quantity, consider Kadane's algorithm.

If the problem says "subsequence", "not necessarily contiguous", or asks you to select elements while preserving order, you are dealing with a subsequence problem. Reach for dynamic programming. Determine whether you need 1D DP (single sequence decisions) or 2D DP (comparing two sequences).

There is one important edge case: some problems can be framed as either subarray or subsequence problems depending on constraints. For example, "longest substring without repeating characters" is technically a subarray problem on a string, solved with a sliding window. But "longest common subsequence" with the same two strings requires DP. Always let the contiguity requirement guide you.

The following problems are organized by whether they are subarray or subsequence problems, along with the pattern you should apply. Working through these in order builds your intuition for recognizing the distinction in new problems.

For subarray problems, start with Maximum Subarray (#53) to learn Kadane's algorithm. Then move to Subarray Sum Equals K (#560) for the prefix sum plus hash map technique. Minimum Size Subarray Sum (#209) teaches the variable sliding window, and Maximum Average Subarray I (#643) covers the fixed sliding window.

For subsequence problems, begin with Is Subsequence (#392) as a warm-up using the two-pointer greedy approach. Then tackle Longest Increasing Subsequence (#300) for core 1D DP. Longest Common Subsequence (#1143) introduces 2D DP, and Number of Longest Increasing Subsequence (#673) tests whether you truly understand the LIS recurrence.

Pay close attention to the complexity gap. Every subarray problem above runs in O(n) time. The subsequence problems range from O(n) for the trivial existence check to O(n^2) for the DP solutions. This complexity difference is a built-in sanity check — if your subarray solution is O(n^2), you are probably missing a better approach.

The most effective way to build pattern recognition for subarray and subsequence problems is to practice them in pairs. Solve a subarray problem, then immediately solve a subsequence problem with a similar feel. This contrast cements the distinction in your mind far faster than grinding one type at a time.

Start with Maximum Subarray (#53) using Kadane's algorithm. Once you are comfortable, move to Subarray Sum Equals K (#560) to learn the prefix sum plus hash map technique. These two problems cover the most common subarray patterns you will see in interviews.

Next, shift to subsequence problems. Solve Longest Increasing Subsequence (#300) with the O(n^2) DP approach first, then optimize it to O(n log n) with patience sorting. Follow that with Longest Common Subsequence (#1143) to practice 2D DP. These are the two most frequently tested subsequence patterns.

After solving each problem, use YeetCode flashcards to drill the pattern recognition. The key is not memorizing solutions — it is training your brain to see "contiguous" and immediately think sliding window or prefix sum, and to see "subsequence" and immediately think DP. Spaced repetition makes this automatic over time, so when you sit down for an interview the right approach comes to you in seconds.