Is Subsequence — Problem Statement & Solution Guide
Problem Description
Given two arrays of characters arr and sub, determine if sub is a subsequence of arr. A subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Is Subsequence"
WHY DOES IT MATTER?
The two-pointer pattern is essential because it transforms a potentially exponential problem into a linear one, enabling real-time processing of large datasets. It also provides a clear, deterministic control flow that is easy to reason about and debug, which is critical in high-stakes production systems.
OPTIMIZATION CHALLENGE
The key insight is that you never need to backtrack: once you skip an element in the main array, it can never be part of the subsequence. This eliminates nested loops and reduces the time complexity from O(n*m) to O(n + m).
REAL-WORLD CONNECTION
In distributed event sourcing, you often need to verify that a series of user actions (the subsequence) appears in the same order within a massive event log. The two-pointer technique mirrors the way event processors scan logs once, advancing their expected event pointer only when a match is found, ensuring efficient stream reconciliation.
When explaining this to an interviewer, emphasize that the algorithm is essentially a single-pass scan with constant extra space, and that it is the canonical solution for subsequence problems in interviews and production code alike.
COMPLEXITY AT A GLANCE
O(n + m)O(1)Core Theory — Why This Approach?
The problem of determining whether one array of characters is a subsequence of another is a classic example of the two-pointer technique, which operates in linear time relative to the combined lengths of the arrays. A naive approach would attempt to generate all possible subsequences of the larger array and then search for the target subsequence, leading to exponential time complexity and making it infeasible for large inputs. Instead, by maintaining two indices—one iterating over the main array and one over the candidate subsequence—we can scan each element exactly once. Whenever the current element of the main array matches the current element of the subsequence, we advance the subsequence pointer; otherwise, we simply advance the main pointer. If the subsequence pointer reaches the end of the subsequence array, we have successfully matched all required characters in order, confirming that it is indeed a subsequence. This approach guarantees O(n + m) time complexity, where n is the length of the main array and m is the length of the subsequence, and uses only O(1) additional space, making it optimal for large-scale data.
The two-pointer strategy is powerful because it leverages the inherent order of the sequences without backtracking or recursion. By avoiding nested loops, we eliminate the quadratic blow-up that would otherwise occur when checking each possible position in the main array for every character of the subsequence. Moreover, the algorithm is cache-friendly and can be implemented in-place, which is advantageous in memory-constrained environments such as embedded systems or high-throughput streaming services. The simplicity of the method also translates to lower risk of bugs and easier reasoning during code reviews and interviews.
In distributed systems, a similar pattern emerges when reconciling event streams: you often need to verify that a sequence of events (e.g., user actions) appears in the same order within a larger log. The two-pointer technique maps directly to stream processing, where you consume events from the log and advance your expected event pointer only when a match occurs. This analogy helps engineers understand why the algorithm is both efficient and robust in real-world scenarios.
Interview Questions on This Problem
Q1How would you modify the subsequence check algorithm to handle very large input streams that cannot fit into memory, such as logs stored in a distributed file system?
You would process the stream in a single pass, maintaining only the current position in the subsequence. As each character arrives from the stream, compare it to the current subsequence character; if it matches, advance the subsequence pointer. This streaming approach keeps memory usage constant and works with data that is too large to load entirely into RAM.
Q2During a recent interview at a fintech startup, the interviewer asked: "What is the worst-case time complexity of your solution, and can you explain why it is optimal?" How would you answer?
The worst-case time complexity is O(n + m), where n is the length of the main array and m is the length of the subsequence. This is optimal because each element of both arrays is examined at most once; any algorithm must read the entire subsequence to confirm it, and reading the main array cannot be avoided in the worst case.
Q3A senior engineer at a global product company asked: "If the subsequence array is sorted, can you use binary search to improve the algorithm?" What is your response?
Sorting the subsequence does not help because the relative order of elements in the subsequence must match the order in the main array. Binary search would only be useful if we were looking for a subsequence that could be reordered, which is not the case here. Therefore, the two-pointer linear scan remains the best approach.
Examples
Input
["a", "b", "c"], ["a", "b"]
Output
true
Explanation: Step-by-step: with input ["a", "b", "c"] and ["a", "b"], we check each character in the subsequence ["a", "b"] and find them in order in the main sequence ["a", "b", "c"], giving output true
Input
["a", "b", "c"], ["b", "a"]
Output
false
Explanation: Step-by-step: with input ["a", "b", "c"] and ["b", "a"], we check each character in the subsequence ["b", "a"] and find that they are not in order in the main sequence ["a", "b", "c"], giving output false
Constraints
- 0 <= arr.length <= 10^5
- 0 <= sub.length <= 10^4
- Characters consist of lowercase English letters.
Optimal Approach & Strategy
Use two pointers to scan both arrays in a single pass; advance the subsequence pointer only on matches. This achieves linear time and constant space.
Brute Force Approach
Generate all possible subsequences of the main array and check if the target subsequence is among them. This requires exponential time and is impractical for large arrays.
Verified Code Solutions
function isSubsequence(arr, sub) { let i = 0, j = 0; while (i < arr.length && j < sub.length) { if (arr[i] === sub[j]) j++; i++; } return j === sub.length; }class Solution { public: bool isSubsequence(vector<char> arr, vector<char> sub) { int i = 0, j = 0; while (i < arr.size() && j < sub.size()) { if (arr[i] == sub[j]) j++; i++; } return j == sub.size(); } }class Solution { public boolean isSubsequence(String[] arr, String[] sub) { int i = 0, j = 0; while (i < arr.length && j < sub.length) { if (arr[i].equals(sub[j])) j++; i++; } return j == sub.length; } }def isSubsequence(arr, sub): i, j = 0, 0; while i < len(arr) and j < len(sub): if arr[i] == sub[j]: j += 1; i += 1; return j == len(sub)function isSubsequence(arr, sub) { let i = 0, j = 0; while (i < arr.length && j < sub.length) { if (arr[i] === sub[j]) j++; i++; } return j === sub.length; }Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.