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.

