Original subtitles

Hey, everybody, welcome to AlgoExpert.

In this video we're gonna cover the question

of validating a subsequence.

This is a pretty easy and straightforward question

but it is an interesting one.

Mainly because it deals with a concept

that's very popular in coding interviews

and especially in some of the harder

coding interview questions

that we've got right here on AlgoExpert.

And that concept is the concept of subsequence.

What is a subsequence?

Well, it's a concept that stems from mathematics

and here I'll actually read off

the definition of subsequence from Wikipedia

because I think it's a pretty good definition.

In mathematics, a subsequence is a sequence

that can be derived from another sequence

by deleting some or no elements

without changing the order of the remaining elements.

So for example, if you take a look at the array

that I've got in front of me here,

the one that starts with five and than ends with 10.

This is an array of integers,

so it's a sequence of integers.

And if you were to remove some of the integers

from this sequence, like, for example,

if you were to remove the integer 22.

Or maybe if you were to remove none of the integers,

maybe you didn't remove 22,

the remaining elements would be a subsequence

of the original sequence.

And so this question gives us two arrays of integers,

and we're told that they're non-empty.

And it wants us to write a function

that is gonna determine whether or not

the second array is a valid subsequence of the first one.

So for example here, we have to determine

whether or not this array

is valid subsequence of this array.

And another way to think about subsequences

when we're dealing with arrays

is in order for an array to be a valid subsequence

of another array, all of the integers

in the potential subsequence have to not only appear

in the original array but they also have to appear

in the same order.

They don't necessarily have to be adjacent.

As you can see here, the numbers one, six,

negative one and 10 do appear in this array

but they're not adjacent.

One is here, six is here,

we've got a couple of integers in between them,

then here we've got eight in between negative one and 10,

but they do appear in the original array

and they appear in the same order

where they go from one to six to negative one to 10,

one to six to negative one to 10.

And so if we were to call our function

or the function that we have to write

passing in these two arrays,

the output of our function would be true

because this array indeed a valid subsequence of this array.

So how do we solve this problem?

Well, the first thing that we should realize

is that we're gonna have to traverse

both arrays that were given.

We're gonna have to traverse the potential subsequence

because that's the thing that we're looking for.

We're looking to see if the sequence appears

in the first array.

So we're definitely gonna have to traverse

our entire second array here,

just because we have to know what integers we're looking for

in the first array.

And then we're also gonna have to traverse

our entire main array because our sequence

could basically be located anywhere in the main array.

In other words, the first element in our sequence

could very well be the first element in our main array

and the last element in our sequence

could very well be the last element in our main array.

And in this case, it actually is.

10 is indeed the last element in our main array.

So we're likely gonna have to traverse the entire array.

We might be able to stop early

when we're traversing our array

if we found our entire subsequence already.

But the point is the logic of our algorithm

will likely involve traversing both of these arrays.

Now the question becomes how do we wanna traverse them?

How do we actually find these numbers

and in this order in the main array?

Well, one way to think about it

is that because the order of the elements in a subsequence

and in the original sequence matters,

that means that at the very beginning

when we're just starting to look

for our potential subsequence,

we're really looking for the first element

in the potential subsequence.

We're not looking for six,

we're not looking for negative one,

we're not looking for 10, we're looking for one.

Because if we can't find one,

or if we find other elements before finding one,

that doesn't matter.

Like, a subsequence cares about order.

So we're really looking for the first element which is one.

So what we're gonna do is we're gonna initialize a pointer

underneath the first element of our subsequence

or our potential subsequence and we're gonna say

let's traverse our main array until we find

this first element that our pointer is pointing to.

And so we're gonna put another pointer

underneath the first element in our main array.

And here, as you might imagine,

when we're actually gonna write the code

for this algorithm, this might be a simple for loop

or a simple while loop.

But the point is we're iterating through this array

by looking at elements and seeing if we find

the first element in our potential subsequence.

So here we've got a five.

Is five equal to one?

No, it's not.

So what we're gonna do is we're just gonna move our pointer

to the next element.

We're gonna move along in our first array

until we find this first element

from our potential subsequence.

It turns out here that the second element

is the one we're looking for.

This is a one and the element that we're looking for is one.

So at this point what we do is we say okay,

we found the first element in our potential subsequence,

now we need to look for the second element.

We need to look for the number six.

So what we're gonna do is we're gonna move our pointer

in our potential subsequence to the next element.

So the pointer now points to six.

And we're gonna move our pointer

in our main sequence forward.

And the reason we're moving forward

and we don't have to go back or anything

is because once again order matters.

We found the first element in our subsequence here.

That means that any future elements that we're looking for,

we're looking to find them after this element.

We don't wanna go back, we don't wanna stay here, obviously,

we wanna keep going forward.

