1
00:00:00,930 --> 00:00:02,310
Hi, everyone, welcome back.

2
00:00:02,340 --> 00:00:07,950
So in this video, we are going to write the code for this problem distinct no in Windows, so let's

3
00:00:07,950 --> 00:00:09,270
start writing the code.

4
00:00:13,390 --> 00:00:15,520
And we discussed that, what do we do?

5
00:00:15,550 --> 00:00:17,650
So let me take one example.

6
00:00:19,390 --> 00:00:25,870
So if the window size is three and if this is your Eddie.

7
00:00:27,480 --> 00:00:35,410
It's a one four one five seven, eight and nine or zero letter.

8
00:00:35,490 --> 00:00:36,960
This is your that is what we need to do.

9
00:00:37,200 --> 00:00:44,220
So first of all, we need to create one map and this map, what it will contain, it will contain the

10
00:00:44,220 --> 00:00:48,390
element and the count of that element and window size three.

11
00:00:49,620 --> 00:00:55,160
So first of all, let's create one map and also we need to return answer any.

12
00:00:55,170 --> 00:00:55,490
Right.

13
00:00:55,500 --> 00:00:57,180
We need to return answer vector.

14
00:00:58,890 --> 00:01:00,970
So let's consider these two.

15
00:01:00,990 --> 00:01:02,730
Let's create these two things first.

16
00:01:03,870 --> 00:01:05,489
So let's create one map.

17
00:01:09,770 --> 00:01:16,820
Key and value key will be integer and value will also be integer and my map.

18
00:01:19,720 --> 00:01:28,810
So what we need to do, we need to create one answer, so victory and answer, and now what is the first

19
00:01:28,810 --> 00:01:29,150
step?

20
00:01:29,470 --> 00:01:32,140
I think the first step will be what we need to do.

21
00:01:32,410 --> 00:01:38,610
So we will insert all three elements that is ALBE elements.

22
00:01:38,980 --> 00:01:42,450
So I will insert, first of all, all these three elements in the map.

23
00:01:43,030 --> 00:01:45,670
So my map will look like this one.

24
00:01:46,340 --> 00:01:51,620
So the count of one is two and the count of one is count of this one.

25
00:01:51,670 --> 00:01:55,840
So first of all, I need to insert these values one for everyone.

26
00:01:56,140 --> 00:01:59,650
So the count of one will become two and the count of four will become one.

27
00:02:00,310 --> 00:02:07,930
And after doing this, what the unique elements in this window, that will be my map glasses.

28
00:02:07,930 --> 00:02:11,540
That is to my eyes, I will contain two.

29
00:02:11,710 --> 00:02:14,320
So let's do this much amount of work first.

30
00:02:14,470 --> 00:02:17,500
So first of all, as discussed, what to do?

31
00:02:17,500 --> 00:02:24,280
We need to go to B elements that these three elements.

32
00:02:27,470 --> 00:02:30,680
So let's insert so my map.

33
00:02:32,360 --> 00:02:45,140
Of age of 80 plus plus, right, I'm inserting the element in the count and after coming out, my answer

34
00:02:45,140 --> 00:02:47,240
will contain two and what is two?

35
00:02:47,240 --> 00:02:50,060
Two is basically the number of entries in the map.

36
00:02:50,860 --> 00:03:00,670
So answers Eddie will contain will you two and two is nothing but my map that size the number of entries

37
00:03:00,670 --> 00:03:01,950
in the map.

38
00:03:03,220 --> 00:03:08,440
So after this much amount of work, my answer is containing to solve what I need to do.

39
00:03:08,920 --> 00:03:13,720
I need to start one loop from this and I will go till the end of the area.

40
00:03:14,380 --> 00:03:15,550
So what is this index?

41
00:03:15,580 --> 00:03:23,140
This index is three three means B, I will start from industry that is index B and I will go till the

42
00:03:23,140 --> 00:03:23,390
end.

43
00:03:23,410 --> 00:03:32,440
So what I will do first step is I will insert five, so I will insert five and the count of five is

44
00:03:32,440 --> 00:03:32,710
one.

45
00:03:33,370 --> 00:03:34,820
Five is coming for the first time.

46
00:03:35,980 --> 00:03:38,320
So you are considering one new element.

47
00:03:39,490 --> 00:03:43,810
That means you need to remove one element because the window size has to be three.

48
00:03:44,650 --> 00:03:48,760
So you need to remove one element in which element you will remove.

49
00:03:48,760 --> 00:03:53,580
You will remove element one, you will remove element one.

50
00:03:53,590 --> 00:03:57,400
So from this element from index three, how can I reach index zero?

51
00:03:57,820 --> 00:03:58,370
Nothing.

52
00:03:58,390 --> 00:04:00,910
What do you need to write, i.e. minus B?

53
00:04:03,220 --> 00:04:04,870
So I is basically three.

54
00:04:05,380 --> 00:04:05,620
Right.

