# Problem Statement Q2:

``````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
``````

# Note: See hints only if you are unable to solve the problem at least twice. Be astute.

Hint 1:

You can solve this question by iterating through the main input array once.
What are the time and space implications of this approach?

Hint 2:

Iterate through the main array, and look for the first integer in the potential subsequence.
If you find that integer, keep on iterating through the main array,
but now look for the second integer in the potential subsequence.
Continue this process until you either find every integer in the potential subsequence or
you reach the end of the main array.

# Optimal Time and Space Complexity:

O(n) time complexity| O(1) space complexity - where n is the length of the input array

# Solutions will be posted in 12 hours of posting the above question.

``````import ValidateSubsequence as program
import unittest

class TestProgram(unittest.TestCase):

def test_case_1(self):
output = program.validateSubsequence([5, 1, 22, 25, 6, -1, 8, 10], [5, 22, 25, -1, 10])
# This should return True
self.assertTrue(output == True)

def test_case_2(self):
output = program.validateSubsequence([5, 1, 22, 25, 6, -1, 8, 10], [5, 22, 25, 10, -1])
# This should return False
self.assertTrue(output == False)

def test_case_3(self):
output = program.validateSubsequence2([5, 1, 22, 25, 6, -1, 8, 10], [5, 22, 25, 10, -1])
# This should return False
self.assertTrue(output == False)

if __name__ == '__main__':
# Driver Code starts here
unittest.main()
``````

# Date 9th July, 2022

Two approaches used:

First Approach

``````def validateSubsequence(array, sequence):

# Approach 1:
# TC = O(n), where n is the length of the array
# SC = O(1)
lenSeq = len(sequence)
seqIdx = 0
for val in array:
# for every val in array, check if it is equal
# to the sequence[seqIdx]. If equal then do seqIdx++ until
# either array exhausts or the len(seq) becomes equal to seqIdx i.e., either of the arrays is exhausted
if seqIdx == lenSeq:
break
if val == sequence[seqIdx]:
seqIdx += 1
return seqIdx == lenSeq
``````

# Date 9th July, 2022

Two approaches used:

Second Approach

def validateSubsequence2(array, sequence):

``````# Approach Number 2: using 2 pointers
# Time Complexity = Big-Oh(n), where n is the length of the array
# Space Complexity = Big-Oh(1)
arrIdx, seqIdx = 0, 0
# maintaining two pointers for array and seq.
# until array exhausts or sequence exhausts do
# if arr[arrIdx] = seq[seqidx] then increment both the ptrs
# else only increment arrIdx
while (arrIdx < len(array)) and (seqIdx < len(sequence)):
if sequence[seqIdx] == array[arrIdx]:
seqIdx += 1
arrIdx += 1
return seqIdx == len(sequence)``````

arr = [5, 1, 22, 25, 6, -1, 8, 10]
sequence = [1, 6, -1, 10]
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(arr,sequence))

@ishwar-chippa-d8fbca71 good work, you just need to work on variable name definitions and the comments. For example the definition of the variable j is not clear on the first look. One has to go through the line by line to understand the approach. Once that is sorted, I believe this is an acceptable solution. Kuddos!!!

Simple answer if someone has learnt DS.