So we're gonna move along forward here.

And now we're gonna do the same thing.

We're gonna compare the element that we're at

in our main array to the element that our pointer

in our potential subsequence is pointing at

and see if they match.

Is 22 equal to six?

No, it's not.

So we're gonna move forward to 25.

Is 25 equal to six?

No, it's not.

So we're gonna keep moving forward.

Is six equal to six?

Yes, it is.

We've got a match.

So at this point we do exactly what we did

when we found the first element here with the two ones.

We move the pointer in our subsequence forward.

So this is now gonna point to negative one.

And then we keep moving along in our main array.

So here we're now gonna be under the negative one.

It turns out that we've got another match immediately.

Negative one is equal to negative one.

So now we can move this pointer along to the right

and move this pointer along to the right.

And to clarify here, what we're effectively saying

is that we have found one, six and negative one

in this order, not necessarily adjacent but in this order,

in the main array.

And now we're looking for 10, which is the next number

in our potential subsequence,

and it happens to be the last number.

So is 10 equal to eight?

No, it's not.

Then, we move this pointer to the next element, which is 10.

And at this point 10 is equal to 10,

so we move our pointer here in the subsequence,

we move it forward and we realize that we are

past the bound of our subsequence.

There are no more elements here.

So we can basically stop the algorithm.

And here, this is sort of what I hinted at earlier.

We could've had more elements in our main array.

We could've had maybe 11 here.

We could've had another number, seven.

But the point is we wouldn't have had to keep on

going to the 11 or to the seven

because we've finished traversing

through our entire subsequence.

We found the entire subsequence so we can stop early.

And so that's our algorithm.

The algorithm has us traversed

both arrays that were given simultaneously.

And we're effectively moving forward

in the main array without stopping.

The only thing that we do is at every point

or at every element, we check if that element

matches the current element that we're looking for

in the subsequence.

And in the subsequence, we only move forward

when we find a match.

Until we find a match for the current element that we're at,

we don't move forward in the subsequence,

we only move forward in the main array.

So as far as complexity analysis goes,

let's start with the time complexity.

The time complexity of this algorithm

is gonna be O of N time

where N is the length of the main array.

The reason it's O of N time

is because we're gonna have to traverse

through the entire main array.

Like we said, we iterate through it without stopping

and all that we do is we check if there's a match

with the current element, like, for instance,

the number 10 here and the element that we're at

in the subsequence, the comparison of the numbers

is a constant time operation.

Now you might say but wait a second,

sometimes we're gonna stop early once we found

the entire subsequence

but that's only gonna be in certain cases.

It's only gonna be if the subsequence

ends before the end of the main array

like here when we added 11 and seven.

Yeah, we didn't traverse through the entire main array.

We said we could stop at 10

because we found the entire subsequence

but still we had to traverse

through the majority of the array.

It's not like we only traversed through four elements.

That would only happen if the subsequence

were at the very beginning of the main array.

But also sometimes the subsequence

is gonna take up the entire main array.

Like, for instance, before when we didn't have 11 and seven,

when we only had the 10 here at the end,

this subsequence had us go all the way to the end

and that's where we found the last element.

And also if the subsequence isn't contained

in the main array.

Like, imagine here instead of having these numbers,

we just had the number, I don't know, 23,

we would have to iterate through the entire array

to see that 23 is not contained in it.

So all that to say the time complexity

is best described here as O of N

where N is the length of the main array.

Even though there will be a few cases

where we will do fewer than N iterations or N operations.

Now as far as the space complexity.

Space complexity is gonna be constant.

So it'll be O of one.

And the reason it's constant

is because we're not storing anything extra,

except for maybe a couple of pointers

for our position in the respective arrays.

But we're not storing any other big variables

or big pieces of data

and more specifically we're not storing anything

that is gonna increase in size

with respect to the size of the two inputs.

So with that, let's jump into the code walkthrough

to see what this looks like in code.

All right, so we've got

our validate subsequence function to find.

It takes in two non-empty arrays of integers

where the second array is a potential subsequence

of the first array.

And we're actually gonna cover two code solutions here.

They both have the same overarching logic,

the logic that we covered

in the conceptual overview of this video.

But the first solution is gonna use a while loop

to traverse through both arrays in tandem

and is gonna keep track of the positions

that we're at in both arrays.

Whereas the second solution is gonna use a for loop

to traverse through the main array

and is gonna keep track of our position

only in the second array.

So let's jump into the first solution,

the one with the while loop.

For this solution, like I said,

we're gonna need to keep track

of our position in both arrays.

So we're gonna declare our arrIdx

which is gonna be initialized to zero,

and this is gonna be our position in the main array.

And then we're gonna have our seqIdx,

also initialized to zero,

our position in the sequence array.

