Hello, everyone.
So in this video, we'll be writing the code for the unique problem as discussed in our last video.
So what is America's evolution?
It is very simple.
DPF idea will be deep off.
I might some Komachi plus deep off I and J minus one.
And what will be our answer?
Our answer will be DPF M minus one and and minus one.
And what is 80 present.
What DPF.
I do represent it represent Namaroff unique possible part to reach index icon magic.
And this will be our answer.
Simple right now let's start writing the code for this problem.
So they need to do we need to create one.
So let's create a debris Amaru's.
And Gollum's.
Now, what we need to do so.
Let's discuss what will be the best case to see if this is your deputy.
Or let's say this is your McCrossin grid, if you want to reach this is your starting, if you want
to reach this index or this index or this index or this index, how many possible ways will be there?
So the answer is when there's only one unique possible path to reach index, this one, this one, this
one or this one.
Why?
Because you can only move in the right direction.
So far, reaching this particular index, what do you do?
You will move in this direction only.
So there will be only one unique path.
Similarly for this index, you can only move in this direction.
So there is only one unique index, one unique battery.
And similarly for this index, you can move only in this direction.
So there will be only one unique part.
And similarly for this, you will move in this direction.
So there will be one unique path.
So basically you're depressed how your depression look like.
So all these values.
So all these values will be one.
Right, you are you are standing here, and if you want to reach any of this, it makes the only possible
way is you will move down.
So there is only one unique possible path, similarly to reach any of these indexes.
The only possible ways you will move in the right hand side and this and that will be only one unique
part.
Right.
So we will initialize our deprave with all the ones in the first column and basically all the one in
the first row.
So this is first row and this is first column.
So basically zero through and as you read column.
So we need to initialize with all the ones here and all the ones here.
So let's do that.
So let's start writing the code, so what we need to do, let's initialize our DP at the best case.
So I equals zero, I then am I plus plus.
DP of I.
And zero will be when.
Similarly, we will do the same.
So and let's take J.
J equals zero G and then and G plus plus.
And BP of Zero and G will be one fine now our best guess is right now what we need to do, we need to
utilize this reconciliation.
So let's do that.
Let's fill our Deepti.
So I would start from when obviously I lost then.
Am I placeless?
Now for column so J equals one J less than N j plus plus and what will be our DP of IJI?
So DP of IJA will be nothing but DP of a minus one plus G.
Plus, deep of I and J minus one, and finally, when we come out of the for loop, our DPRK will be
completely filled and our answer will be DPE of M minus one and and minus one.
That's so simple, gold, and this is the entire gold.
Now let's celebrate our gold.
So basically, our goal is working fine.
So our goal past all the test cases now let's discuss what is the time, complexity and the space complexity
for this problem so that time complexity is basically big off M Cross.
And and what is the space?
Complexity?
Space complexity is also M Cross and you are creating a deep of size across.
And so that is your space complexity.
And basically this loop is contributing towards your time complexity.
So now the challenge is basically what I have seen is one of my friend was given this question in an
interview, so he solved the problem using this approach.
But the interviewer asked him, can you do better?
Can you reduce time or space complexity?
So your challenges, can you reduce the time, complexity and space complexity for this problem?
So I will discuss the solution, I will discuss this next with you, but you should give it a try.
Give it a try.
You will be able to reduce the time and the space complexity answer is basically you need to use maths
and maths yesterday about permutation combination.
So we will we are going to use that logic only to reduce the time and space complexity.
So try to do this yourself, and if you are not able to do this yourself, then watch the next video.
OK, so I will see you in the next one.
Bye bye.