1 00:00:01,260 --> 00:00:02,020 Hi, everyone. 2 00:00:02,040 --> 00:00:06,990 So in this video, we are going to write the code for this problem number of aliens, basically we need 3 00:00:06,990 --> 00:00:09,640 to write the code for the offense, not defense. 4 00:00:09,660 --> 00:00:12,930 We need to write the code for finding out the number of connected components. 5 00:00:14,620 --> 00:00:19,320 We need to write the code for finding out the number of connected components in the graph. 6 00:00:19,830 --> 00:00:24,090 And DFS algorithm can be used to find out the number of connected components. 7 00:00:24,600 --> 00:00:24,930 Right. 8 00:00:25,170 --> 00:00:30,660 So we just need to maintain one count that how many times I am running the algorithm. 9 00:00:30,660 --> 00:00:31,950 And that will be our answer. 10 00:00:33,360 --> 00:00:34,980 Right, for the algorithm. 11 00:00:35,100 --> 00:00:39,900 But we need we need a visitor, daddy and DFAC, the recursive algorithm. 12 00:00:39,900 --> 00:00:44,430 So it will recursively visit all the elements. 13 00:00:44,790 --> 00:00:45,180 Right. 14 00:00:45,840 --> 00:00:47,780 So let's start writing the code. 15 00:00:49,200 --> 00:00:50,690 So this is great. 16 00:00:50,850 --> 00:00:57,600 OK, so first let's find out how many rules are there that will be grid, not size. 17 00:01:03,820 --> 00:01:09,640 And let's find out how many columns out there that will be great of zero that size. 18 00:01:14,170 --> 00:01:22,120 Now, what we need, we need a visionary also, so this visit is that it will be a total matrix, right? 19 00:01:22,390 --> 00:01:28,960 So initially, what I'm going to do is I will create one visited Eddie, I will create one visited Eddie. 20 00:01:32,390 --> 00:01:39,200 I mean, to reiterate, and initially, no one is arrested, so I will initialize all the value to false 21 00:01:40,180 --> 00:01:46,270 light so all these values will be initialized or Tuvalu's because I have not listed any element yet. 22 00:01:46,820 --> 00:01:48,100 So let's do that. 23 00:01:49,010 --> 00:01:53,930 So we need to revisit it today and it will be of type. 24 00:01:53,990 --> 00:01:54,620 All right. 25 00:01:57,230 --> 00:01:58,700 So that predictable. 26 00:02:02,250 --> 00:02:03,300 And I visited. 27 00:02:06,020 --> 00:02:15,320 So how many rooms are there, M plus three Ambrosial with their great criticizes, eminent, so Amaru's 28 00:02:15,320 --> 00:02:20,000 will be there and we need to initialize. 29 00:02:23,830 --> 00:02:25,480 All the values would follow. 30 00:02:25,540 --> 00:02:30,830 So how many columns and columns and we need to initialize all the elements with files. 31 00:02:31,780 --> 00:02:33,370 So this is this index, right? 32 00:02:34,510 --> 00:02:36,280 This is this index for doing this. 33 00:02:39,500 --> 00:02:46,850 So this is this index, so what I'm doing, I am creating one vector, this vector is of size and so 34 00:02:46,850 --> 00:02:53,040 Ambros will be there, Ambros will be there and distractor, what does it contains? 35 00:02:53,060 --> 00:02:58,790 It contains a vector of bull and disprovable is of size n and initialized with false. 36 00:02:59,150 --> 00:03:01,220 So this vector is of size and. 37 00:03:03,710 --> 00:03:11,000 His office says any and all the values are initialized with files, all the values are initialized with 38 00:03:11,000 --> 00:03:11,460 files. 39 00:03:11,960 --> 00:03:15,650 So that is what we need to do right now. 40 00:03:15,650 --> 00:03:20,930 What we need to do, we need to iterate over this data with this great array. 41 00:03:21,170 --> 00:03:25,430 And if it is one and not visited, then start the offense. 42 00:03:26,330 --> 00:03:26,720 Right. 43 00:03:28,220 --> 00:03:36,730 So our answer will be our answer is how many times we are calling DFS algorithm. 44 00:03:37,040 --> 00:03:39,000 So countercurrent will be our answer. 45 00:03:39,020 --> 00:03:45,320 Initially, the count zero and our answer will be count how many times we will call the algorithm. 46 00:03:46,520 --> 00:03:49,700 Now, what we need to do, we need to hydrate over the Eddie. 47 00:03:50,390 --> 00:03:55,060 So let's hydrate equals zero iList and am I plus. 48 00:03:55,070 --> 00:03:55,520 Plus. 49 00:03:58,980 --> 00:04:09,300 Forint J equals zero, G, Leiston and G plus plus what you need to do if the current element. 50 00:04:11,330 --> 00:04:20,540 So if greed of AIG, if the current element is basically one, if the current element is one where they 51 00:04:20,540 --> 00:04:24,710 need to do, you will call the algorithm, right? 52 00:04:25,010 --> 00:04:26,970 You will call the algorithm what they have. 53 00:04:27,270 --> 00:04:29,480 Gardam will take it will take has input. 54 00:04:29,760 --> 00:04:37,670 It will take the index I and the current index, and it will take a visitor that remember the algorithm 55 00:04:37,670 --> 00:04:39,440 used to take visitor, that is input. 56 00:04:40,760 --> 00:04:45,280 And what else do we need to do since we are running the DFS algorithm. 57 00:04:45,620 --> 00:04:49,250 So we need to do account plus plus rate. 58 00:04:49,550 --> 00:04:51,680 We are doing we are running the official gardam. 59 00:04:51,680 --> 00:04:53,350 So we need to do count plus. 60 00:04:53,360 --> 00:04:56,060 Plus no one thing is missing here. 61 00:04:56,510 --> 00:04:57,630 What else do we need to do? 62 00:04:58,400 --> 00:05:00,230 So let me clear the screen first. 63 00:05:02,150 --> 00:05:03,920 Let's talk about this example. 64 00:05:04,160 --> 00:05:04,670 Right. 65 00:05:06,530 --> 00:05:14,050 So what we need to do, I am I reading all this greenery and I will start from this element, right. 66 00:05:14,690 --> 00:05:21,200 But if it is when you will start DFS, but you also need to check whether this element is visited or 67 00:05:21,200 --> 00:05:21,500 not. 68 00:05:22,190 --> 00:05:22,580 Right. 69 00:05:22,820 --> 00:05:27,590 So here we should write one more condition that the current element has not been visited. 70 00:05:27,890 --> 00:05:32,080 Then only you will start DFS from that element late. 71 00:05:32,210 --> 00:05:33,380 For example, this is one. 72 00:05:34,720 --> 00:05:39,980 So when you will start DFS from this element, what this element will do, it will visit these four 73 00:05:39,980 --> 00:05:42,800 elements so that your next element will be one. 74 00:05:42,980 --> 00:05:45,490 And if it is one, you will start DFS again. 75 00:05:45,500 --> 00:05:46,970 But that is wrong, right? 76 00:05:47,150 --> 00:05:51,590 So you should have one more, Jacare, that the current element has not been visited. 77 00:05:53,330 --> 00:05:53,770 Right. 78 00:05:55,990 --> 00:06:03,760 So we need to have one more check before calling the DFS from this element that the current element 79 00:06:03,760 --> 00:06:04,890 should not be visited. 80 00:06:05,590 --> 00:06:12,260 So if visited of IJI is false. 81 00:06:13,270 --> 00:06:19,910 So if the current element has not been visited, then only you will start DFS from the current element. 82 00:06:21,570 --> 00:06:22,000 Right. 83 00:06:23,430 --> 00:06:29,550 So now our goal is really the only thing that is missing is we need to write the code for the DFS function, 84 00:06:29,550 --> 00:06:31,650 which is going to be a recursive function. 85 00:06:34,110 --> 00:06:39,600 So where does this DFS function will return, it will not add anything, it will just visit all the 86 00:06:39,600 --> 00:06:43,840 elements and what it is taking it is taking graphics input. 87 00:06:44,010 --> 00:06:48,890 So let's take the graph vector vector character. 88 00:06:50,220 --> 00:06:53,490 And this is our graph grid, right? 89 00:06:53,830 --> 00:06:57,090 It is taking the index, Anji. 90 00:06:57,570 --> 00:07:02,190 And it is also taking I've visited at as input rate. 91 00:07:02,730 --> 00:07:05,670 So this visit today is to the Eddie. 92 00:07:08,850 --> 00:07:19,010 And visited, so one important thing is basically this visitor that should be passed Bio-Reference, 93 00:07:20,580 --> 00:07:24,390 this visitor that should be passed by the fence, because what we are going to do is we are going to 94 00:07:24,390 --> 00:07:25,910 change this reality. 95 00:07:26,190 --> 00:07:28,050 So that changes should be reflected here. 96 00:07:28,050 --> 00:07:34,560 Also made so you will not pass by value, you will pass by reference, because the whatever changes 97 00:07:34,560 --> 00:07:39,520 we are doing in this function that changes should reflect in main function also. 98 00:07:40,260 --> 00:07:43,820 So you need to pass Bio-Reference and that is very important. 99 00:07:43,830 --> 00:07:45,920 Otherwise your algorithm will not run. 100 00:07:46,320 --> 00:07:47,900 It will give you wrong output. 101 00:07:48,390 --> 00:07:50,550 So it has to be Bio-Reference. 102 00:07:52,590 --> 00:07:58,110 Now, this is going to be a recursive algorithm, so very simple, simple based guesses, right? 103 00:07:58,260 --> 00:08:09,540 If I is less than zero indexes invalid, you are just basically less than zero invalid index or the 104 00:08:09,540 --> 00:08:14,190 value of AI is basically greater than or close to your griddled size. 105 00:08:15,600 --> 00:08:18,450 Again, invalid index. 106 00:08:20,070 --> 00:08:26,910 Or Jay is basically bigger than our to grade of zero dark size again in the next. 107 00:08:28,800 --> 00:08:31,020 So these are all invalidly next. 108 00:08:31,380 --> 00:08:34,770 And when we will get invalided, index, what we will do, we will simply return. 109 00:08:34,860 --> 00:08:38,130 Do not do anything Sembler written because the index is invalid. 110 00:08:38,970 --> 00:08:39,350 Right? 111 00:08:39,360 --> 00:08:47,580 Simple because other simple baskets can be if the current element is basically zero, if the current 112 00:08:47,580 --> 00:08:49,520 element is water. 113 00:08:50,100 --> 00:08:53,430 So if the current element is water, what will will simply return. 114 00:08:54,150 --> 00:08:54,580 Right. 115 00:08:55,500 --> 00:09:01,230 Similarly, another base case can be if the current element is already visited. 116 00:09:01,260 --> 00:09:05,760 So if we started off IGY is already true. 117 00:09:05,880 --> 00:09:09,090 We have already visited this element in that case. 118 00:09:09,090 --> 00:09:12,590 Also where they are going to do is you done right. 119 00:09:12,870 --> 00:09:16,560 So simple, simple cases because this is going to be a recursive algorithm. 120 00:09:18,450 --> 00:09:21,510 So now let's actually write the code for the first. 121 00:09:23,720 --> 00:09:30,110 So I'm standing at the current parliament, right, I am standing at current elements, so I am standing 122 00:09:30,110 --> 00:09:30,420 here. 123 00:09:30,800 --> 00:09:34,670 So what I'm going to do is I will mogg this element as visited. 124 00:09:36,080 --> 00:09:44,060 So what to do since I am standing at the next AMG and this index is valid and this index is containing 125 00:09:44,060 --> 00:09:47,520 element one that this land and this index has not been visited before. 126 00:09:48,260 --> 00:09:53,690 So this element has not been visited before and now I am visiting this element. 127 00:09:53,690 --> 00:09:55,880 So I will mark this as proof. 128 00:09:56,930 --> 00:09:57,320 Right. 129 00:09:57,320 --> 00:09:58,580 I will mark this as true. 130 00:09:58,820 --> 00:10:03,200 And since we are changing the mystery value, that's why we need to take Bio-Reference, because the 131 00:10:03,210 --> 00:10:06,310 changes must be reflected here in this function also. 132 00:10:06,680 --> 00:10:09,560 And then what we need to do so from a given index. 133 00:10:10,280 --> 00:10:11,810 From a given index. 134 00:10:12,620 --> 00:10:13,070 Right. 135 00:10:13,070 --> 00:10:14,360 From a given index. 136 00:10:14,360 --> 00:10:19,720 What you can do, you can move in either directions, we can move in either directions. 137 00:10:19,970 --> 00:10:26,030 So what we will do, we will call DFS, we will call the function DFS in all the other directions, 138 00:10:27,590 --> 00:10:30,460 call DFS, function in all eight directions. 139 00:10:30,980 --> 00:10:31,390 Right. 140 00:10:31,790 --> 00:10:32,900 So let's do that. 141 00:10:34,460 --> 00:10:38,300 We need to call the DFS function on all eight Badakshan. 142 00:10:38,300 --> 00:10:39,950 So the efface. 143 00:10:41,180 --> 00:10:42,560 This is a recursive algorithm. 144 00:10:42,560 --> 00:10:46,010 We already know this will take graph as input. 145 00:10:46,550 --> 00:10:56,420 This will take the first let's say I minus one and G minus one and it will take with Gianetti Farshad. 146 00:10:58,340 --> 00:10:58,750 Right. 147 00:10:58,760 --> 00:11:06,170 So let's copy this and there are eight directions possible, so let's paste them. 148 00:11:13,100 --> 00:11:22,010 So this is one, two, three, four, five, six, seven and eight, yes, so total eight directions. 149 00:11:27,270 --> 00:11:33,420 And now let us change the values, so I am minus and minus, and the second can be a minus, one energy 150 00:11:35,250 --> 00:11:44,340 tower can be a minus one energy plus one for the addiction can be, I think, minus one. 151 00:11:46,770 --> 00:11:52,320 Which direction can be I and J plus one? 152 00:11:54,500 --> 00:12:03,660 Sixth medication can be a plus one and G minus one, correct, next direction can be lifted. 153 00:12:03,680 --> 00:12:13,550 This is G and this is a plus one and let's say the last election is a plus one and G plus one. 154 00:12:14,090 --> 00:12:16,790 So D let me give some spaces between them. 155 00:12:21,840 --> 00:12:24,790 So these are total eight possible actions, right? 156 00:12:26,070 --> 00:12:31,320 So from a given element, I will call DFS on all eight possible directions. 157 00:12:34,870 --> 00:12:36,610 And that will be the entity called. 158 00:12:44,480 --> 00:12:47,370 Right, so this will be the entire record. 159 00:12:48,140 --> 00:12:49,870 Let me give space's here. 160 00:12:53,760 --> 00:12:58,800 Yep, and let's also make sure that in line. 161 00:13:02,430 --> 00:13:06,900 So, yeah, this will be total eight possible directions, right? 162 00:13:07,170 --> 00:13:09,090 So this is the complete code. 163 00:13:10,770 --> 00:13:12,480 Let's our current annual summit. 164 00:13:17,120 --> 00:13:19,440 So we are getting some compilation error. 165 00:13:19,610 --> 00:13:20,190 Did you mean. 166 00:13:20,660 --> 00:13:26,570 OK, so spelling mistake, this will be size. 167 00:13:32,680 --> 00:13:34,930 Yep, our code is working right now. 168 00:13:43,110 --> 00:13:45,150 OK, so we are getting a wrong answer. 169 00:13:45,780 --> 00:13:48,620 Let's see what we did wrong. 170 00:13:52,230 --> 00:13:55,320 OK, so let's see, what is this? 171 00:13:56,190 --> 00:14:05,190 So this is we have one one zero zero zero, then again, one one zero zero zero, then zero zero one 172 00:14:05,190 --> 00:14:09,130 zero zero and then zero zero zero one one. 173 00:14:09,210 --> 00:14:11,520 So this is the graph. 174 00:14:11,520 --> 00:14:14,630 And yeah, the expected output is correct. 175 00:14:14,640 --> 00:14:17,220 This is one connected component. 176 00:14:17,280 --> 00:14:19,050 This is another connected component. 177 00:14:19,050 --> 00:14:20,920 And this is another connected component. 178 00:14:21,300 --> 00:14:25,800 So the expected output is correct and our goal is giving the output as one. 179 00:14:26,880 --> 00:14:31,830 So our goal is giving wrong output and why it is. 180 00:14:31,830 --> 00:14:36,270 So let's try to analyze what we did wrong here. 181 00:14:38,310 --> 00:14:39,030 Hi, everyone. 182 00:14:39,060 --> 00:14:42,340 So I have figured out actually why our goal was failing. 183 00:14:42,630 --> 00:14:46,280 So let me try to submit this quote again and let's see. 184 00:14:47,400 --> 00:14:51,500 So see, this is the input which is given to us. 185 00:14:52,140 --> 00:14:57,780 The input is one one zero zero one zero, then one one zero zero zero. 186 00:14:58,050 --> 00:15:03,340 Then I have zero zero one zero zero, then zero zero zero one and one. 187 00:15:03,750 --> 00:15:07,060 So what my goal is returning. 188 00:15:07,320 --> 00:15:10,890 So what I am doing, I am moving in two directions. 189 00:15:11,340 --> 00:15:11,790 Right. 190 00:15:12,630 --> 00:15:14,290 If you will move in each direction. 191 00:15:14,550 --> 00:15:16,680 So that means you can move diagonally also. 192 00:15:17,880 --> 00:15:18,290 Right. 193 00:15:18,570 --> 00:15:21,490 So I can move diagonally and I can reach here. 194 00:15:21,510 --> 00:15:24,010 Similarly, I can move diagonally and I can reach here. 195 00:15:24,270 --> 00:15:27,560 So what my goal is doing, I am moving in eight directions. 196 00:15:27,780 --> 00:15:31,620 So my goal is combining all these right. 197 00:15:31,860 --> 00:15:33,720 My goal is combining all this. 198 00:15:33,720 --> 00:15:38,120 And that's why my goal is retaining that output is when there is only one connected component. 199 00:15:38,610 --> 00:15:40,470 So that's why the goal is returning one. 200 00:15:40,650 --> 00:15:46,680 But if you will see the actual quotient description in that question, it has mentioned that you can 201 00:15:46,680 --> 00:15:48,900 either move horizontally automatically. 202 00:15:49,470 --> 00:15:49,720 Right. 203 00:15:50,010 --> 00:15:53,160 It is mentioned that you can move in four directions. 204 00:15:53,580 --> 00:15:56,660 So it was like pretty silly mistake from my side. 205 00:15:56,670 --> 00:15:58,830 Actually, I saw only one question before solving this. 206 00:15:59,130 --> 00:16:02,430 So in that question, I was able to move in a direction. 207 00:16:02,700 --> 00:16:04,410 So that's why I missed out here. 208 00:16:04,680 --> 00:16:09,060 And like, I paused the video for some time and I tried debugging a lot. 209 00:16:09,060 --> 00:16:13,680 And then when I was not able to find the solution, then I read the description again. 210 00:16:13,690 --> 00:16:17,580 And then I was able to figure out that you can move only in four directions. 211 00:16:18,600 --> 00:16:20,940 So if you will move in for direction, what will happen? 212 00:16:21,120 --> 00:16:23,430 You will not be able to reach this right. 213 00:16:23,670 --> 00:16:26,220 You will not be able to reach at this one. 214 00:16:26,230 --> 00:16:28,620 So you will finish here similarly. 215 00:16:28,620 --> 00:16:33,540 Then you will finish it because you will not be able to move diagonally and this will be another connected 216 00:16:33,540 --> 00:16:34,120 component. 217 00:16:34,320 --> 00:16:39,230 So instead of moving in a direction, we need to modify our code to move only in four direction. 218 00:16:39,510 --> 00:16:42,030 So that was the error that we did. 219 00:16:42,310 --> 00:16:44,490 It was a pretty silly mistake from my side. 220 00:16:44,850 --> 00:16:45,270 Right. 221 00:16:45,420 --> 00:16:46,910 So here you can see it. 222 00:16:46,950 --> 00:16:53,100 You can see for yourself that the question is asking us to move only horizontally or vertically Direxion 223 00:16:53,100 --> 00:16:54,480 and not diagonal direction. 224 00:16:54,870 --> 00:16:56,330 So I am so sorry, guys. 225 00:16:57,030 --> 00:17:00,950 That's why you should read the question very carefully before jumping to the code. 226 00:17:01,110 --> 00:17:05,849 So since we can move on in four direction, let's remove this line. 227 00:17:08,880 --> 00:17:12,390 Which else I think we need to remove this line also. 228 00:17:15,829 --> 00:17:17,869 We need to remove this line. 229 00:17:21,010 --> 00:17:28,550 And we need to remove this line, so I have removed all the four directional directions right now. 230 00:17:28,569 --> 00:17:29,240 This is correct. 231 00:17:30,370 --> 00:17:31,570 Now I will call Vilborg. 232 00:17:36,410 --> 00:17:39,110 So now we are getting a time limit exceeded. 233 00:17:40,160 --> 00:17:41,090 Yeah, very good. 234 00:17:41,570 --> 00:17:44,270 Let's see how many test case our court is passing. 235 00:17:51,960 --> 00:17:56,610 So our goal, the past 47 days, cases out of 48, 236 00:17:59,610 --> 00:18:02,070 so basically we are getting time limited exited. 237 00:18:02,380 --> 00:18:08,070 So let's try to find out what is the time complexity of our code and then we will see how we can reduce 238 00:18:08,070 --> 00:18:09,160 the time complexity. 239 00:18:09,240 --> 00:18:13,630 So let's discuss the time complexity so that we can reduce our time complexity. 240 00:18:14,040 --> 00:18:21,090 So what is the time complexity of how according to our time complexities and I mean because we are iterating 241 00:18:21,090 --> 00:18:27,210 right Ambrosiano in columns so that when the time complexities Emman and we are going to each and every 242 00:18:27,210 --> 00:18:28,410 element only once. 243 00:18:28,530 --> 00:18:28,890 Right. 244 00:18:29,130 --> 00:18:35,140 We are visiting the element only once since we are visiting each and every element only once. 245 00:18:35,160 --> 00:18:41,380 So that's why the time complexities Eman and regarding the space complexity. 246 00:18:41,400 --> 00:18:43,340 So we have created this visibility. 247 00:18:43,570 --> 00:18:45,030 So space complexities. 248 00:18:45,030 --> 00:18:46,080 Emman, right. 249 00:18:46,350 --> 00:18:48,270 So this is the time and the space complexity. 250 00:18:48,510 --> 00:18:52,860 And even after this time, complexity, I am getting time limited exited. 251 00:18:53,250 --> 00:18:56,990 So that means there is not a problem with our logic. 252 00:18:57,000 --> 00:19:01,620 There is some different problem and what this different problem is. 253 00:19:01,920 --> 00:19:05,760 So here what they are doing, you are pressing the greenery, right. 254 00:19:05,760 --> 00:19:07,290 And you are passing by value. 255 00:19:07,680 --> 00:19:10,380 So by value, what will happen for this function? 256 00:19:10,740 --> 00:19:15,090 This grid array will be created and all the values will be copied. 257 00:19:15,390 --> 00:19:15,850 Right. 258 00:19:15,990 --> 00:19:17,130 So that will take time. 259 00:19:17,760 --> 00:19:20,760 So what I am trying to say here is this grid array. 260 00:19:20,760 --> 00:19:25,590 We are passing this great array by value and when we pass by value, so what will happen? 261 00:19:25,800 --> 00:19:30,750 This function will create one local variable grid and it will copy all the data. 262 00:19:31,590 --> 00:19:33,350 It will copy all the data. 263 00:19:34,620 --> 00:19:36,450 So that is time consuming, right? 264 00:19:36,880 --> 00:19:38,160 That will take time. 265 00:19:38,400 --> 00:19:43,650 So what we will do, instead of taking by value, if we will take it by reference, then we will not 266 00:19:43,650 --> 00:19:48,620 have a time limit extended, because if you take by definition, then we will not copy the data. 267 00:19:48,870 --> 00:19:51,350 We will just refer to the data that is present here. 268 00:19:54,770 --> 00:20:00,920 So what we are going to do is instead of taking great away by volume, we will take great Bio-Reference 269 00:20:01,640 --> 00:20:05,480 so that we will avoid the time that we are using in copying the data. 270 00:20:06,140 --> 00:20:09,710 Now, if we will submit now, Gore will work. 271 00:20:13,020 --> 00:20:15,810 Right, so now our court is working. 272 00:20:16,180 --> 00:20:23,250 OK, so this was the catch, a great idea by the fence to reduce your time complexity, to save the 273 00:20:23,250 --> 00:20:25,350 time that you are using in copying the data. 274 00:20:27,000 --> 00:20:29,060 So this is it from this device. 275 00:20:29,070 --> 00:20:32,910 If you have any doubt to ask me, I will see you in the next one. 276 00:20:33,090 --> 00:20:33,630 Thank you.