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
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.
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
# 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)
@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!!!