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
You can solve this question by iterating through the main input array once.
What are the time and space implications of this approach?
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.
O(n) time complexity| O(1) space complexity - where n is the length of the input array
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()
Two approaches used:
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
Two approaches used:
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):
if seq[j] == val:
j += 1
return j == len(seq)
@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.