Is Valid Subsequence

The problem is to determine whether a given array called sequence is a valid subsequence of another given array called arr.

A subsequence is defined as a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements. For example, [1, 3, 4] is a subsequence of [1, 2, 3, 4], but [1, 4, 3] is not a subsequence of [1, 2, 3, 4].

In this problem, we are given two integer arrays arr and sequence, and we need to check if sequence can be derived from arr by deleting some or no elements without changing the order of the remaining elements.

The solution should return a boolean indicating whether sequence is a valid subsequence of arr.

For example, if arr = [1, 2, 3, 4, 5] and sequence = [2, 4, 5], the function should return True, because sequence can be derived from arr by deleting the elements [1, 3].

Solution 1: Brute Force

The simplest solution to this problem is to iterate through both arrays and check if each element of sequence appears in arr in the same order. This solution has a time complexity of O(n) where n is the length of arr, but is inefficient because it iterates over arr for each element in sequence.

Advantages: Easy to implement.

Disadvantages: Inefficient for large inputs.

Here is an implementation of the brute force solution:

def is_valid_subsequence(arr, sequence):
    seq_index = 0
    for num in arr:
        if seq_index == len(sequence):
            break
        if num == sequence[seq_index]:
            seq_index += 1
    return seq_index == len(sequence)

Solution 2: Two Pointers

A more efficient solution is to use two pointers to iterate through arr and sequence. The first pointer iterates through arr while the second pointer iterates through sequence. If the current element in arr matches the current element in sequence, we move both pointers forward. Otherwise, we only move the first pointer forward. This solution has a time complexity of O(n) where n is the length of arr.

Advantages: More efficient than the brute force solution.

Disadvantages: None.

Here is an implementation of the two pointers solution:

def is_valid_subsequence(arr, sequence):
    arr_index = 0
    seq_index = 0
    while arr_index < len(arr) and seq_index < len(sequence):
        if arr[arr_index] == sequence[seq_index]:
            seq_index += 1
        arr_index += 1
    return seq_index == len(sequence)

Solution 3: Using Pop

Another way to solve the problem is to pop the first element of sequence for each element in arr that matches the first element in sequence. If we can pop all the elements in sequence, it is a valid subsequence. This solution has a time complexity of O(n) where n is the length of arr, but may modify sequence.

Advantages: Simple implementation.

Disadvantages: Modifies sequence.

Here is an implementation of the pop solution:

def is_valid_subsequence(arr, sequence):
    for num in arr:
        if sequence and num == sequence[0]:
            sequence.pop(0)
    return not sequence