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