Validate Subsequence

Tags

Validate Subsequence

Category

Arrays

Difficulty

Easy

Problem Statement

Given two non-empty arrays of integers, determine whether the second array is a subsequence of the first. A subsequence is a set of numbers that appear in the same order within the original array, but not necessarily adjacent.

Intuition

Since the subsequence must preserve order, we can scan through the main array while maintaining a pointer into the candidate subsequence. Each time the current main-array element matches the current subsequence element, we advance the subsequence pointer. If we reach the end of the subsequence, it is valid.

Approach

  1. Initialize a pointer seqIdx at 0 for the subsequence.
  2. Iterate through each element in the main array.
  3. If seqIdx has reached the end of the subsequence, break early — the subsequence is valid.
  4. If the current main-array element equals sequence[seqIdx], increment seqIdx.
  5. After the loop, check if seqIdx equals the length of the subsequence.

Pseudocode

function isValidSubsequence(array, sequence):
    seqIdx = 0
    for value in array:
        if seqIdx == length(sequence):
            break
        if value == sequence[seqIdx]:
            seqIdx += 1
    return seqIdx == length(sequence)

Time & Space Complexity

  • Time: O(n) — where n is the length of the main array. We traverse it at most once.
  • Space: O(1) — only a single index variable is used.

Key Insights

  • This is a classic two-pointer / greedy pattern: greedily match as early as possible.
  • Order matters — [1, 3, 2] is not a subsequence of [1, 2, 3].
  • Every array is a subsequence of itself.
  • The empty array is a subsequence of any array (though this problem specifies non-empty arrays).

Edge Cases

  • The sequence is longer than the main array — impossible to be a subsequence.
  • The sequence equals the main array — valid subsequence.
  • Single-element arrays — check if that one element appears in the main array.
  • Duplicate values in both arrays — the greedy match handles duplicates correctly because it only advances once per match.

Linked mentions