55
00:04:05,710 --> 00:04:08,210
You are standing at the next three and the value of these three.

56
00:04:08,410 --> 00:04:10,040
So three minus three will be zero.

57
00:04:10,420 --> 00:04:15,360
So what do you need to reduce the count for this element.

58
00:04:15,370 --> 00:04:19,810
So you will reduce the count and the count will become one.

59
00:04:21,430 --> 00:04:29,230
So you are considering this window for one five and we need to find out the number of unique elements

60
00:04:29,230 --> 00:04:29,980
in this window.

61
00:04:29,980 --> 00:04:36,940
And that will be my map Dartez, which is containing three entries so that you will insert three in

62
00:04:36,940 --> 00:04:38,370
this way, we will move forward.

63
00:04:38,770 --> 00:04:45,250
So what I need to do, I need to start iterating over the array from index three.

64
00:04:45,730 --> 00:04:47,590
And what is index three?

65
00:04:47,590 --> 00:04:51,010
Index three is nothing but B only.

66
00:04:51,010 --> 00:04:54,250
So I understand it says.

67
00:04:58,510 --> 00:05:07,450
I placeless, so what we need to do, we need to insert the current element, so I am inserting the

68
00:05:07,450 --> 00:05:11,100
current element in the map, but now the window size increases by one.

69
00:05:11,410 --> 00:05:15,370
So we need to maintain the window size for maintaining the window size.

70
00:05:15,380 --> 00:05:19,360
You need to remove the element that we will not consider.

71
00:05:20,320 --> 00:05:21,370
Minus minus.

72
00:05:22,120 --> 00:05:23,970
And finally, what we will do.

73
00:05:25,600 --> 00:05:29,220
So how many unique elements are present in this particular window?

74
00:05:29,230 --> 00:05:32,710
That will be my map, not size.

75
00:05:35,680 --> 00:05:42,490
And finally, what do you do after this loop is over, you can return your answer and that's it, and

76
00:05:42,500 --> 00:05:42,950
that's it.

77
00:05:43,270 --> 00:05:45,350
So let's see whether this quote will work or not.

78
00:05:45,370 --> 00:05:48,100
So what I'm doing, I'm considering the current element.

79
00:05:48,100 --> 00:05:50,020
So I am pushing this element in the map.

80
00:05:50,260 --> 00:05:51,510
So I'm considering five.

81
00:05:52,300 --> 00:05:54,610
That's why I am pushing element five in the map.

82
00:05:56,530 --> 00:06:02,200
And now I am talking about this window, so I need to remove this element from the map, so that's why

83
00:06:02,200 --> 00:06:08,980
I am doing I minus B and I'm reducing the count, so I am reducing the count and count becomes one.

84
00:06:10,150 --> 00:06:18,130
So in this way, we will be able to update this map and after updating the map, we can push the elements

85
00:06:18,130 --> 00:06:19,230
inside the answer.

86
00:06:19,660 --> 00:06:21,810
But this code is not correct way.

87
00:06:22,120 --> 00:06:22,960
So what will happen?

88
00:06:22,960 --> 00:06:23,440
Let's see.

89
00:06:25,390 --> 00:06:27,930
So the next element that we will consider will be seven.

90
00:06:27,940 --> 00:06:34,980
So you will insert seven and the count of seven is one since you are doing seven.

91
00:06:34,990 --> 00:06:37,100
So you need to remove element four.

92
00:06:37,690 --> 00:06:42,280
So what you will do, you will reduce the count by one, so reduce the count by one.

93
00:06:42,820 --> 00:06:46,960
So the count becomes to zero, the count becomes zero.

94
00:06:46,960 --> 00:06:49,740
And what they are doing next, you are figuring out the size.

95
00:06:49,750 --> 00:06:50,680
So what is the size?

96
00:06:51,160 --> 00:06:54,730
Map is containing four elements, so I will insert four.

97
00:06:54,730 --> 00:07:03,420
But four is wrong because in this window, in this window there are three elements.

98
00:07:04,000 --> 00:07:09,130
And since there are three elements, the maximum answer can be three and all the three elements are

99
00:07:09,130 --> 00:07:09,460
unique.

100
00:07:09,490 --> 00:07:15,070
So your answer should be three, but you will retain the answers for and via four, because after reducing

101
00:07:15,070 --> 00:07:20,500
the count, when the count becomes zero, you also need to remove the element from the map.

102
00:07:21,160 --> 00:07:26,010
So you also need to remove the element from the map if the count becomes zero.

103
00:07:27,070 --> 00:07:34,540
So you need to check that if after reducing the count, the count becomes zero.

104
00:07:35,990 --> 00:07:42,380
Then you also need to delete this element from the map, so my map dot it is we need to delete this

105
00:07:42,380 --> 00:07:44,810
element and this element is.

