What's up, guys?
Andy, here we are living together into day, free of the from zero to hero challenge.
And I've prepared for you.
An awesome problem which actually has a smart solution, which uses my favorite ever data structures.
A very simple one, but super powerful.
First of all, if you really like this Vidor's and want more, make sure to stay in tune by clicking
the subscribe button.
Make sure your like the videos and support this, Jenna.
Your job is to make it happen.
As always, my job is to make it awesome.
So let us read the statement together.
The problem is called one free two pattern.
And given a sequence of N integers.
A1, a2.
Dot, dot.
Dot.
And what is the one free to better?
A one free two pattern is a subsequence A.I., A.J. and AK.
Right.
So free numbers from the array where I is less than G.
J.
There's a K and a of AI is less than A of K which is less than a of J.
Right.
So the first number eight is the smallest one.
Then the second smallest number is a K.
Right.
And that the biggest number from this free is the second one.
That's why one free to factor.
Right.
So design an algorithm that takes the list of our numbers as input and checks, whether there is a one
free two pattern in the list.
Also, let's just open our notepad, as always.
And take the first example.
So example number one is one, two, three, four.
Right.
So obvious we don't have free numbers to satisfy that because the array is increasing disorder, but
not for free.
One for two, we should return.
True.
Because the one free true pattern.
What is it.
Is free for two or one.
Four two.
Right.
This is good.
So free for two or maybe one for two.
Right.
The first element is the smallest one then is the third one.
Right.
Is the second smallest one.
And then the second one from this is the biggest one.
So.
Let's start thinking about this problem.
And as always, guys.
You probably if you watched my last videos, you probably got used to it.
We always start by brute force approaches.
Right.
So I want the worst brute force approach ever.
And that is Biegel of MQ Starbase brute force number one.
Right.
Brute force number one, which is Bigo of and cute.
What shall I do?
I should fix each number.
Right.
So make a for loop four.
I make another for loop for J.
Make another four.
Loop for K.
Right.
So fix each of those.
Fix I fix.
Jake fix king.
Check if they are valid.
So I use less than a half ks less than a day.
If it is return.
True.
If not, continue checking.
In the end, if you haven't find a solution, you are a mystery to enforce.
So.
All right.
This is super simple.
Let's try to find another brute force, which now to be M squared.
So brute force.
Number two, I want something in Bigo of Arms Sweat.
And let's be smart about that, right?
For Biegel of any cube.
We could fix all those free positions.
I J and K now for Begal of M squared.
We won't fix all the free of them.
We are going to fix only two of them.
And which ones should we fix.
Well.
I don't think it matters at all.
So I am going to fix, let's say, fix or changing.
Right.
So the last two of them.
Right when I fixed K.
Right.
So it's actually gently.
This is your right.
So fixing janky and I should check.
If so, check if ACA is less than aging.
First of all.
Right.
And if it is, I should find the missing eye.
And what should I do?
I should see if there is an eye which is less than G.
Such as.
So check if there is some eye.
Right.
Which is less than G.
Right.
And what should be the property of a right.
Obviously it's less than achy.
So and a I it's less than 80.
But how should I check this.
I should take this in.
Konstantine writes on Bigo of one.
So I want you to imagine right now we have fixed J and K.
Right.
And we have seen that A of J.
Is bigger than JFK.
And now what we want here is to find some eye less than G.
Such as a Y is less than a of key.
So.
The question is, do I have an element from position one to position Jay minus one?
Which has a value less than some given value, which is obviously AK.
So if I have to try to find an element from some range less than other value.
The perfect candidate for that is going to be the minimum element from that range.
Right.
So doesn't make any sense to take the greatest element from position one to position Jay minus one.
When I can check the smallest one, because the smallest one has the higher odds to be less than AFIK.
So this is Mark, right?
So what I should basically do in order to check this in Konstantine is that I should know the minimum
value from some prefix.
Very quick.
And how do we know some value very quick in Bigo of one?
Exactly.
Pre computing it.
So we shall have another.
We shall have, let's say, mean value.
Right.
We should have an auxiliary array, which is mean value.
Which is going to have the minimum.
The minimum value.
Right.
B to in.
The minimal barrier between a one, a two that are that a right?
So the value of this preface.
Now, if I could disagree, which is obviously linear time to pre compute, right?
It's like the partial sums, but it's basic, you know, a partial minimum.
After I can do this great, I will know my information in constant time, which is awesome, right?
So.
Meanwell of life is basically the minimum between minivan of minus one.
So the minimum between the first minus one element and now my current element, which is eight.
Right.
All of this in a Ford Loop.
So Ford is going to be from position one, let's say, all the way to position.
And plus plus I would have the minivan after computing its other three, computing the minivan I should
fix.
Jay and Kate, we've tested for loops and I should check if A of Kate is less than A.J. and most important,
the minivan of J minus one.
His heart is less than a game.
And if it is, we should return to right away, if not after executing these two nested for loops.
We know that we won't have a solution.
So return false.
Perfect.
So this is the second brute force approach.
B, go off and square.
Now let's dive into the optimal solution, which is linear time.
Right.
So optimal solution is going to be pretty amazing, actually.
Is of.
And so I want you to post this video right now and think about the optimal solution, because obviously
we didn't we haven't gone through this brute force approaches because they are useless.
Right.
So the brute force approach number two will help.
You will be the foundation to find your optimal solution.
Post the video and think about it.
Perfect eyes.
I hope as many as you can.
The optimal solution, right?
It's not an easy one.
It's quite tricky, but it's super awesome.
And we are going to dive into my favorite data structure, which is the most basic one.
The stack.
This problem is going to use the stack to be solved.
But now this is my end.
If you want to think again of the problem, knowing that it's solved this stack, Bill, I guess.
And we are going to take this step by step.
So individual support number two, we have fixed J and K and found that our favorite, a the most favorable
candidate is the minimum value from the prefix from position one to do minus one.
Right.
Right now for Biegel of am I not able anymore to fix J.
K.
So I should fix only one of those.
And I am going to share with you a super powerful trick which is used in 99 percent of these kinds of
problem.
When you have to find or fix free pointers, I, j and K, right.
But because of the time complexity, you could only fix one of those.
You always fix them.
Middle one.
Right.
So it is the most useful to fix G.
So I am making a for loop for only fixing G.
Now let's take a look again at the brute force approach number two.
And remember that when we fixed J and K, we know that I write that minimum value.
That's our I.
D still false.
Now I don't know the k k could be everything between J plus one an N, but I still the most favorable
I is going to be the minimum element from the prefix.
So I fix the J.
I know.
What is the I write.
So I is the position of a minivan basically of J minus one.
Right.
And now I should find if there is a K.
So we should check in Konstantine if.
There is some key such buzz.
Well, first of all.
Often we find Mike.
I should check if I mgd our venue.
Right.
So obviously what we know here is that AIG should be less than AIG.
Right.
So first of all, reject this check.
Give.
Right.
And if this holds perfect, we should go on and find the key.
If there is one.
So check if there is some key.
Such as.
This case should be between these venues, right?
So this case should be less than A.J..
But should be greater than a.
Well, remember that I have fixed my jeep and they know my AOF, right?
Right.
So when I fix my jeep.
That is the maximum value between this free and.
He of K should be less than this and greater than a of all.
So eight of K.
Should be what is the, let's say, most favorable element?
Right from the position J plus one to the position M.
Which could hold this.
What is the maximum value?
Which is less than a of J.
Right.
So it should be less than a J.
But in order to be greater than a of I.
The best candidate is the maximum vote.
So EFCA should be the maximum value from this range or from the range from J plus one all the way to
position N, right.
Which is less than a J.
And that's perfect.
Is that what we want?
We want to find out if there is some key.
Right.
Again, the maximum value from Geep US one, an end, which is less than a of G.
So we need to find this value really quick.
In Bigo of one.
Now what is the difference between this and what we had to find a brute force approach.
Number two in the brute force approach.
Number two, we had to find the minimum value from some prefix.
Right now we have to find the maximum value from some suffix.
Right.
Because it's from some position all the way to end to the end of the array.
But the maximum value, which is less than some given value.
So it's not enough just to compute a personal maximum or suffixes or something like that.
We need something stronger and that something stronger is the step.
Right.
And how will we use the stack?
Well, we will go with our G.
We are going to iterate from the end of the array all the way to the beginning.
And why is that?
Because when we are at some G, we will have already iterate through the elements on his right, which
are our possible maximum value, our possible case.
Right.
So I am going to go if this G.
Starting from position and all the way to position one in G minus minus.
And here we have actually two possibilities because we could ever use a set.
Right.
Remember what is a set I said is a collection which stores our elements increasingly or decreasing the
sorting.
So if we store a set here.
We basically have iterated for all the elements between J plus one position, give us one and M we basically
added each element in our set, right?
So when iterating for an element, inserting it into our set, the city's increasingly sorted.
And we can perform lower and upper bound on this set.
So we have the lower and upper bound.
We can binary search basically the first greater element or the last less or equal element from that
set.
Which is perfect because solves our problem.
Right.
The maximum value, which is less than a.
Which is less than a G.
So if our set is increasingly sorted and we perform the lower bound on eight of G.
And then we decrement one time that iterator, we are going to have the maximum value, which is strictly
less than a G.
So a possible solution.
Basically I can write here O brute force approach.
Right.
So this is it's not actually brute force approach because it's super good in time.
But just for the fun of it, let's say it's a brute force approach between because we are better than
that.
Right.
So in Biegel of Ms.
Logan.
Right.
Using a set.
We have this for brute force approach.
Not.
The beauty of this solution of the bigo of an optimal solution is that we can get rid of the set to
using the stick and follow me.
As you might know, if you have some experience with sex when using the stick, we will basically have
some elements into the stack sorted, either increasingly or decreasing.
Right.
So what should be the order of our elements in our stack here?
Well, we need all the elements which are of less than a of G.
So when we are at some element, I need to eat a rate in my stack.
All the elements less than me.
So we are going to have a stacked non increasingly sort of right.
Mawn increasingly or buy new shoes.
Good.
Sorted.
Right.
Because if we have our in on increasingly sorted.
All right.
Let's suppose it's then six, five, two or three free again.
And one when we have some value, let's say when we are at the step, AIG equals seven.
We are iterating from the top of the stack.
Right.
Always we are taking element from the top of the stack.
And those elements are going to be less than my seven.
If it was increasingly sorted, I would have started with the maximum.
So I wouldn't cover my less elements right from the stack.
So we are keeping a stack which is sorted decreasingly or non increasingly.
Right.
And each time we are in some position G and we want to insert that element in our stack.
First of all, in order to maintain this stack in the non increasingly sorted order, we have to get
rid of those elements from the top, which are less than my value.
So we are basically iterating for all the elements.
Less than me.
We are going to try out each of these elements, right?
So we are going to encounter at some point the maximum right from that state, which is awesome.
And we are going to pop those from the state and then add my element.
So here I will have one free, free five and six.
Try each of those to be my possible key.
If one of them is so it's basically I know that it's no less than A.J. I should check if these elements
are greater than eight, if I find one return true.
If not, I would just continue my algorithm.
These elements are now gone from my stack and I add my seven and continue the algorithm right now.
Why is the complexity of this big, all of em?
Because you should know this.
You must think.
Of course, at some point we are going to remove more than one element.
Right.
So you might think that, oh, this thing isn't bigger event squared because we have N elements.
And for each element before inserting it to the stake, we are popping a lot of elements.
And it's not because there's some stake, if you think about it.
Each element is inserted and popped from the stake exactly once.
And we have in our array and elements.
Right.
So an alliance crossed two operations, one insertion and one removal is big off.
That makes us not.
We have the optimal solution.
Let's jump into lead code and write the code for it.
By the way, that code is an amazing platform, the perfect plan for preparing for technical endeavors.
Right.
So make sure you check it out.
Not for implementing this.
We have an argument, which is a vector of integer numbers.
And I am going to use my stack.
So stack of integers as team, let's say in this deck.
I'm not going to hold my elements right there.
Values.
I'm going to fold positions.
Right.
So basically here is the boysie shots of my Norn increasingly sorted elements and elements.
Right.
Perfect.
Not the main for loop, which we said is going to be for the G.
So we've the G starting that position.
So we are here in nums.
All right.
First things first.
We should compute that mean event array.
Right.
This is super important.
So for the sake of this example, I am even going to use the vectors because is the way to do it.
So vector of integer max not its meaning then.
Right.
We are computing minimum's so mean Val of.
First of all let's take into one variable the size of the nums vector.
So M equals nums dot sight.
Right now we have the size of the of these vector nums.
And after getting the size we are going to compute the minivan.
So let's just define it.
Meanwhile is going to be an array consisting of M elements.
Right.
And each of those I don't know.
They don't have initially some value.
Right.
So this is basically a constructor right here with this N.
I am constructing a vector of integers, which has initially already N elements.
Right.
Perfect.
Now let's compute the mean event vector.
And first of all, the mean Val one position zero is going to be the element of position zero from us.
So I mean Val of zero Islams.
Then I will make a for loop starting a position one less than N.
Right.
Because vectors are zero indexed superimportant plus plus and mean val of eyes is going to be the minimum
in between mean value by minus one and nums.
OK.
Right.
Perfect.
Now we have this means that it's time to write our made for loop and I am iterating from the last element
which here is at minus one all the way to position one.
Right.
Because James the second one.
So I can go to position zero and J minus minus.
So I know the J.
Now I know the value of A.I. because A.I. is always going to be mean van of J.
Minus one.
And I shall find my most favorable.
Which I will find it in the stack.
But first of all, steak is not increasingly.
I need to push these elements right.
Each element of the array will be inserted to the steak at some point.
So I need to be certain of this element.
But in order to keep it non increasingly sorted, I need to pop those elements from the stack which
are less than me.
So while the steak is not empty.
So not steak that empty.
And I will go to steak that Bob.
Remember, here I have positions, not values.
So for the value, I shall look at nums of stacked up top.
And while this value is hope is less than my value.
Nums of G.
Right.
What should I do?
Well, first of all.
This could be a possible key.
So I shall check if nams of those to the top.
So this aof key is how greater than a of I.
Right.
So if this is greater than my aof I, which I know is mean then of G minus one.
Right.
Perfect.
I returned to write to me.
I have found my solution.
If not, what should I do?
I remove that position from my stick.
Perfect.
Not after this.
When it finishes execution, I will insert my element in my state.
So stick that push.
Remember, those are positions.
So I insert here, Jake.
Not a not none of G.
Right.
So I have basically I have basically all that I need.
So after this for loop finishes execution, let me fall right here.
I should just return false.
Right.
So fix the second element, which is J.
We know what's the first element and we try it from the stake of the possible fourth element in the
end.
We just return false.
And that's it.
Let's run the code.
Fingers crossed.
Ron Paul, the result?
Let's see.
All right.
Passes the test cases.
And now let's submit our solution.
Fingers crossed again.
I've already solved this task.
Two months ago.
All right.
And I have a runtime error.
All this is a corner case.
Be very careful.
In interviews, you will have you will be asked a lot of corner cases.
Right.
So the interviewer will ask you, okay.
Think about some corner cases where you think your algorithm would crash right or won't work, won't
give the right answer.
And you should be very careful on this one.
One of these is always the empty array.
Right.
Very popular.
And it got almost every problem has its corner case.
So how do we check this?
Well, if nonstop, empty.
If this area is empty.
What shall I return?
I return false.
Right away.
Because obviously I won't have a solution.
So let's submit this again.
Fingers crossed again.
Hope for the best.
And we are accepted, right?
Perfect ice.
This was the problem.
First problem that we have solved using the stack.
And there are yet more to come.
And notice how beautiful this is because we had free brute force approaches.
Right.
And cube and square then and again, which is still a brute force approach.
And then getting to the stack in the linear time solution.
Remember, guys, if you really like the content and enjoy seeing me approaching this problems, working
you from my thinking process and writing the code together with me.
Don't forget to really, really support the general hit that subscribe button.
Hit the like button.
Share it with your friends and everyone, which would really find it valuable.
And as always, guys, I will see you in day four.
Keep the hustle and out.