# Given two non-empty arrays of integers, write a function that
# determines whether the second array is a subsequence of the first one.

# A subsequence of an array is a set of numbers that aren't necessarily
# adjacent in the array but that are in the same order as they appear in
# the array. For instance, the numbers [1, 3, 4] form a subsequence of the
# array [1, 2, 3, 4], and so do the numbers [2, 4]. Note that a single number
# in an array and the array itself are both valid subsequences of the array.

# Sample Input
# array = [5, 1, 22, 25, 6, -1, 8, 10]
# sequence = [1, 6, -1, 10]
# Sample Output
# true

# Solution 1: Time complexity: O(n), Space complexity: O(1)
# Use two pointers on the array and subsequence arrays and whenever there
# is a match, advance the subsequence pointer. Finally, check whether the
# subsequence pointer exactly matches the length of the string.
def is_valid_subsequence(arr, seq):
	j = 0
	for val in arr:
		if j == len(seq):
			break
		if seq[j] == val:
			j += 1
	return j == len(seq)

print(is_valid_subsequence([5, 1, 22, 25, 6, -1, 8, 10], [1, 6, -1, 10]))
print(is_valid_subsequence([5, 1, 22, 25, 6, -1, 8, 10], [5, 1, 22, 25, 6, -1, 8, 10, 12]))