Valid Subsequence Verification — Problem Statement & Solution Guide
Quick Answer & Algorithm Key Takeaway
Master coding challenges related to Stack and solve the Valid Subsequence Verification problem optimally.
O(n)O(1)Problem Description
Given two integer arrays, source and sequence, determine whether sequence appears in source as a subsequence. A subsequence is formed by removing zero or more elements from source without changing the order of the remaining elements. Return true if every element of sequence can be matched to an element in source in the same relative order; otherwise return false. The algorithm must run in linear time relative to the length of source.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Valid Subsequence Verification"
WHY DOES IT MATTER?
Subsequence checks appear in version‑control diffing, event‑stream validation, and permission‑hierarchy checks; mastering the two‑pointer pattern equips engineers to solve any ordered‑matching problem efficiently.
OPTIMIZATION CHALLENGE
The insight is that you never need to backtrack; once an element of the sequence is matched, you can safely discard all earlier source elements, reducing the problem to a single forward scan.
REAL-WORLD CONNECTION
Think of a playlist (source) and a setlist (sequence). The DJ wants to know if the setlist songs appear in the same order within the larger playlist without rearranging tracks—exactly what the algorithm verifies.
During an interview, write the two‑pointer loop first, then immediately add a guard for the edge case where the sequence is empty—this shows you consider corner cases and keeps the code concise.
COMPLEXITY AT A GLANCE
O(n)O(1)Core Theory — Why This Approach?
The subsequence verification problem is a classic example of a linear scan using two-pointer technique. By iterating through the source array while maintaining an index into the sequence, we can greedily match each required element in order, guaranteeing correctness because any valid subsequence must preserve relative ordering. Naïve solutions that generate all subsets or use nested loops explode combinatorially (O(2^n) or O(n*m)) and become infeasible for large inputs (n up to 10^5). The optimal paradigm leverages the fact that we only need to know whether each element of the sequence appears later in the source, which can be resolved in a single pass, yielding O(n) time and O(1) auxiliary space.
Interview Questions on This Problem
Q1How would you modify the algorithm if the source array is a read‑only stream and you cannot store it entirely in memory?
Maintain only the current pointer into the sequence and consume the stream element‑by‑element; as soon as the sequence pointer reaches the end you can return true, otherwise false after the stream ends.
Q2Can you extend the solution to handle multiple sequences simultaneously (e.g., checking if several candidate subsequences exist in the same source)?
Yes, keep a map from each candidate’s next expected value to a list of candidate indices; as you scan the source, advance all candidates waiting for that value, which runs in O(n + totalLength) time.
Q3Why does the two‑pointer method work even when the source contains duplicate values?
Because the algorithm only advances the sequence pointer when it finds a matching element; duplicates are naturally skipped or consumed based on order, preserving the required relative ordering.
Examples
Input
source = [5,1,22,25,6,8,10,12], sequence = [1,6,10,12]
Output
true
Explanation: Traverse `source` while keeping a pointer on `sequence`. The pointer advances when a matching element is found: 1 matches at index 1, 6 matches at index 4, 10 matches at index 6, and 12 matches at index 7. All elements of `sequence` are found in order, so the result is true.
Input
source = [5,1,22,25,6,8,10,12], sequence = [1,6,11]
Output
false
Explanation: Scanning `source` yields matches for 1 (index 1) and 6 (index 4). The next required element is 11, which never appears after index 4, so the subsequence cannot be completed. Hence the answer is false.
Input
source = [2,7,4,3,5], sequence = [2,3,5]
Output
true
Explanation: The pointer on `sequence` moves as follows: 2 matches at index 0, 3 matches at index 3, and 5 matches at index 4. All three elements are found in increasing indices, so the output is true.
Constraints
- 1 <= source.length <= 10^5
- 1 <= sequence.length <= source.length
- -10^9 <= source[i] <= 10^9
- -10^9 <= sequence[i] <= 10^9
- All array elements are integers
Optimal Approach & Strategy
Use a two‑pointer scan: iterate source once while advancing a pointer in sequence only on matches, achieving linear time.
Brute Force Approach
Generate every possible subsequence of the source and compare each to the target sequence, which is exponential in the source length.
Code Solutions
function isValidSubsequence(source, sequence) {
let i = 0, j = 0;
while (i < source.length && j < sequence.length) {
if (source[i] === sequence[j]) j++;
i++;
}
return j === sequence.length;
}
const fs = require('fs');
const input = fs.readFileSync(0,'utf8').trim().split(/\s+/).map(Number);
let idx=0;
const n = input[idx++];
const source = input.slice(idx, idx+n); idx+=n;
const m = input[idx++];
const sequence = input.slice(idx, idx+m);
console.log(isValidSubsequence(source, sequence) ? 'true' : 'false');#include <bits/stdc++.h>
using namespace std;
bool isValidSubsequence(const vector<int>& source, const vector<int>& sequence){
size_t i=0,j=0;
while(i<source.size() && j<sequence.size()){
if(source[i]==sequence[j]) ++j;
++i;
}
return j==sequence.size();
}
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);
int n; if(!(cin>>n)) return 0; vector<int> source(n); for(int &x:source)cin>>x;
int m; cin>>m; vector<int> sequence(m); for(int &x:sequence)cin>>x;
cout<<(isValidSubsequence(source,sequence)?"true":"false");
return 0;}
import java.io.*;
import java.util.*;
public class Main {
public static boolean isValidSubsequence(int[] source, int[] sequence) {
int i = 0, j = 0;
while (i < source.length && j < sequence.length) {
if (source[i] == sequence[j]) {
j++;
}
i++;
}
return j == sequence.length;
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int[] source = new int[n];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) source[i] = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
int m = Integer.parseInt(st.nextToken());
int[] sequence = new int[m];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < m; i++) sequence[i] = Integer.parseInt(st.nextToken());
System.out.println(isValidSubsequence(source, sequence) ? "true" : "false");
}
}def is_valid_subsequence(source, sequence):
i = j = 0
while i < len(source) and j < len(sequence):
if source[i] == sequence[j]:
j += 1
i += 1
return j == len(sequence)
if __name__ == "__main__":
import sys
data = list(map(int, sys.stdin.read().strip().split()))
if not data:
sys.exit()
idx = 0
n = data[idx]; idx+=1
source = data[idx:idx+n]; idx+=n
m = data[idx]; idx+=1
sequence = data[idx:idx+m]
print(str(is_valid_subsequence(source, sequence)).lower())function isValidSubsequence(source, sequence) {
let i = 0, j = 0;
while (i < source.length && j < sequence.length) {
if (source[i] === sequence[j]) j++;
i++;
}
return j === sequence.length;
}
const fs = require('fs');
const input = fs.readFileSync(0,'utf8').trim().split(/\s+/).map(Number);
let idx=0;
const n = input[idx++];
const source = input.slice(idx, idx+n); idx+=n;
const m = input[idx++];
const sequence = input.slice(idx, idx+m);
console.log(isValidSubsequence(source, sequence) ? 'true' : 'false');Asked in Top Tech Interviews
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.