Foundation · Module 3 · Lesson 3

Subarrays vs subsequences

Contiguous ranges and order-preserving choices.

15–25 min readLesson 15 of 123

Lesson 15 of 123

1d streak

Subarray vs Subsequence vs Subset: Know the Difference

One of the most frequent sources of confusion in array interview problems is mixing up subarrays, subsequences, and subsets. Understanding their constraints dictates whether a problem calls for Prefix Sums, Sliding Window, Dynamic Programming, or Backtracking.

Visual Distinction on Array: [1, 2, 3]text

Original: [ 1,  2,  3 ]

1. SUBARRAY (Contiguous & Order-Preserving):
   Valid:   [1], [2], [3], [1, 2], [2, 3], [1, 2, 3]
   Invalid: [1, 3] (Not contiguous!)
   Total Count for length n: n * (n + 1) / 2 = O(n²)

2. SUBSEQUENCE (Non-Contiguous, but Order-Preserving):
   Valid:   [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]
   Invalid: [3, 1] (Order is reversed!)
   Total Count for length n: 2^n - 1 non-empty choices = O(2^n)

3. SUBSET (Any combination, order does not matter):
   Valid:   {1, 3}, {3, 1}, {2}, {1, 2, 3}

Concept	Contiguous?	Order Preserved?	Total Combinations	Standard Approach
Subarray	YES	YES	n(n+1)/2 = O(n²)	Sliding Window, Kadane’s Algorithm, Prefix Sums
Subsequence	NO	YES	2^n = O(2^n)	Dynamic Programming (LIS, LCS), Backtracking
Subset	NO	NO	2^n = O(2^n)	Bitmasking, Backtracking (Subsets problem)

Golden Interview Rule: Can You Sort the Array?

If a problem asks about subarrays, sorting is forbidden because sorting destroys contiguous index relationships. If a problem asks about subsequences or subsets, sorting is often a great first step because it groups duplicates and unlocks two pointers or binary search.

Cost Model

Complexity & Trade-offs

OperationTimeSpaceWhy

Enumerate all

O(n²) / O(2ⁿ)

Output-sensitive

The bound follows from the number of states visited and the work performed per transition.

When to use it

Contiguous data, strings, matrix grids, and in-place transformations.
Problems where indexes encode processed regions.
Cache-friendly scans and compact storage.

Common mistakes

Using a stale index after insertion, deletion, or a boundary move.
Overwriting a value before it has been consumed.
Assuming a matrix is square or a string is mutable.

Practice prompts

Reproduce the worked Subarrays vs subsequences example without looking at the trace.
Change one input condition and explain whether the Subarrays vs subsequences invariant still holds.
Implement the approach, derive its cost, and compare it with a straightforward baseline.

Mastery check

Can you derive it instead of memorizing it?

State the invariant before looking at code.

Explain why every transition is safe.

Construct a worst-case input.

Name one alternative and its trade-off.