106
00:07:46,780 --> 00:07:58,480
I minus B. So now this is correct, discord is correct, but one more thing, what we need to handle.

107
00:07:58,480 --> 00:08:05,860
So it is given the indication it is given in the indication that if the value of B is good, then and

108
00:08:05,890 --> 00:08:07,210
and is basically ignored.

109
00:08:07,210 --> 00:08:13,800
Sighs So it is given the question, if this is the condition, then you need to return Empty-headed,

110
00:08:14,020 --> 00:08:15,560
then you need to return Ampitheater.

111
00:08:15,790 --> 00:08:18,090
So let us use this condition also.

112
00:08:19,090 --> 00:08:21,040
So it is mentioned in the question.

113
00:08:23,440 --> 00:08:27,710
That F B is good.

114
00:08:27,760 --> 00:08:37,659
Then Edward says, then your answer will be empathy, so you will retain empathy, Eddie and I think

115
00:08:37,659 --> 00:08:38,690
our code will work.

116
00:08:39,340 --> 00:08:41,020
So let's test our code.

117
00:08:46,880 --> 00:08:51,200
Yep, so basically our goal is working and let's try to submit our code now.

118
00:08:58,990 --> 00:09:05,590
So, yes, basically our goal is working and we can also discuss the time and the space complexity for

119
00:09:05,590 --> 00:09:05,950
this.

120
00:09:08,710 --> 00:09:12,610
So what we are doing here, we are creating one map.

121
00:09:15,710 --> 00:09:22,040
And this map will contain a maximum of bee and trees at one time.

122
00:09:22,340 --> 00:09:26,860
This map will contain maximum bee entries at any given point of time.

123
00:09:27,290 --> 00:09:30,980
So the space complexities big off bee.

124
00:09:32,090 --> 00:09:34,130
And we are also returning this.

125
00:09:34,130 --> 00:09:37,300
We are creating this vector and we are returning this.

126
00:09:38,360 --> 00:09:45,410
So since the question is asking us to return the answer in the form of vectors, let's not include this

127
00:09:45,410 --> 00:09:49,370
in calculating space complexity because it is the question prerequisite.

128
00:09:49,680 --> 00:09:52,600
It is the question demand that you need to create and return.

129
00:09:52,880 --> 00:09:57,010
So let's not let's not consider this in space complexity.

130
00:09:57,380 --> 00:10:01,610
You may or may not consider this, but let's say we are not considering this.

131
00:10:01,820 --> 00:10:08,240
So the only extra space that we are using is basically this map and this map will contain maximum of

132
00:10:08,240 --> 00:10:10,460
being present at any given point of time.

133
00:10:11,540 --> 00:10:16,830
So space complexities, big off B, what will be the time complexity?

134
00:10:18,050 --> 00:10:27,230
So first you are outrating Dahlby and next you are retreating from the number of elements and minus

135
00:10:27,230 --> 00:10:27,680
B times.

136
00:10:27,690 --> 00:10:31,640
So in total you are iterating basically you are iterating.

137
00:10:31,640 --> 00:10:32,840
See, this is your area.

138
00:10:33,260 --> 00:10:36,620
First you are trading only this much will be the next.

139
00:10:36,620 --> 00:10:38,440
You are reading from this till the end.

140
00:10:38,720 --> 00:10:41,480
So basically I can say I am I reading like this.

141
00:10:42,170 --> 00:10:46,380
So time complexity is big often and this operation is constant.

142
00:10:46,790 --> 00:10:51,050
This is also constant again, constant, constant and constant.

143
00:10:51,380 --> 00:10:57,070
So all these operations are big, often so time complexities big often.

144
00:10:57,650 --> 00:10:59,840
So this is their time in this space complexity.

145
00:11:02,000 --> 00:11:10,430
And if you are not satisfied with the space complexity, so we can also consider this instead of calculation

146
00:11:10,430 --> 00:11:13,320
and what will be how many elements in this answer will contain?

147
00:11:13,760 --> 00:11:15,620
So there are elements, right.

148
00:11:15,620 --> 00:11:23,180
And the window sizes be so we can say that space complexity will be and might not be the answer.

149
00:11:23,180 --> 00:11:25,250
Addresses will be and minus be.

150
00:11:25,250 --> 00:11:28,290
So if you will add so B and B will cancel out each other.

151
00:11:28,310 --> 00:11:30,510
So space complexity is also a big often.

152
00:11:30,530 --> 00:11:37,850
So finally, the time is big often and the space is big enough and when you will consider the space

153
00:11:37,850 --> 00:11:39,540
given to this answer vector.

154
00:11:39,560 --> 00:11:42,290
So this is the time and the space complexity for this problem.

155
00:11:43,370 --> 00:11:45,320
So this is all about this video.

156
00:11:45,330 --> 00:11:50,640
Guys, if you have any doubt, you can ask me in the junior section and I will see you in the next one.

157
00:11:50,660 --> 00:11:51,200
Thank you.