Arrays Q2: Validate Subsequence, Data Structure Problems Series, Part 1 (Python)

Software Development
1

Arrays Q2: Validate Subsequence, Data Structure Problems Series, Part 1 (Python)

In case anyone missed Q1 of Part 1 Arrays, then please visit below link for the same:

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

Try solving it!

Hints are in the first comment.

UnitTest.py is in the second comment.

Solutions will be posted in 12 hours

3

Here are the two hints to solve the above problem:

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.

4 
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()
5

@Author: Anish Arya

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
6

@Author: Anish Arya

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

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

9

@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!!!

10

Simple answer if someone has learnt DS.