Would you like to inspect the original subtitles? These are the user uploaded subtitles that are being translated:
1
00:00:00,860 --> 00:00:03,290
Hey, everybody, welcome to AlgoExpert.
2
00:00:03,290 --> 00:00:05,850
In this video we're gonna cover the question
3
00:00:05,850 --> 00:00:07,473
of validating a subsequence.
4
00:00:08,560 --> 00:00:11,330
This is a pretty easy and straightforward question
5
00:00:11,330 --> 00:00:13,240
but it is an interesting one.
6
00:00:13,240 --> 00:00:15,770
Mainly because it deals with a concept
7
00:00:15,770 --> 00:00:18,540
that's very popular in coding interviews
8
00:00:18,540 --> 00:00:21,110
and especially in some of the harder
9
00:00:21,110 --> 00:00:22,470
coding interview questions
10
00:00:22,470 --> 00:00:24,750
that we've got right here on AlgoExpert.
11
00:00:24,750 --> 00:00:28,902
And that concept is the concept of subsequence.
12
00:00:28,902 --> 00:00:30,610
What is a subsequence?
13
00:00:30,610 --> 00:00:33,740
Well, it's a concept that stems from mathematics
14
00:00:33,740 --> 00:00:35,250
and here I'll actually read off
15
00:00:35,250 --> 00:00:38,410
the definition of subsequence from Wikipedia
16
00:00:38,410 --> 00:00:40,960
because I think it's a pretty good definition.
17
00:00:40,960 --> 00:00:44,940
In mathematics, a subsequence is a sequence
18
00:00:44,940 --> 00:00:47,620
that can be derived from another sequence
19
00:00:47,620 --> 00:00:51,210
by deleting some or no elements
20
00:00:51,210 --> 00:00:55,790
without changing the order of the remaining elements.
21
00:00:55,790 --> 00:00:57,920
So for example, if you take a look at the array
22
00:00:57,920 --> 00:00:59,220
that I've got in front of me here,
23
00:00:59,220 --> 00:01:02,440
the one that starts with five and than ends with 10.
24
00:01:02,440 --> 00:01:04,580
This is an array of integers,
25
00:01:04,580 --> 00:01:06,910
so it's a sequence of integers.
26
00:01:06,910 --> 00:01:09,850
And if you were to remove some of the integers
27
00:01:09,850 --> 00:01:11,790
from this sequence, like, for example,
28
00:01:11,790 --> 00:01:14,260
if you were to remove the integer 22.
29
00:01:14,260 --> 00:01:17,490
Or maybe if you were to remove none of the integers,
30
00:01:17,490 --> 00:01:19,690
maybe you didn't remove 22,
31
00:01:19,690 --> 00:01:23,010
the remaining elements would be a subsequence
32
00:01:23,922 --> 00:01:26,800
of the original sequence.
33
00:01:26,800 --> 00:01:30,860
And so this question gives us two arrays of integers,
34
00:01:30,860 --> 00:01:33,230
and we're told that they're non-empty.
35
00:01:33,230 --> 00:01:35,380
And it wants us to write a function
36
00:01:35,380 --> 00:01:37,570
that is gonna determine whether or not
37
00:01:37,570 --> 00:01:42,140
the second array is a valid subsequence of the first one.
38
00:01:42,140 --> 00:01:44,520
So for example here, we have to determine
39
00:01:44,520 --> 00:01:46,310
whether or not this array
40
00:01:46,310 --> 00:01:49,860
is valid subsequence of this array.
41
00:01:49,860 --> 00:01:52,390
And another way to think about subsequences
42
00:01:52,390 --> 00:01:54,150
when we're dealing with arrays
43
00:01:54,150 --> 00:01:57,530
is in order for an array to be a valid subsequence
44
00:01:57,530 --> 00:02:01,830
of another array, all of the integers
45
00:02:01,830 --> 00:02:06,830
in the potential subsequence have to not only appear
46
00:02:07,050 --> 00:02:10,270
in the original array but they also have to appear
47
00:02:10,270 --> 00:02:11,870
in the same order.
48
00:02:11,870 --> 00:02:14,100
They don't necessarily have to be adjacent.
49
00:02:14,100 --> 00:02:16,980
As you can see here, the numbers one, six,
50
00:02:16,980 --> 00:02:20,160
negative one and 10 do appear in this array
51
00:02:20,160 --> 00:02:21,660
but they're not adjacent.
52
00:02:21,660 --> 00:02:23,600
One is here, six is here,
53
00:02:23,600 --> 00:02:25,850
we've got a couple of integers in between them,
54
00:02:25,850 --> 00:02:28,950
then here we've got eight in between negative one and 10,
55
00:02:28,950 --> 00:02:31,320
but they do appear in the original array
56
00:02:31,320 --> 00:02:33,400
and they appear in the same order
57
00:02:33,400 --> 00:02:37,280
where they go from one to six to negative one to 10,
58
00:02:37,280 --> 00:02:39,840
one to six to negative one to 10.
59
00:02:39,840 --> 00:02:41,620
And so if we were to call our function
60
00:02:41,620 --> 00:02:43,380
or the function that we have to write
61
00:02:43,380 --> 00:02:45,220
passing in these two arrays,
62
00:02:45,220 --> 00:02:47,600
the output of our function would be true
63
00:02:47,600 --> 00:02:52,600
because this array indeed a valid subsequence of this array.
64
00:02:52,870 --> 00:02:54,950
So how do we solve this problem?
65
00:02:54,950 --> 00:02:56,940
Well, the first thing that we should realize
66
00:02:56,940 --> 00:02:59,720
is that we're gonna have to traverse
67
00:02:59,720 --> 00:03:01,940
both arrays that were given.
68
00:03:01,940 --> 00:03:04,960
We're gonna have to traverse the potential subsequence
69
00:03:04,960 --> 00:03:07,570
because that's the thing that we're looking for.
70
00:03:07,570 --> 00:03:11,420
We're looking to see if the sequence appears
71
00:03:11,420 --> 00:03:13,040
in the first array.
72
00:03:13,040 --> 00:03:14,580
So we're definitely gonna have to traverse
73
00:03:14,580 --> 00:03:16,520
our entire second array here,
74
00:03:16,520 --> 00:03:20,150
just because we have to know what integers we're looking for
75
00:03:20,150 --> 00:03:21,670
in the first array.
76
00:03:21,670 --> 00:03:23,900
And then we're also gonna have to traverse
77
00:03:23,900 --> 00:03:27,470
our entire main array because our sequence
78
00:03:27,470 --> 00:03:31,670
could basically be located anywhere in the main array.
79
00:03:31,670 --> 00:03:34,490
In other words, the first element in our sequence
80
00:03:34,490 --> 00:03:37,520
could very well be the first element in our main array
81
00:03:37,520 --> 00:03:39,480
and the last element in our sequence
82
00:03:39,480 --> 00:03:42,080
could very well be the last element in our main array.
83
00:03:42,080 --> 00:03:43,800
And in this case, it actually is.
84
00:03:43,800 --> 00:03:46,610
10 is indeed the last element in our main array.
85
00:03:46,610 --> 00:03:49,640
So we're likely gonna have to traverse the entire array.
86
00:03:49,640 --> 00:03:51,690
We might be able to stop early
87
00:03:51,690 --> 00:03:53,060
when we're traversing our array
88
00:03:53,060 --> 00:03:55,690
if we found our entire subsequence already.
89
00:03:55,690 --> 00:03:58,720
But the point is the logic of our algorithm
90
00:03:58,720 --> 00:04:02,340
will likely involve traversing both of these arrays.
91
00:04:02,340 --> 00:04:05,580
Now the question becomes how do we wanna traverse them?
92
00:04:05,580 --> 00:04:08,270
How do we actually find these numbers
93
00:04:08,270 --> 00:04:11,690
and in this order in the main array?
94
00:04:11,690 --> 00:04:13,240
Well, one way to think about it
95
00:04:13,240 --> 00:04:18,030
is that because the order of the elements in a subsequence
96
00:04:18,950 --> 00:04:22,440
and in the original sequence matters,
97
00:04:22,440 --> 00:04:24,660
that means that at the very beginning
98
00:04:24,660 --> 00:04:26,230
when we're just starting to look
99
00:04:26,230 --> 00:04:27,730
for our potential subsequence,
100
00:04:28,580 --> 00:04:31,230
we're really looking for the first element
101
00:04:31,230 --> 00:04:33,040
in the potential subsequence.
102
00:04:33,040 --> 00:04:34,280
We're not looking for six,
103
00:04:34,280 --> 00:04:35,640
we're not looking for negative one,
104
00:04:35,640 --> 00:04:38,330
we're not looking for 10, we're looking for one.
105
00:04:38,330 --> 00:04:40,240
Because if we can't find one,
106
00:04:40,240 --> 00:04:44,240
or if we find other elements before finding one,
107
00:04:44,240 --> 00:04:45,220
that doesn't matter.
108
00:04:45,220 --> 00:04:48,100
Like, a subsequence cares about order.
109
00:04:48,100 --> 00:04:51,540
So we're really looking for the first element which is one.
110
00:04:51,540 --> 00:04:54,460
So what we're gonna do is we're gonna initialize a pointer
111
00:04:54,460 --> 00:04:57,360
underneath the first element of our subsequence
112
00:04:57,360 --> 00:05:00,340
or our potential subsequence and we're gonna say
113
00:05:00,340 --> 00:05:04,370
let's traverse our main array until we find
114
00:05:04,370 --> 00:05:08,120
this first element that our pointer is pointing to.
115
00:05:08,120 --> 00:05:10,100
And so we're gonna put another pointer
116
00:05:10,100 --> 00:05:12,730
underneath the first element in our main array.
117
00:05:12,730 --> 00:05:14,400
And here, as you might imagine,
118
00:05:14,400 --> 00:05:16,140
when we're actually gonna write the code
119
00:05:16,140 --> 00:05:19,550
for this algorithm, this might be a simple for loop
120
00:05:19,550 --> 00:05:20,747
or a simple while loop.
121
00:05:20,747 --> 00:05:23,690
But the point is we're iterating through this array
122
00:05:23,690 --> 00:05:26,740
by looking at elements and seeing if we find
123
00:05:26,740 --> 00:05:29,890
the first element in our potential subsequence.
124
00:05:29,890 --> 00:05:31,550
So here we've got a five.
125
00:05:31,550 --> 00:05:33,120
Is five equal to one?
126
00:05:33,120 --> 00:05:34,120
No, it's not.
127
00:05:34,120 --> 00:05:37,150
So what we're gonna do is we're just gonna move our pointer
128
00:05:37,150 --> 00:05:38,150
to the next element.
129
00:05:38,150 --> 00:05:40,550
We're gonna move along in our first array
130
00:05:40,550 --> 00:05:42,900
until we find this first element
131
00:05:42,900 --> 00:05:44,890
from our potential subsequence.
132
00:05:44,890 --> 00:05:46,920
It turns out here that the second element
133
00:05:46,920 --> 00:05:48,590
is the one we're looking for.
134
00:05:48,590 --> 00:05:52,020
This is a one and the element that we're looking for is one.
135
00:05:52,020 --> 00:05:54,720
So at this point what we do is we say okay,
136
00:05:54,720 --> 00:05:59,020
we found the first element in our potential subsequence,
137
00:05:59,020 --> 00:06:01,280
now we need to look for the second element.
138
00:06:01,280 --> 00:06:03,430
We need to look for the number six.
139
00:06:03,430 --> 00:06:06,170
So what we're gonna do is we're gonna move our pointer
140
00:06:06,170 --> 00:06:09,320
in our potential subsequence to the next element.
141
00:06:09,320 --> 00:06:11,650
So the pointer now points to six.
142
00:06:11,650 --> 00:06:13,340
And we're gonna move our pointer
143
00:06:13,340 --> 00:06:15,650
in our main sequence forward.
144
00:06:15,650 --> 00:06:17,120
And the reason we're moving forward
145
00:06:17,120 --> 00:06:18,770
and we don't have to go back or anything
146
00:06:18,770 --> 00:06:22,210
is because once again order matters.
147
00:06:22,210 --> 00:06:25,810
We found the first element in our subsequence here.
148
00:06:25,810 --> 00:06:29,570
That means that any future elements that we're looking for,
149
00:06:29,570 --> 00:06:32,240
we're looking to find them after this element.
150
00:06:32,240 --> 00:06:35,090
We don't wanna go back, we don't wanna stay here, obviously,
151
00:06:35,090 --> 00:06:36,730
we wanna keep going forward.
152
00:06:36,730 --> 00:06:39,590
So we're gonna move along forward here.
153
00:06:39,590 --> 00:06:40,880
And now we're gonna do the same thing.
154
00:06:40,880 --> 00:06:43,200
We're gonna compare the element that we're at
155
00:06:43,200 --> 00:06:45,810
in our main array to the element that our pointer
156
00:06:45,810 --> 00:06:48,630
in our potential subsequence is pointing at
157
00:06:48,630 --> 00:06:50,170
and see if they match.
158
00:06:50,170 --> 00:06:52,120
Is 22 equal to six?
159
00:06:52,120 --> 00:06:53,040
No, it's not.
160
00:06:53,040 --> 00:06:55,550
So we're gonna move forward to 25.
161
00:06:55,550 --> 00:06:57,780
Is 25 equal to six?
162
00:06:57,780 --> 00:06:58,613
No, it's not.
163
00:06:58,613 --> 00:07:00,490
So we're gonna keep moving forward.
164
00:07:00,490 --> 00:07:02,420
Is six equal to six?
165
00:07:02,420 --> 00:07:03,253
Yes, it is.
166
00:07:03,253 --> 00:07:04,100
We've got a match.
167
00:07:04,100 --> 00:07:06,020
So at this point we do exactly what we did
168
00:07:06,020 --> 00:07:09,070
when we found the first element here with the two ones.
169
00:07:09,070 --> 00:07:12,780
We move the pointer in our subsequence forward.
170
00:07:12,780 --> 00:07:15,660
So this is now gonna point to negative one.
171
00:07:15,660 --> 00:07:18,230
And then we keep moving along in our main array.
172
00:07:18,230 --> 00:07:20,910
So here we're now gonna be under the negative one.
173
00:07:20,910 --> 00:07:23,530
It turns out that we've got another match immediately.
174
00:07:23,530 --> 00:07:25,450
Negative one is equal to negative one.
175
00:07:25,450 --> 00:07:28,550
So now we can move this pointer along to the right
176
00:07:28,550 --> 00:07:31,150
and move this pointer along to the right.
177
00:07:31,150 --> 00:07:34,630
And to clarify here, what we're effectively saying
178
00:07:34,630 --> 00:07:38,930
is that we have found one, six and negative one
179
00:07:38,930 --> 00:07:43,480
in this order, not necessarily adjacent but in this order,
180
00:07:43,480 --> 00:07:44,970
in the main array.
181
00:07:44,970 --> 00:07:48,300
And now we're looking for 10, which is the next number
182
00:07:48,300 --> 00:07:49,900
in our potential subsequence,
183
00:07:49,900 --> 00:07:51,970
and it happens to be the last number.
184
00:07:51,970 --> 00:07:53,480
So is 10 equal to eight?
185
00:07:53,480 --> 00:07:54,600
No, it's not.
186
00:07:54,600 --> 00:07:58,610
Then, we move this pointer to the next element, which is 10.
187
00:07:58,610 --> 00:08:00,900
And at this point 10 is equal to 10,
188
00:08:00,900 --> 00:08:03,860
so we move our pointer here in the subsequence,
189
00:08:03,860 --> 00:08:07,320
we move it forward and we realize that we are
190
00:08:07,320 --> 00:08:10,200
past the bound of our subsequence.
191
00:08:10,200 --> 00:08:12,490
There are no more elements here.
192
00:08:12,490 --> 00:08:14,960
So we can basically stop the algorithm.
193
00:08:14,960 --> 00:08:17,700
And here, this is sort of what I hinted at earlier.
194
00:08:17,700 --> 00:08:20,120
We could've had more elements in our main array.
195
00:08:20,120 --> 00:08:21,710
We could've had maybe 11 here.
196
00:08:21,710 --> 00:08:23,570
We could've had another number, seven.
197
00:08:23,570 --> 00:08:26,570
But the point is we wouldn't have had to keep on
198
00:08:26,570 --> 00:08:28,690
going to the 11 or to the seven
199
00:08:28,690 --> 00:08:31,210
because we've finished traversing
200
00:08:31,210 --> 00:08:32,560
through our entire subsequence.
201
00:08:32,560 --> 00:08:36,550
We found the entire subsequence so we can stop early.
202
00:08:36,550 --> 00:08:38,030
And so that's our algorithm.
203
00:08:38,030 --> 00:08:39,950
The algorithm has us traversed
204
00:08:39,950 --> 00:08:43,090
both arrays that were given simultaneously.
205
00:08:43,090 --> 00:08:46,210
And we're effectively moving forward
206
00:08:46,210 --> 00:08:48,770
in the main array without stopping.
207
00:08:48,770 --> 00:08:51,170
The only thing that we do is at every point
208
00:08:51,170 --> 00:08:53,870
or at every element, we check if that element
209
00:08:53,870 --> 00:08:56,780
matches the current element that we're looking for
210
00:08:56,780 --> 00:08:58,320
in the subsequence.
211
00:08:58,320 --> 00:09:01,920
And in the subsequence, we only move forward
212
00:09:01,920 --> 00:09:03,460
when we find a match.
213
00:09:03,460 --> 00:09:06,750
Until we find a match for the current element that we're at,
214
00:09:06,750 --> 00:09:09,000
we don't move forward in the subsequence,
215
00:09:09,000 --> 00:09:12,080
we only move forward in the main array.
216
00:09:12,080 --> 00:09:14,410
So as far as complexity analysis goes,
217
00:09:14,410 --> 00:09:16,400
let's start with the time complexity.
218
00:09:16,400 --> 00:09:18,890
The time complexity of this algorithm
219
00:09:18,890 --> 00:09:21,770
is gonna be O of N time
220
00:09:21,770 --> 00:09:24,960
where N is the length of the main array.
221
00:09:24,960 --> 00:09:26,300
The reason it's O of N time
222
00:09:26,300 --> 00:09:28,680
is because we're gonna have to traverse
223
00:09:28,680 --> 00:09:30,130
through the entire main array.
224
00:09:30,130 --> 00:09:32,900
Like we said, we iterate through it without stopping
225
00:09:32,900 --> 00:09:35,390
and all that we do is we check if there's a match
226
00:09:35,390 --> 00:09:37,310
with the current element, like, for instance,
227
00:09:37,310 --> 00:09:40,104
the number 10 here and the element that we're at
228
00:09:40,104 --> 00:09:43,200
in the subsequence, the comparison of the numbers
229
00:09:43,200 --> 00:09:45,380
is a constant time operation.
230
00:09:45,380 --> 00:09:47,290
Now you might say but wait a second,
231
00:09:47,290 --> 00:09:50,320
sometimes we're gonna stop early once we found
232
00:09:50,320 --> 00:09:51,840
the entire subsequence
233
00:09:51,840 --> 00:09:54,510
but that's only gonna be in certain cases.
234
00:09:54,510 --> 00:09:57,120
It's only gonna be if the subsequence
235
00:09:57,120 --> 00:09:59,770
ends before the end of the main array
236
00:09:59,770 --> 00:10:02,170
like here when we added 11 and seven.
237
00:10:02,170 --> 00:10:04,720
Yeah, we didn't traverse through the entire main array.
238
00:10:04,720 --> 00:10:06,480
We said we could stop at 10
239
00:10:06,480 --> 00:10:08,640
because we found the entire subsequence
240
00:10:08,640 --> 00:10:10,070
but still we had to traverse
241
00:10:10,070 --> 00:10:11,570
through the majority of the array.
242
00:10:11,570 --> 00:10:14,700
It's not like we only traversed through four elements.
243
00:10:14,700 --> 00:10:16,260
That would only happen if the subsequence
244
00:10:16,260 --> 00:10:20,140
were at the very beginning of the main array.
245
00:10:20,140 --> 00:10:22,290
But also sometimes the subsequence
246
00:10:23,150 --> 00:10:25,950
is gonna take up the entire main array.
247
00:10:25,950 --> 00:10:30,010
Like, for instance, before when we didn't have 11 and seven,
248
00:10:30,010 --> 00:10:33,130
when we only had the 10 here at the end,
249
00:10:33,130 --> 00:10:36,660
this subsequence had us go all the way to the end
250
00:10:36,660 --> 00:10:38,860
and that's where we found the last element.
251
00:10:38,860 --> 00:10:42,130
And also if the subsequence isn't contained
252
00:10:42,130 --> 00:10:43,210
in the main array.
253
00:10:43,210 --> 00:10:46,370
Like, imagine here instead of having these numbers,
254
00:10:46,370 --> 00:10:49,150
we just had the number, I don't know, 23,
255
00:10:49,150 --> 00:10:51,330
we would have to iterate through the entire array
256
00:10:51,330 --> 00:10:53,860
to see that 23 is not contained in it.
257
00:10:53,860 --> 00:10:56,420
So all that to say the time complexity
258
00:10:56,420 --> 00:10:59,540
is best described here as O of N
259
00:10:59,540 --> 00:11:01,760
where N is the length of the main array.
260
00:11:01,760 --> 00:11:03,920
Even though there will be a few cases
261
00:11:03,920 --> 00:11:08,210
where we will do fewer than N iterations or N operations.
262
00:11:08,210 --> 00:11:10,440
Now as far as the space complexity.
263
00:11:10,440 --> 00:11:12,970
Space complexity is gonna be constant.
264
00:11:12,970 --> 00:11:15,030
So it'll be O of one.
265
00:11:15,030 --> 00:11:16,270
And the reason it's constant
266
00:11:16,270 --> 00:11:18,570
is because we're not storing anything extra,
267
00:11:18,570 --> 00:11:21,040
except for maybe a couple of pointers
268
00:11:21,040 --> 00:11:24,040
for our position in the respective arrays.
269
00:11:24,040 --> 00:11:27,440
But we're not storing any other big variables
270
00:11:27,440 --> 00:11:29,350
or big pieces of data
271
00:11:29,350 --> 00:11:32,100
and more specifically we're not storing anything
272
00:11:32,100 --> 00:11:34,120
that is gonna increase in size
273
00:11:34,120 --> 00:11:37,430
with respect to the size of the two inputs.
274
00:11:37,430 --> 00:11:40,380
So with that, let's jump into the code walkthrough
275
00:11:40,380 --> 00:11:42,773
to see what this looks like in code.
276
00:11:43,660 --> 00:11:45,080
All right, so we've got
277
00:11:45,080 --> 00:11:47,860
our validate subsequence function to find.
278
00:11:47,860 --> 00:11:51,140
It takes in two non-empty arrays of integers
279
00:11:51,140 --> 00:11:53,330
where the second array is a potential subsequence
280
00:11:53,330 --> 00:11:55,290
of the first array.
281
00:11:55,290 --> 00:11:58,450
And we're actually gonna cover two code solutions here.
282
00:11:58,450 --> 00:12:01,050
They both have the same overarching logic,
283
00:12:01,050 --> 00:12:02,230
the logic that we covered
284
00:12:02,230 --> 00:12:04,530
in the conceptual overview of this video.
285
00:12:04,530 --> 00:12:07,640
But the first solution is gonna use a while loop
286
00:12:07,640 --> 00:12:10,400
to traverse through both arrays in tandem
287
00:12:10,400 --> 00:12:12,870
and is gonna keep track of the positions
288
00:12:12,870 --> 00:12:14,960
that we're at in both arrays.
289
00:12:14,960 --> 00:12:18,110
Whereas the second solution is gonna use a for loop
290
00:12:18,110 --> 00:12:19,560
to traverse through the main array
291
00:12:19,560 --> 00:12:21,360
and is gonna keep track of our position
292
00:12:21,360 --> 00:12:22,910
only in the second array.
293
00:12:22,910 --> 00:12:24,770
So let's jump into the first solution,
294
00:12:24,770 --> 00:12:26,110
the one with the while loop.
295
00:12:26,110 --> 00:12:27,900
For this solution, like I said,
296
00:12:27,900 --> 00:12:29,080
we're gonna need to keep track
297
00:12:29,080 --> 00:12:30,980
of our position in both arrays.
298
00:12:30,980 --> 00:12:33,580
So we're gonna declare our arrIdx
299
00:12:33,580 --> 00:12:35,810
which is gonna be initialized to zero,
300
00:12:35,810 --> 00:12:38,410
and this is gonna be our position in the main array.
301
00:12:38,410 --> 00:12:40,790
And then we're gonna have our seqIdx,
302
00:12:40,790 --> 00:12:42,560
also initialized to zero,
303
00:12:42,560 --> 00:12:44,870
our position in the sequence array.
304
00:12:44,870 --> 00:12:46,990
And our while loop is basically
305
00:12:46,990 --> 00:12:49,020
gonna perform some operations.
306
00:12:49,020 --> 00:12:51,130
We'll cover the operations in a second.
307
00:12:51,130 --> 00:12:54,560
So long as we are in bounds of both the main array
308
00:12:54,560 --> 00:12:55,890
and the sequence array.
309
00:12:55,890 --> 00:13:00,890
So while our arrIdx is smaller than the length of our array,
310
00:13:01,000 --> 00:13:04,410
and while our seqIdx is smaller
311
00:13:04,410 --> 00:13:06,900
than the length of our sequence,
312
00:13:06,900 --> 00:13:08,600
we're gonna perform some stuff.
313
00:13:08,600 --> 00:13:09,640
What are we gonna perform?
314
00:13:09,640 --> 00:13:10,650
What are we gonna do?
315
00:13:10,650 --> 00:13:13,440
Well, we're looking to see if the element
316
00:13:13,440 --> 00:13:16,210
that we are at in the main array
317
00:13:16,210 --> 00:13:19,500
is equal to the element that we're at in the sequence array.
318
00:13:19,500 --> 00:13:23,350
We're specifically looking to find or to match
319
00:13:23,350 --> 00:13:25,490
the current element in the sequence.
320
00:13:25,490 --> 00:13:29,550
So we're gonna say if our array at arrIdx
321
00:13:29,550 --> 00:13:33,750
is equal to our sequence at seqIdx,
322
00:13:33,750 --> 00:13:36,010
if that's the case then we found
323
00:13:36,010 --> 00:13:38,180
our current element in the sequence
324
00:13:38,180 --> 00:13:40,150
and we're gonna move our position,
325
00:13:40,150 --> 00:13:42,220
the sequence forward by one.
326
00:13:42,220 --> 00:13:45,480
So we're gonna increment our seqIdx by one.
327
00:13:45,480 --> 00:13:49,320
And then regardless of whether this condition is true,
328
00:13:49,320 --> 00:13:51,870
so regardless of whether or not we have a match
329
00:13:51,870 --> 00:13:54,550
between our current number in the main array
330
00:13:54,550 --> 00:13:58,000
and in the sequence array, we're gonna keep moving forward
331
00:13:58,000 --> 00:13:58,980
in the main array.
332
00:13:58,980 --> 00:14:00,750
So regardless of this condition,
333
00:14:00,750 --> 00:14:03,887
we are gonna increment our arrIdx by one.
334
00:14:03,887 --> 00:14:06,150
And that means that we're gonna keep moving along
335
00:14:06,150 --> 00:14:07,240
in the main array.
336
00:14:07,240 --> 00:14:08,600
And in the sequence array,
337
00:14:08,600 --> 00:14:11,650
we'll move along only if we found a match.
338
00:14:11,650 --> 00:14:14,470
Eventually, we're gonna break out of this while loop,
339
00:14:14,470 --> 00:14:17,480
either 'cause we're gonna have traversed the entire sequence
340
00:14:17,480 --> 00:14:18,690
or 'cause we're gonna have traversed
341
00:14:18,690 --> 00:14:20,710
the entire array or both.
342
00:14:20,710 --> 00:14:23,070
And in that case, we're gonna return
343
00:14:23,070 --> 00:14:26,490
whether or not we found a valid subsequence.
344
00:14:26,490 --> 00:14:27,640
How do we know that?
345
00:14:27,640 --> 00:14:31,290
Well, if we've traversed through the entire sequence
346
00:14:31,290 --> 00:14:33,060
by the end of this while loop,
347
00:14:33,060 --> 00:14:35,400
then we found a valid subsequence
348
00:14:35,400 --> 00:14:37,420
'cause that means that we will have hit
349
00:14:37,420 --> 00:14:41,320
and satisfied this if condition here
350
00:14:41,320 --> 00:14:45,000
and the times where N is the length of the sequence.
351
00:14:45,000 --> 00:14:47,400
And therefore we will have matched
352
00:14:47,400 --> 00:14:49,030
all elements in the sequence,
353
00:14:49,030 --> 00:14:51,160
and we will have a valid subsequence.
354
00:14:51,160 --> 00:14:54,070
So we will only have a valid subsequence
355
00:14:54,070 --> 00:14:59,030
if the seqIdx is equal to the length of the sequence.
356
00:14:59,030 --> 00:15:02,260
If we're ever at a point here after this while loop
357
00:15:02,260 --> 00:15:06,680
where the seqIdx is smaller than the length of the sequence,
358
00:15:06,680 --> 00:15:08,480
either we're still at the very beginning
359
00:15:08,480 --> 00:15:10,610
or maybe even we're at the very last element,
360
00:15:10,610 --> 00:15:13,620
maybe we're at length of sequence minus one here.
361
00:15:13,620 --> 00:15:16,170
If that's the case, we clearly didn't find
362
00:15:16,170 --> 00:15:19,300
all of the sequence elements in the main array
363
00:15:19,300 --> 00:15:21,830
and we do not have a valid subsequence.
364
00:15:21,830 --> 00:15:24,400
So here we wanna return seqIdx
365
00:15:24,400 --> 00:15:27,030
is equal to the length of the sequence.
366
00:15:27,030 --> 00:15:29,740
So like I said in the conceptual overview of this video,
367
00:15:29,740 --> 00:15:33,930
this algorithm is gonna run in O of N time
368
00:15:33,930 --> 00:15:37,060
where N is the length of our main array
369
00:15:37,060 --> 00:15:40,140
and it's gonna run in O of one space.
370
00:15:40,140 --> 00:15:42,740
And you can see the space complexity very clearly.
371
00:15:42,740 --> 00:15:46,070
All that we store are these two variables here,
372
00:15:46,070 --> 00:15:49,450
nothing that increases with the size of the inputs.
373
00:15:49,450 --> 00:15:51,750
And as far as the time complexity,
374
00:15:51,750 --> 00:15:54,540
you can see here that we are going
375
00:15:54,540 --> 00:15:58,060
through the entire array with this while loop,
376
00:15:58,060 --> 00:16:00,270
and once we reach the end, we break out of it
377
00:16:00,270 --> 00:16:01,103
and we're done.
378
00:16:01,103 --> 00:16:04,120
We might break early if the sequence is smaller
379
00:16:04,120 --> 00:16:05,220
but we're not sure.
380
00:16:05,220 --> 00:16:07,140
And there are many times when, for instance,
381
00:16:07,140 --> 00:16:09,673
we're not gonna have a valid subsequence
382
00:16:09,673 --> 00:16:12,000
when we're gonna have to go through the end of the array.
383
00:16:12,000 --> 00:16:16,020
So the most accurate way of describing this time complexity
384
00:16:16,020 --> 00:16:19,040
is gonna be O of N where N is the length of the array.
385
00:16:19,040 --> 00:16:22,730
Now on average or in the worst case, it's O of N.
386
00:16:22,730 --> 00:16:25,370
So this is the solution that uses a while loop.
387
00:16:25,370 --> 00:16:27,960
Now let's cover the solution with a for loop.
388
00:16:27,960 --> 00:16:29,170
So we'll copy the code.
389
00:16:29,170 --> 00:16:30,970
Well I guess we'll comment it out first.
390
00:16:30,970 --> 00:16:34,400
We'll copy the code and delete most of it.
391
00:16:34,400 --> 00:16:36,620
The one thing that we'll keep is the seqIdx
392
00:16:36,620 --> 00:16:39,850
initialized to zero 'cause we're still gonna keep track
393
00:16:39,850 --> 00:16:42,960
of our position in the sequence with this pointer
394
00:16:42,960 --> 00:16:46,502
but instead of a while loop with the arrIdx pointer,
395
00:16:46,502 --> 00:16:47,990
we're just gonna do a for loop to the array.
396
00:16:47,990 --> 00:16:51,550
So we'll say for value in our array.
397
00:16:51,550 --> 00:16:54,570
And here we're gonna do a similar check
398
00:16:54,570 --> 00:16:57,600
as we had here on line six with the if statement.
399
00:16:57,600 --> 00:17:01,820
We're gonna say if our sequence at the seqIdx
400
00:17:01,820 --> 00:17:05,880
is equal to our value, then we have a match.
401
00:17:05,880 --> 00:17:08,260
It's the same sort of logic as here.
402
00:17:08,260 --> 00:17:09,750
We have a match and what do we wanna do?
403
00:17:09,750 --> 00:17:12,650
We wanna increase our seqIdx.
404
00:17:12,650 --> 00:17:15,940
We'll say seqIdx plus equal to one.
405
00:17:15,940 --> 00:17:18,560
However, the one thing that we wanna do here
406
00:17:18,560 --> 00:17:20,540
since we don't have our while loop
407
00:17:20,540 --> 00:17:23,490
that's gonna break if we're out of bounds with the sequence,
408
00:17:23,490 --> 00:17:27,850
is we wanna add this condition inside of our for loop.
409
00:17:27,850 --> 00:17:30,610
So before we actually do this if statement here,
410
00:17:30,610 --> 00:17:32,150
which would probably cause an error
411
00:17:32,150 --> 00:17:35,320
'cause we might be accessing something out of bounds,
412
00:17:35,320 --> 00:17:36,523
we wanna have this condition
413
00:17:36,523 --> 00:17:39,850
that is gonna say if our seqIdx is equal
414
00:17:39,850 --> 00:17:44,760
to the length of the sequence here, then we break.
415
00:17:44,760 --> 00:17:46,070
We break out of our for loop.
416
00:17:46,070 --> 00:17:47,980
So we're essentially mimicking
417
00:17:47,980 --> 00:17:50,170
this while loop condition here.
418
00:17:50,170 --> 00:17:52,280
And then if we break out of our for loop,
419
00:17:52,280 --> 00:17:53,760
we just return the same thing,
420
00:17:53,760 --> 00:17:57,330
seqIdx is equal to the length of the sequence.
421
00:17:57,330 --> 00:17:59,330
And of course here you don't even need to break,
422
00:17:59,330 --> 00:18:01,560
you could just return true in this case
423
00:18:01,560 --> 00:18:03,890
because if our seqIdx is equal
424
00:18:03,890 --> 00:18:05,480
to the length of the sequence,
425
00:18:05,480 --> 00:18:07,650
then we've got a valid subsequence.
426
00:18:07,650 --> 00:18:10,840
But we're gonna check this here at the very anyway.
427
00:18:10,840 --> 00:18:12,870
So I just like to break here.
428
00:18:12,870 --> 00:18:13,900
Up to you.
429
00:18:13,900 --> 00:18:16,830
As far as the complexity analysis for this solution,
430
00:18:16,830 --> 00:18:18,500
it's gonna be identical to the first one.
431
00:18:18,500 --> 00:18:20,710
So I'm just gonna go ahead and copy that here.
432
00:18:20,710 --> 00:18:22,010
And the reason it's identical
433
00:18:22,010 --> 00:18:23,700
is because we're doing the same logic.
434
00:18:23,700 --> 00:18:27,750
We're only storing one variable here with our index.
435
00:18:27,750 --> 00:18:29,280
We're iterating through our array here
436
00:18:29,280 --> 00:18:30,960
and keeping track of the value.
437
00:18:30,960 --> 00:18:32,830
We're not storing anything with respect
438
00:18:32,830 --> 00:18:34,930
to the size of the input.
439
00:18:34,930 --> 00:18:36,720
And as far as the time complexity,
440
00:18:36,720 --> 00:18:39,020
we're really just doing a for loop through the array
441
00:18:39,020 --> 00:18:40,530
so it's gonna be O of N time.
442
00:18:40,530 --> 00:18:43,070
We might break early but we don't really know that.
443
00:18:43,070 --> 00:18:44,640
On average or in the worst case,
444
00:18:44,640 --> 00:18:48,230
we won't break early and that's why it's O of N time.
445
00:18:48,230 --> 00:18:51,040
So with that I hope that you found this video informative
446
00:18:51,040 --> 00:18:52,793
and I'll see you in the next one.
33512
Can't find what you're looking for?
Get subtitles in any language from opensubtitles.com, and translate them here.