Hi, everyone.
So in this video, we are going to write the code for this problem number of aliens, basically we need
to write the code for the offense, not defense.
We need to write the code for finding out the number of connected components.
We need to write the code for finding out the number of connected components in the graph.
And DFS algorithm can be used to find out the number of connected components.
Right.
So we just need to maintain one count that how many times I am running the algorithm.
And that will be our answer.
Right, for the algorithm.
But we need we need a visitor, daddy and DFAC, the recursive algorithm.
So it will recursively visit all the elements.
Right.
So let's start writing the code.
So this is great.
OK, so first let's find out how many rules are there that will be grid, not size.
And let's find out how many columns out there that will be great of zero that size.
Now, what we need, we need a visionary also, so this visit is that it will be a total matrix, right?
So initially, what I'm going to do is I will create one visited Eddie, I will create one visited Eddie.
I mean, to reiterate, and initially, no one is arrested, so I will initialize all the value to false
light so all these values will be initialized or Tuvalu's because I have not listed any element yet.
So let's do that.
So we need to revisit it today and it will be of type.
All right.
So that predictable.
And I visited.
So how many rooms are there, M plus three Ambrosial with their great criticizes, eminent, so Amaru's
will be there and we need to initialize.
All the values would follow.
So how many columns and columns and we need to initialize all the elements with files.
So this is this index, right?
This is this index for doing this.
So this is this index, so what I'm doing, I am creating one vector, this vector is of size and so
Ambros will be there, Ambros will be there and distractor, what does it contains?
It contains a vector of bull and disprovable is of size n and initialized with false.
So this vector is of size and.
His office says any and all the values are initialized with files, all the values are initialized with
files.
So that is what we need to do right now.
What we need to do, we need to iterate over this data with this great array.
And if it is one and not visited, then start the offense.
Right.
So our answer will be our answer is how many times we are calling DFS algorithm.
So countercurrent will be our answer.
Initially, the count zero and our answer will be count how many times we will call the algorithm.
Now, what we need to do, we need to hydrate over the Eddie.
So let's hydrate equals zero iList and am I plus.
Plus.
Forint J equals zero, G, Leiston and G plus plus what you need to do if the current element.
So if greed of AIG, if the current element is basically one, if the current element is one where they
need to do, you will call the algorithm, right?
You will call the algorithm what they have.
Gardam will take it will take has input.
It will take the index I and the current index, and it will take a visitor that remember the algorithm
used to take visitor, that is input.
And what else do we need to do since we are running the DFS algorithm.
So we need to do account plus plus rate.
We are doing we are running the official gardam.
So we need to do count plus.
Plus no one thing is missing here.
What else do we need to do?
So let me clear the screen first.
Let's talk about this example.
Right.
So what we need to do, I am I reading all this greenery and I will start from this element, right.
But if it is when you will start DFS, but you also need to check whether this element is visited or
not.
Right.
So here we should write one more condition that the current element has not been visited.
Then only you will start DFS from that element late.
For example, this is one.
So when you will start DFS from this element, what this element will do, it will visit these four
elements so that your next element will be one.
And if it is one, you will start DFS again.
But that is wrong, right?
So you should have one more, Jacare, that the current element has not been visited.
Right.
So we need to have one more check before calling the DFS from this element that the current element
should not be visited.
So if visited of IJI is false.
So if the current element has not been visited, then only you will start DFS from the current element.
Right.
So now our goal is really the only thing that is missing is we need to write the code for the DFS function,
which is going to be a recursive function.
So where does this DFS function will return, it will not add anything, it will just visit all the
elements and what it is taking it is taking graphics input.
So let's take the graph vector vector character.
And this is our graph grid, right?
It is taking the index, Anji.
And it is also taking I've visited at as input rate.
So this visit today is to the Eddie.
And visited, so one important thing is basically this visitor that should be passed Bio-Reference,
this visitor that should be passed by the fence, because what we are going to do is we are going to
change this reality.
So that changes should be reflected here.
Also made so you will not pass by value, you will pass by reference, because the whatever changes
we are doing in this function that changes should reflect in main function also.
So you need to pass Bio-Reference and that is very important.
Otherwise your algorithm will not run.
It will give you wrong output.
So it has to be Bio-Reference.
Now, this is going to be a recursive algorithm, so very simple, simple based guesses, right?
If I is less than zero indexes invalid, you are just basically less than zero invalid index or the
value of AI is basically greater than or close to your griddled size.
Again, invalid index.
Or Jay is basically bigger than our to grade of zero dark size again in the next.
So these are all invalidly next.
And when we will get invalided, index, what we will do, we will simply return.
Do not do anything Sembler written because the index is invalid.
Right?
Simple because other simple baskets can be if the current element is basically zero, if the current
element is water.
So if the current element is water, what will will simply return.
Right.
Similarly, another base case can be if the current element is already visited.
So if we started off IGY is already true.
We have already visited this element in that case.
Also where they are going to do is you done right.
So simple, simple cases because this is going to be a recursive algorithm.
So now let's actually write the code for the first.
So I'm standing at the current parliament, right, I am standing at current elements, so I am standing
here.
So what I'm going to do is I will mogg this element as visited.
So what to do since I am standing at the next AMG and this index is valid and this index is containing
element one that this land and this index has not been visited before.
So this element has not been visited before and now I am visiting this element.
So I will mark this as proof.
Right.
I will mark this as true.
And since we are changing the mystery value, that's why we need to take Bio-Reference, because the
changes must be reflected here in this function also.
And then what we need to do so from a given index.
From a given index.
Right.
From a given index.
What you can do, you can move in either directions, we can move in either directions.
So what we will do, we will call DFS, we will call the function DFS in all the other directions,
call DFS, function in all eight directions.
Right.
So let's do that.
We need to call the DFS function on all eight Badakshan.
So the efface.
This is a recursive algorithm.
We already know this will take graph as input.
This will take the first let's say I minus one and G minus one and it will take with Gianetti Farshad.
Right.
So let's copy this and there are eight directions possible, so let's paste them.
So this is one, two, three, four, five, six, seven and eight, yes, so total eight directions.
And now let us change the values, so I am minus and minus, and the second can be a minus, one energy
tower can be a minus one energy plus one for the addiction can be, I think, minus one.
Which direction can be I and J plus one?
Sixth medication can be a plus one and G minus one, correct, next direction can be lifted.
This is G and this is a plus one and let's say the last election is a plus one and G plus one.
So D let me give some spaces between them.
So these are total eight possible actions, right?
So from a given element, I will call DFS on all eight possible directions.
And that will be the entity called.
Right, so this will be the entire record.
Let me give space's here.
Yep, and let's also make sure that in line.
So, yeah, this will be total eight possible directions, right?
So this is the complete code.
Let's our current annual summit.
So we are getting some compilation error.
Did you mean.
OK, so spelling mistake, this will be size.
Yep, our code is working right now.
OK, so we are getting a wrong answer.
Let's see what we did wrong.
OK, so let's see, what is this?
So this is we have one one zero zero zero, then again, one one zero zero zero, then zero zero one
zero zero and then zero zero zero one one.
So this is the graph.
And yeah, the expected output is correct.
This is one connected component.
This is another connected component.
And this is another connected component.
So the expected output is correct and our goal is giving the output as one.
So our goal is giving wrong output and why it is.
So let's try to analyze what we did wrong here.
Hi, everyone.
So I have figured out actually why our goal was failing.
So let me try to submit this quote again and let's see.
So see, this is the input which is given to us.
The input is one one zero zero one zero, then one one zero zero zero.
Then I have zero zero one zero zero, then zero zero zero one and one.
So what my goal is returning.
So what I am doing, I am moving in two directions.
Right.
If you will move in each direction.
So that means you can move diagonally also.
Right.
So I can move diagonally and I can reach here.
Similarly, I can move diagonally and I can reach here.
So what my goal is doing, I am moving in eight directions.
So my goal is combining all these right.
My goal is combining all this.
And that's why my goal is retaining that output is when there is only one connected component.
So that's why the goal is returning one.
But if you will see the actual quotient description in that question, it has mentioned that you can
either move horizontally automatically.
Right.
It is mentioned that you can move in four directions.
So it was like pretty silly mistake from my side.
Actually, I saw only one question before solving this.
So in that question, I was able to move in a direction.
So that's why I missed out here.
And like, I paused the video for some time and I tried debugging a lot.
And then when I was not able to find the solution, then I read the description again.
And then I was able to figure out that you can move only in four directions.
So if you will move in for direction, what will happen?
You will not be able to reach this right.
You will not be able to reach at this one.
So you will finish here similarly.
Then you will finish it because you will not be able to move diagonally and this will be another connected
component.
So instead of moving in a direction, we need to modify our code to move only in four direction.
So that was the error that we did.
It was a pretty silly mistake from my side.
Right.
So here you can see it.
You can see for yourself that the question is asking us to move only horizontally or vertically Direxion
and not diagonal direction.
So I am so sorry, guys.
That's why you should read the question very carefully before jumping to the code.
So since we can move on in four direction, let's remove this line.
Which else I think we need to remove this line also.
We need to remove this line.
And we need to remove this line, so I have removed all the four directional directions right now.
This is correct.
Now I will call Vilborg.
So now we are getting a time limit exceeded.
Yeah, very good.
Let's see how many test case our court is passing.
So our goal, the past 47 days, cases out of 48,
so basically we are getting time limited exited.
So let's try to find out what is the time complexity of our code and then we will see how we can reduce
the time complexity.
So let's discuss the time complexity so that we can reduce our time complexity.
So what is the time complexity of how according to our time complexities and I mean because we are iterating
right Ambrosiano in columns so that when the time complexities Emman and we are going to each and every
element only once.
Right.
We are visiting the element only once since we are visiting each and every element only once.
So that's why the time complexities Eman and regarding the space complexity.
So we have created this visibility.
So space complexities.
Emman, right.
So this is the time and the space complexity.
And even after this time, complexity, I am getting time limited exited.
So that means there is not a problem with our logic.
There is some different problem and what this different problem is.
So here what they are doing, you are pressing the greenery, right.
And you are passing by value.
So by value, what will happen for this function?
This grid array will be created and all the values will be copied.
Right.
So that will take time.
So what I am trying to say here is this grid array.
We are passing this great array by value and when we pass by value, so what will happen?
This function will create one local variable grid and it will copy all the data.
It will copy all the data.
So that is time consuming, right?
That will take time.
So what we will do, instead of taking by value, if we will take it by reference, then we will not
have a time limit extended, because if you take by definition, then we will not copy the data.
We will just refer to the data that is present here.
So what we are going to do is instead of taking great away by volume, we will take great Bio-Reference
so that we will avoid the time that we are using in copying the data.
Now, if we will submit now, Gore will work.
Right, so now our court is working.
OK, so this was the catch, a great idea by the fence to reduce your time complexity, to save the
time that you are using in copying the data.
So this is it from this device.
If you have any doubt to ask me, I will see you in the next one.
Thank you.