Two Pointers - Valid Subsequence Checker

Problem Statement

Given two arrays of integers, determine if the second array is a valid subsequence of the first. A subsequence is a sequence that can be derived from the original array by deleting some or no elements without changing the order of the remaining elements. This is an easy-level problem that tests your ability to traverse arrays while maintaining order.

Example

Input: array = [5, 1, 22, 25, 6, -1, 8, 10], sequence = [1, 6, -1, 10]

Output: true (the sequence [1, 6, -1, 10] appears in order within the array)

Input: array = [5, 1, 22, 25, 6, -1, 8, 10], sequence = [25, 1, 6]

Output: false (the order does not match)

Code

public class Solution {
    public boolean isValidSubsequence(int[] array, int[] sequence) {
        int seqIndex = 0;
        
        for (int value : array) {
            if (seqIndex == sequence.length) {
                break;
            }
            if (sequence[seqIndex] == value) {
                seqIndex++;
            }
        }
        return seqIndex == sequence.length;
    }
}
            

def is_valid_subsequence(array, sequence):
    seq_idx = 0
    
    for value in array:
        if seq_idx == len(sequence):
            break
        if sequence[seq_idx] == value:
            seq_idx += 1
    return seq_idx == len(sequence)

# Example usage
print(is_valid_subsequence([5, 1, 22, 25, 6, -1, 8, 10], [1, 6, -1, 10]))  # True
print(is_valid_subsequence([5, 1, 22, 25, 6, -1, 8, 10], [25, 1, 6]))      # False
            

function isValidSubsequence(array, sequence) {
    let seqIndex = 0;
    
    for (let value of array) {
        if (seqIndex === sequence.length) {
            break;
        }
        if (sequence[seqIndex] === value) {
            seqIndex++;
        }
    }
    return seqIndex === sequence.length;
}

// Example usage
console.log(isValidSubsequence([5, 1, 22, 25, 6, -1, 8, 10], [1, 6, -1, 10])); // true
console.log(isValidSubsequence([5, 1, 22, 25, 6, -1, 8, 10], [25, 1, 6]));    // false
            

Explanation

• Initialize a pointer (seqIndex) to track progress in the sequence array.
• Iterate through the main array, checking each element against the current sequence element.
• If there’s a match, increment the sequence pointer to move to the next element.
• Stop if the sequence pointer reaches the end (all elements found) or continue until the array is exhausted.
• Return true if the entire sequence was matched, false otherwise.

Note