What THEY Do Not Teach YOU In Data Science! - Data Structures Problem #2 By Anish Arya (Machine Learning and Reinforcement Learning Consultant)

Data Science, AI and ML
#1

Hello Aspiring Data and Decision Scientists,

In case you missed, the introduction to the series of problems, please go through the following discussion:
.
.

What THEY Do Not Teach YOU In Data Science! - By Anish Arya (Machine Learning and Reinforcement Learning Consultant)

.
.

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
#2
#3

predict
predict1360×553 10.5 KB

#4

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

#5 
   **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
#6 
**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