And our while loop is basically

gonna perform some operations.

We'll cover the operations in a second.

So long as we are in bounds of both the main array

and the sequence array.

So while our arrIdx is smaller than the length of our array,

and while our seqIdx is smaller

than the length of our sequence,

we're gonna perform some stuff.

What are we gonna perform?

What are we gonna do?

Well, we're looking to see if the element

that we are at in the main array

is equal to the element that we're at in the sequence array.

We're specifically looking to find or to match

the current element in the sequence.

So we're gonna say if our array at arrIdx

is equal to our sequence at seqIdx,

if that's the case then we found

our current element in the sequence

and we're gonna move our position,

the sequence forward by one.

So we're gonna increment our seqIdx by one.

And then regardless of whether this condition is true,

so regardless of whether or not we have a match

between our current number in the main array

and in the sequence array, we're gonna keep moving forward

in the main array.

So regardless of this condition,

we are gonna increment our arrIdx by one.

And that means that we're gonna keep moving along

in the main array.

And in the sequence array,

we'll move along only if we found a match.

Eventually, we're gonna break out of this while loop,

either 'cause we're gonna have traversed the entire sequence

or 'cause we're gonna have traversed

the entire array or both.

And in that case, we're gonna return

whether or not we found a valid subsequence.

How do we know that?

Well, if we've traversed through the entire sequence

by the end of this while loop,

then we found a valid subsequence

'cause that means that we will have hit

and satisfied this if condition here

and the times where N is the length of the sequence.

And therefore we will have matched

all elements in the sequence,

and we will have a valid subsequence.

So we will only have a valid subsequence

if the seqIdx is equal to the length of the sequence.

If we're ever at a point here after this while loop

where the seqIdx is smaller than the length of the sequence,

either we're still at the very beginning

or maybe even we're at the very last element,

maybe we're at length of sequence minus one here.

If that's the case, we clearly didn't find

all of the sequence elements in the main array

and we do not have a valid subsequence.

So here we wanna return seqIdx

is equal to the length of the sequence.

So like I said in the conceptual overview of this video,

this algorithm is gonna run in O of N time

where N is the length of our main array

and it's gonna run in O of one space.

And you can see the space complexity very clearly.

All that we store are these two variables here,

nothing that increases with the size of the inputs.

And as far as the time complexity,

you can see here that we are going

through the entire array with this while loop,

and once we reach the end, we break out of it

and we're done.

We might break early if the sequence is smaller

but we're not sure.

And there are many times when, for instance,

we're not gonna have a valid subsequence

when we're gonna have to go through the end of the array.

So the most accurate way of describing this time complexity

is gonna be O of N where N is the length of the array.

Now on average or in the worst case, it's O of N.

So this is the solution that uses a while loop.

Now let's cover the solution with a for loop.

So we'll copy the code.

Well I guess we'll comment it out first.

We'll copy the code and delete most of it.

The one thing that we'll keep is the seqIdx

initialized to zero 'cause we're still gonna keep track

of our position in the sequence with this pointer

but instead of a while loop with the arrIdx pointer,

we're just gonna do a for loop to the array.

So we'll say for value in our array.

And here we're gonna do a similar check

as we had here on line six with the if statement.

We're gonna say if our sequence at the seqIdx

is equal to our value, then we have a match.

It's the same sort of logic as here.

We have a match and what do we wanna do?

We wanna increase our seqIdx.

We'll say seqIdx plus equal to one.

However, the one thing that we wanna do here

since we don't have our while loop

that's gonna break if we're out of bounds with the sequence,

is we wanna add this condition inside of our for loop.

So before we actually do this if statement here,

which would probably cause an error

'cause we might be accessing something out of bounds,

we wanna have this condition

that is gonna say if our seqIdx is equal

to the length of the sequence here, then we break.

We break out of our for loop.

So we're essentially mimicking

this while loop condition here.

And then if we break out of our for loop,

we just return the same thing,

seqIdx is equal to the length of the sequence.

And of course here you don't even need to break,

you could just return true in this case

because if our seqIdx is equal

to the length of the sequence,

then we've got a valid subsequence.

But we're gonna check this here at the very anyway.

So I just like to break here.

Up to you.

As far as the complexity analysis for this solution,

it's gonna be identical to the first one.

So I'm just gonna go ahead and copy that here.

And the reason it's identical

is because we're doing the same logic.

We're only storing one variable here with our index.

We're iterating through our array here

and keeping track of the value.

We're not storing anything with respect

to the size of the input.

And as far as the time complexity,

we're really just doing a for loop through the array

so it's gonna be O of N time.

We might break early but we don't really know that.

On average or in the worst case,

we won't break early and that's why it's O of N time.

So with that I hope that you found this video informative

and I'll see you in the next one.