1 00:00:00,990 --> 00:00:02,880 Hi, everyone, welcome to this new video. 2 00:00:02,910 --> 00:00:07,620 So in this video, we are going to write the code for this problem, make some off island. 3 00:00:07,620 --> 00:00:12,800 And as discussed, what we will do, we are going to modify the code for the number of islands problem. 4 00:00:12,810 --> 00:00:17,700 We just need to maintain one variable area and will take maximum of all the areas. 5 00:00:18,060 --> 00:00:18,500 Right. 6 00:00:18,750 --> 00:00:20,430 That's already need to do so. 7 00:00:20,430 --> 00:00:24,060 Let's copy that code and let's start modifying that code. 8 00:00:24,960 --> 00:00:27,810 So first, let us copy this DFS code. 9 00:00:41,170 --> 00:00:46,570 So this is the call for DFS and let's copy this one also. 10 00:00:53,480 --> 00:00:53,910 Right. 11 00:00:54,500 --> 00:00:55,440 So that's it. 12 00:00:56,000 --> 00:00:56,900 Now what you need to do. 13 00:00:59,610 --> 00:01:05,400 So right, so what you need to do, first of all, we need to do some changes here and what changes 14 00:01:05,880 --> 00:01:11,520 so here what I'm returning I'm returning the number of connected components, but I need to return the 15 00:01:11,540 --> 00:01:12,320 make some media. 16 00:01:12,570 --> 00:01:14,510 So let's change this variable to one. 17 00:01:15,390 --> 00:01:21,930 I will return answer, right, and similarly, let's remove it from here and let's return our answer 18 00:01:21,930 --> 00:01:23,340 answer will be to make some area. 19 00:01:24,660 --> 00:01:25,820 So let's do that. 20 00:01:27,420 --> 00:01:30,610 So I'm going to return the maximum area. 21 00:01:30,630 --> 00:01:35,340 Let's name this variable max area rate. 22 00:01:35,700 --> 00:01:39,560 So we are not counting the number of connected components. 23 00:01:39,630 --> 00:01:41,100 Let's remove going from here. 24 00:01:44,160 --> 00:01:49,660 And we are going to return the mix media, right? 25 00:01:50,280 --> 00:01:52,360 We are going to return maximum area. 26 00:01:52,770 --> 00:01:58,320 Also, one more thing to notice here is this time the grid is basically of type integer. 27 00:01:58,680 --> 00:02:02,140 Late in previous problem, grid was of type character. 28 00:02:02,520 --> 00:02:04,620 So that's why I have written character here. 29 00:02:04,650 --> 00:02:06,570 Now let's modify it to integer. 30 00:02:08,940 --> 00:02:16,050 So what else do we need to do, what I said is, while finding out the connected component, so in this 31 00:02:16,050 --> 00:02:22,680 loop, what I am doing, I am calling DFS, that means I am finding out one connected component since 32 00:02:22,680 --> 00:02:24,230 I am finding out connected component. 33 00:02:24,260 --> 00:02:26,240 Let's also find the area for this. 34 00:02:26,250 --> 00:02:26,610 Right. 35 00:02:26,790 --> 00:02:35,430 Let's say initially Area zero and Tulu, let's also pass the area because we want to find out the area 36 00:02:35,430 --> 00:02:36,000 for this. 37 00:02:36,000 --> 00:02:36,400 Right. 38 00:02:36,720 --> 00:02:42,240 So what this DFS function will do, it will visit the connected component and it will also find out 39 00:02:42,240 --> 00:02:44,540 the area and what we need to do. 40 00:02:44,550 --> 00:02:46,460 We need to find out the myxoma area. 41 00:02:46,470 --> 00:02:56,060 So make some area will be the maximum of the current maximum area and the area for this connected component. 42 00:02:57,300 --> 00:02:57,810 Right. 43 00:02:59,460 --> 00:03:04,500 So we are passing area here, so we need to pass area. 44 00:03:09,920 --> 00:03:12,290 And we need to pass a.D.A head. 45 00:03:23,540 --> 00:03:33,920 And what else so whenever you are visiting the element, that means you will do area plus since you 46 00:03:33,920 --> 00:03:38,440 are changing the value of area here, you are changing the value of area here. 47 00:03:38,840 --> 00:03:44,830 So that means you need to pass area by reference so that those changes can appear here. 48 00:03:45,260 --> 00:03:45,660 Right. 49 00:03:47,210 --> 00:03:50,170 So let me try to explain you what is happening here. 50 00:03:52,010 --> 00:03:53,560 See what I am doing. 51 00:03:53,840 --> 00:03:56,030 I need to find out the make some area. 52 00:03:56,390 --> 00:03:56,810 Right. 53 00:03:56,810 --> 00:03:58,960 Make some area of all connected components. 54 00:03:59,360 --> 00:04:05,330 So what I am doing is whenever I am calling DFS, so what DFS will do, it will visit one connected 55 00:04:05,330 --> 00:04:09,280 component based DFS will visit one connected component. 56 00:04:09,290 --> 00:04:14,330 So I am passing one variable area so that DFS will update the area rate. 57 00:04:14,540 --> 00:04:17,120 I am passing variable area and usually it is zero. 58 00:04:17,570 --> 00:04:18,980 I am passing variable area. 59 00:04:18,990 --> 00:04:25,070 So whenever DFS will visit any element, what it will do, it will do area plus plus Veidt. 60 00:04:25,250 --> 00:04:30,350 So when DFS will visit this element, this connected component, so area will become full. 61 00:04:31,130 --> 00:04:36,170 And since you are changing the value of area, so you need to pass area by reference because what we 62 00:04:36,170 --> 00:04:39,560 need to do, we need to take maksym off all the areas. 63 00:04:39,890 --> 00:04:46,850 We need to find the maximum of all the areas that you need to pass area by reference so that the changes 64 00:04:46,850 --> 00:04:49,350 that you are doing here should be reflected here. 65 00:04:49,370 --> 00:04:51,830 So I think that is the complete code. 66 00:04:52,100 --> 00:04:53,630 So let's submit our code. 67 00:04:55,020 --> 00:04:57,170 Let's first run our code and then we will submit. 68 00:05:01,280 --> 00:05:04,400 So we are getting wrong answer for this, OK? 69 00:05:05,090 --> 00:05:08,180 My output is zero and the expected output is six. 70 00:05:09,830 --> 00:05:11,720 OK, so what we did wrong. 71 00:05:14,460 --> 00:05:22,560 This is area and I'm taking makes media is mix of the mix of media and area, this seems correct to 72 00:05:22,560 --> 00:05:22,890 me. 73 00:05:38,850 --> 00:05:46,170 OK, so what you did wrong here is, see, this is what integer array and what I'm doing, this is character, 74 00:05:46,650 --> 00:05:47,050 right? 75 00:05:47,070 --> 00:05:48,120 This should be integer. 76 00:05:49,740 --> 00:05:50,660 This should be one. 77 00:05:50,820 --> 00:05:57,100 And similarly, instead of zero here character zero, you will compare it to zero rate. 78 00:05:57,810 --> 00:05:58,350 Yep. 79 00:05:58,380 --> 00:05:59,610 So let's try again. 80 00:06:03,900 --> 00:06:05,730 Yes, it's working, it's now. 81 00:06:09,420 --> 00:06:12,000 Yes, so basically our goal is working. 82 00:06:12,210 --> 00:06:16,060 And let me try to explain to you again what we are doing here. 83 00:06:17,790 --> 00:06:18,900 See what I am doing here. 84 00:06:19,170 --> 00:06:20,130 I need to find out. 85 00:06:20,140 --> 00:06:23,490 The maximum aerofoil can include component, because that will be my answer. 86 00:06:24,540 --> 00:06:28,620 But this function, does this function visit one connected component? 87 00:06:30,460 --> 00:06:37,510 And I need to find out the area for all connected component, because we need to take Maksym off all 88 00:06:37,510 --> 00:06:42,190 the areas and how we can find the area for one connected component. 89 00:06:42,430 --> 00:06:46,640 So whenever you are visiting one element, that element will be the part of your connected component. 90 00:06:46,660 --> 00:06:49,360 So you will simply do area placeless and that's it. 91 00:06:50,300 --> 00:06:52,110 That nothing else. 92 00:06:52,240 --> 00:06:53,470 Very, very simple code. 93 00:06:53,650 --> 00:06:54,670 So what will be the time? 94 00:06:54,670 --> 00:06:55,440 Complexity. 95 00:06:55,450 --> 00:06:57,970 So you are visiting each and every element. 96 00:06:57,970 --> 00:07:01,750 Only once certain complexity will be eminent doing. 97 00:07:02,380 --> 00:07:05,170 And what is the space complexity, space complexities. 98 00:07:05,170 --> 00:07:06,370 You are creating this visit. 99 00:07:07,240 --> 00:07:10,000 So space complexities, eminent domain and that. 100 00:07:10,900 --> 00:07:13,700 So this is the time and the space complexity for this problem. 101 00:07:15,130 --> 00:07:17,890 So if you have any doubt in this problem, do ask me. 102 00:07:18,130 --> 00:07:19,930 This is all about this device. 103 00:07:20,020 --> 00:07:21,410 I will see you in the next one. 104 00:07:21,520 --> 00:07:22,090 Thank you.