Hello Aspiring Data and Decision Scientists,
In case you missed, the introduction to the series of problems, please go through the following discussion:
.
.
.
.
PROBLEM #2 STATEMENT: Problem Level: Easy
The following is a Array Sequencing problem which will test the basic knowledge of position referencing and looping of arrays.
Please Note: Submission should not exceed Time Complexity O(n) and Space Complexity O(1)
Validate Subsequence
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
PS: Will share the solution by end of the day
1 Like
Hi Thripathi,
Here the Nested For loop will make the worst time complexity of the code O(n^2), which makes the code a bad one in this case.
I understand the rationale behind your code of using two nested loops. Would request you to use the power of array indexing and pointers, and rethink the logic where
As mentioned in the problem statement, the max complexity your code
Hint 1: Use only one for loop which iterate over the array
Hint 2: Increment the index/pointer of the sequence
**Solution:**
def isValidSubsequence(array, sequence):
# Initializing array index position to 0
array_ptr = 0
# Initializing sequence index position to 0
seq_ptr = 0
# the following code will check find the corresponding sequence element in array
while seq_ptr < len(sequence) and array_ptr < len(array):
# If there is a match, then increase the sequence counter
if sequence[seq_ptr] == array[array_ptr]:
seq_ptr += 1
# Increase the array index at each iteration
array_ptr += 1
# Return a boolean value True if the sequence is found in the array else returns False
return len(sequence) == seq_ptr
**Solution : Using For Loop" : Have also posted using while loop
# O(n) time | O(1) space - where n is the length of the array
def isValidSubsequence(array, sequence):
# Initializing the sequence Idx to 0
seqIdx = 0
# Iterating the array using for loop
for value in array:
# If Sequence Idx is equal to the length of the sequence, this means there are no elements in the sequence to trace, therefore we'll break out of the loop
if seqIdx == len(sequence):
break
# if the sequence value matches the array value
if sequence[seqIdx] == value:
# Increment the seq counter by 1
seqIdx += 1
# Exit For loop
# Return a boolean value True if the sequence length is equal to the Seq Idx else returns False
return seqIdx == len(sequence)
1 Like