1
00:00:01,440 --> 00:00:02,940
Hi, everyone, welcome back.

2
00:00:02,969 --> 00:00:08,530
So in this video, we will be writing the code for this problem and now let's start writing the code.

3
00:00:08,790 --> 00:00:14,000
So as discussed, what we need to do, we need to perform the level order reversal.

4
00:00:14,760 --> 00:00:16,550
So let me write all these steps here.

5
00:00:17,130 --> 00:00:23,430
So what we are going to do, we are going to perform lavalier traversal for performing level or traversal.

6
00:00:23,430 --> 00:00:24,390
We need WANGU.

7
00:00:24,900 --> 00:00:29,730
And this will contain two things Naude and the horizontal distance for that node.

8
00:00:30,120 --> 00:00:31,790
And then we need one map.

9
00:00:32,910 --> 00:00:39,930
So this map will contain the horizontal distance ASCII and list of nodes as well.

10
00:00:40,980 --> 00:00:42,900
So let's start writing the code now.

11
00:00:43,410 --> 00:00:46,760
So first of all, what do we do.

12
00:00:46,770 --> 00:00:50,310
Let's create the map so we need one map.

13
00:00:51,180 --> 00:00:57,990
Map of integer horizontal distance would be integer and then the list of nodes.

14
00:00:58,260 --> 00:01:00,960
So vector end and let's name it my map.

15
00:01:01,620 --> 00:01:02,070
Fine.

16
00:01:02,580 --> 00:01:06,000
And now we're going to do we need to do level or traversal.

17
00:01:06,000 --> 00:01:10,440
So for doing level traversal we need two and vertical with that type of queue.

18
00:01:11,730 --> 00:01:21,000
So the type of goulet's define struct let's name it element or what should we name it.

19
00:01:23,140 --> 00:01:32,770
Yeah, let's name it one element, one element of Q So what it will contain, it will contain two things

20
00:01:35,140 --> 00:01:39,040
the node and the horizontal distance.

21
00:01:39,920 --> 00:01:44,880
Actually is the horizontal distance, so you will be of type element.

22
00:01:45,350 --> 00:01:48,250
It will contain two things in horizontal distance.

23
00:01:48,560 --> 00:01:51,230
So this is not and this is horizontal distance.

24
00:01:51,230 --> 00:01:54,520
Fine now for doing traversal.

25
00:01:54,560 --> 00:01:55,350
What do they need to do?

26
00:01:55,790 --> 00:01:57,500
Let's push the first element.

27
00:01:57,510 --> 00:01:58,500
So culotte push.

28
00:01:59,120 --> 00:02:00,160
So what is the node?

29
00:02:00,170 --> 00:02:02,000
Nor will be the route obviously.

30
00:02:02,000 --> 00:02:03,670
And what is the horizontal distance?

31
00:02:03,680 --> 00:02:04,630
It is zero.

32
00:02:05,090 --> 00:02:07,760
So for you, the horizontal distance is zero.

33
00:02:08,789 --> 00:02:18,540
And now what we need to do, our standard laboratory ourselves, or that is while the queue is not empty,

34
00:02:19,320 --> 00:02:20,310
we will do something.

35
00:02:21,350 --> 00:02:30,600
And what we will do so element, temporary or legitimate element friend.

36
00:02:31,760 --> 00:02:33,790
So what is this dude, old friend?

37
00:02:34,490 --> 00:02:40,860
It will return one element and obviously not pop to pop this element also.

38
00:02:41,630 --> 00:02:46,910
Now, what we need to do, let's find out what is the horizontal distance for this node.

39
00:02:48,320 --> 00:02:51,570
So what is the horizontal distance for this node?

40
00:02:51,920 --> 00:02:57,290
So what is the current horizontal distance that will be front d'arte, horizontal distance.

41
00:02:57,800 --> 00:03:00,880
So front dot, horizontal distance.

42
00:03:00,890 --> 00:03:02,600
I will get the horizontal distance.

43
00:03:03,140 --> 00:03:04,740
And what is this node?

44
00:03:05,390 --> 00:03:11,060
So let's figure out, let's name it current node.

45
00:03:12,200 --> 00:03:15,900
So current nodes, front dot node.

46
00:03:17,090 --> 00:03:19,490
Now all they need to do, we need to insert in map.

47
00:03:20,240 --> 00:03:26,500
So let's insert my map of current horizontal distance.

48
00:03:26,900 --> 00:03:30,130
So my map of current horizontal distance is basically a list.

49
00:03:30,140 --> 00:03:30,530
Right.

50
00:03:30,560 --> 00:03:31,550
This is one list.

51
00:03:32,120 --> 00:03:36,070
So you will put this is one vector.

52
00:03:36,080 --> 00:03:41,270
So that's why you need to you will use the function, push back.

53
00:03:42,080 --> 00:03:48,670
And what will push you will push the data and how we can figure out the data we have the current A.

54
00:03:48,980 --> 00:03:54,530
So current value will give us the data to so to add value.

55
00:03:59,150 --> 00:04:06,320
So what I am doing here is so it's very simple, we decided that the will contain two things known and

56
00:04:06,320 --> 00:04:07,420
the horizontal distance.

57
00:04:07,640 --> 00:04:12,890
So I created this struct or basically if you are having confusion, you can write class also.

58
00:04:13,700 --> 00:04:15,700
So I'm creating a class of Purita members.

59
00:04:15,710 --> 00:04:18,490
One is the node and that one is the horizontal distance.

60
00:04:19,040 --> 00:04:20,899
And this is our map, right.

61
00:04:21,200 --> 00:04:25,420
Horizontal distance versus the date of nodes.

62
00:04:25,760 --> 00:04:29,620
And then we need to push the route and obviously it's zero.

63
00:04:29,900 --> 00:04:35,960
So Bush route, that is, if this is the route node, I will push the node three and the data, the

64
00:04:36,350 --> 00:04:37,540
distance is zero.

65
00:04:38,790 --> 00:04:39,010
Right.

66
00:04:39,260 --> 00:04:41,930
This is the horizontal distance and this is the node.

67
00:04:43,430 --> 00:04:44,540
Then it's very simple.

68
00:04:45,320 --> 00:04:49,740
Take different elements of different elements, find out the horizontal distance, find out the correct

69
00:04:49,790 --> 00:04:54,410
node, and you need to put this data inside the map.

70
00:04:54,420 --> 00:05:00,230
So my map of current horizontal distance that will give you a vector and in the vector we will push

71
00:05:00,230 --> 00:05:00,860
the data.

72
00:05:01,400 --> 00:05:01,910
Simple.

73
00:05:02,420 --> 00:05:03,880
So the code is very simple.

74
00:05:03,890 --> 00:05:10,040
And now what we need to do, we need to check if left exist, then insert left and the right exist,

75
00:05:10,340 --> 00:05:11,720
then insert right in the queue.

76
00:05:14,440 --> 00:05:19,340
So the next step in doing traversal is we need to check if left exist.

77
00:05:19,930 --> 00:05:20,740
So if.

78
00:05:23,850 --> 00:05:27,180
Left exist, that is left is not close to null.

79
00:05:29,700 --> 00:05:34,350
Then what will do, you will insert this in cute, so cute or Bush.

80
00:05:36,390 --> 00:05:41,190
What will push so, you know, to push two things, what is the node?

81
00:05:42,000 --> 00:05:48,020
So the node is the left of this and what is the horizontal distance?

82
00:05:48,270 --> 00:05:54,210
So when you are going left, your horizontal distance will decrease between the horizontal distance

83
00:05:54,210 --> 00:05:54,810
minus one.

84
00:05:55,920 --> 00:05:56,360
Right.

85
00:05:56,670 --> 00:05:58,830
Similarly, check if right axis.

86
00:06:00,760 --> 00:06:04,360
So if the right of Canada did not exist.

87
00:06:09,020 --> 00:06:13,040
Then you will push in the queue, so queue that push,

88
00:06:16,310 --> 00:06:17,690
you will push two things.

89
00:06:18,050 --> 00:06:25,490
The first is the node, so the node is the right of the current node and what is the horizontal distance?

90
00:06:25,910 --> 00:06:27,350
So you are going right.

91
00:06:27,350 --> 00:06:32,450
And we decided that when we go right, the horizontal distance will increase by one.

92
00:06:32,840 --> 00:06:34,130
So horizontal distance.

93
00:06:35,950 --> 00:06:47,080
Plus one simple and then you will come out of this very loop, your map is ready, your map is ready,

94
00:06:47,080 --> 00:06:52,250
and now we're going to do we need to iterate over the map to populate our answer.

95
00:06:52,570 --> 00:06:54,820
So let's create one answer.

96
00:06:55,810 --> 00:06:57,150
So what will be my answer?

97
00:06:57,190 --> 00:07:00,770
My answer will be the perfect parent answer.

98
00:07:00,850 --> 00:07:02,500
You can see the return type is this.

99
00:07:04,090 --> 00:07:06,550
So let's I tripped over the map.

100
00:07:07,180 --> 00:07:16,260
So for outrating or the map authority is my map darte begin.

101
00:07:18,090 --> 00:07:26,200
It is not close to my map dot end and 80 plus plus items.

102
00:07:26,200 --> 00:07:28,120
I created this variable.

103
00:07:28,120 --> 00:07:31,180
It, it means that it's an arbitrator.

104
00:07:31,180 --> 00:07:33,260
So I need to iterate over the map.

105
00:07:33,280 --> 00:07:34,280
Let's consider this.

106
00:07:35,290 --> 00:07:43,600
So for this example, we discussed that my map will look like this minus one zero one and also so against

107
00:07:43,600 --> 00:07:47,710
minus one, I have nine stored against zero.

108
00:07:47,950 --> 00:07:51,610
I have three and 15 stored and against one.

109
00:07:51,610 --> 00:07:56,360
I have 20 stored and against two, I have seven stored.

110
00:07:56,380 --> 00:08:01,240
So what I am doing, I am I rating, I am migrating over the map.

111
00:08:01,540 --> 00:08:08,400
So it means I iterator I, it means I trade and so I am migrating over the map.

112
00:08:09,130 --> 00:08:10,530
And what is this.

113
00:08:10,600 --> 00:08:13,720
This is the first value so we will access the first value.

114
00:08:14,200 --> 00:08:17,200
I drew first and this is the second value.

115
00:08:17,530 --> 00:08:19,240
So that is ideato second.

116
00:08:20,610 --> 00:08:26,460
To access the list, you will write it at second to access the horizontal distance, you will write

117
00:08:26,460 --> 00:08:30,090
it at first, but we are interested in this idea.

118
00:08:30,420 --> 00:08:34,210
Second, that is the useful thing for us.

119
00:08:34,230 --> 00:08:35,010
So Waterloo.

120
00:08:37,929 --> 00:08:41,669
So, Victor, let's name it, small answer.

121
00:08:44,159 --> 00:08:45,490
So what is this small answer?

122
00:08:45,510 --> 00:08:47,430
This is it, ideato.

123
00:08:48,900 --> 00:08:58,890
Second, and you need to push this answer in the big vector, so Ensenat push back, Small answered,

124
00:09:00,960 --> 00:09:03,380
and finally you will have done your answer.

125
00:09:04,230 --> 00:09:10,080
So many of you will think that this court is correct and it is correct also.

126
00:09:10,680 --> 00:09:13,020
But it is not 100 percent correct.

127
00:09:13,020 --> 00:09:15,270
And why it is not 100 percent correct.

128
00:09:15,270 --> 00:09:22,290
Because in the they are saying that when you are returning the answer, make sure that these values

129
00:09:22,290 --> 00:09:26,280
are sorted, make sure that these values are sorted.

130
00:09:26,280 --> 00:09:29,450
But here what I am doing, I am figuring out this whole answer.

131
00:09:30,180 --> 00:09:37,040
I took this small answer and I directly inserted the answer in my answer vector.

132
00:09:37,230 --> 00:09:40,910
So before directly inserting, you need to first start and then insert.

133
00:09:41,160 --> 00:09:47,230
So it is given the question that you need to first start and then you need to return your answer.

134
00:09:47,250 --> 00:09:50,810
So before returning the answer, we will start.

135
00:09:51,240 --> 00:09:53,520
So we have inbuilt function Sarte.

136
00:09:55,920 --> 00:10:00,720
So small, answered, darte, begin small answer dart.

137
00:10:00,730 --> 00:10:03,600
And now the code is correct.

138
00:10:04,130 --> 00:10:10,210
So I think now our code will work and for the basic basic test cases.

139
00:10:10,230 --> 00:10:21,720
So for example, if your route does not exist, so if the route is basically null, so then you do not

140
00:10:21,720 --> 00:10:25,860
need to do anything, you will simply return this empty vector, right.

141
00:10:25,860 --> 00:10:27,300
You will return empty vector.

142
00:10:27,630 --> 00:10:33,750
So OK, so instead of creating the answer here, let's create the answer above so that I can return

143
00:10:33,930 --> 00:10:34,850
empty answer.

144
00:10:37,410 --> 00:10:44,250
So I am creating my answer here and if the rotational I will return empty vector so I will return empty

145
00:10:44,250 --> 00:10:44,470
vector.

146
00:10:44,520 --> 00:10:46,590
Right, so let's return.

147
00:10:51,050 --> 00:11:00,140
Ouran said, we will return, Emboli answered, so yeah, I think our goal should work and let's test.

148
00:11:06,310 --> 00:11:09,220
OK, so we need to put semicolon here.

149
00:11:17,610 --> 00:11:24,520
OK, so this is actually you will see this is VSL and I have written the complete value.

150
00:11:24,550 --> 00:11:26,340
So I need to write V.L..

151
00:11:34,840 --> 00:11:41,680
OK, so it doesn't know what is actually and that's obvious because I need to write current horizontal

152
00:11:41,680 --> 00:11:50,890
distance, so current horizontal distance minus one and the current horizontal distance plus one now

153
00:11:50,890 --> 00:11:51,450
is correct.

154
00:11:56,970 --> 00:12:02,460
Yep, so our goal is passing the basic discuses, let's try to submit our code.

155
00:12:05,770 --> 00:12:11,800
OK, so basically, let's see what's happening here, it's delayed this, so we are getting a wrong

156
00:12:11,800 --> 00:12:16,890
answer for this and my output is zero zero matching.

157
00:12:16,900 --> 00:12:18,100
So this is two to three.

158
00:12:18,670 --> 00:12:22,030
This is my output and the expected output is three to two.

159
00:12:23,190 --> 00:12:27,890
I have four, I have four, so the expected output is three to two.

160
00:12:28,230 --> 00:12:31,590
Let me see how many discuses our goal is passing.

161
00:12:40,210 --> 00:12:47,380
OK, so we passed 14 out of 32, so we do not need to sort of strange.

162
00:12:49,300 --> 00:12:50,650
Let's try to it again.

163
00:12:59,020 --> 00:12:59,890
Interesting.

164
00:13:05,640 --> 00:13:07,610
Here we are passing 16, so.

165
00:13:09,550 --> 00:13:12,120
I think the test cases are not correct.

166
00:13:15,070 --> 00:13:18,370
Because the question is asking us to start before returning.

167
00:13:29,800 --> 00:13:31,800
OK, let's try to sum it one more time.

168
00:13:38,860 --> 00:13:45,760
Well, I think there is some problem with the test cases, because here you can see, you can read that

169
00:13:46,060 --> 00:13:51,550
we need to we need to return our output sorted by their values.

170
00:13:51,550 --> 00:13:53,700
So that's why I'm returning one, five, six here.

171
00:13:54,190 --> 00:13:56,260
But when I am submitting the answer.

172
00:14:02,250 --> 00:14:05,670
So it's saying that the expected output is three to two.

173
00:14:05,700 --> 00:14:11,140
I think this test case is wrong because the expected output should be sorted.

174
00:14:12,060 --> 00:14:15,500
We read that the data expecting that the output should be sorted.

175
00:14:15,510 --> 00:14:18,700
So two to three is the right answer and not three to two.

176
00:14:19,950 --> 00:14:26,430
So I don't know, like what's happening here, why they have given this test cases or maybe we are missing

177
00:14:26,430 --> 00:14:29,370
something, but I don't think we are missing something.

178
00:14:29,670 --> 00:14:36,620
And if we try to draw that result, it will be like this one three, then I have one here.

179
00:14:36,720 --> 00:14:37,830
I have zero here.

180
00:14:38,730 --> 00:14:40,040
I have four here.

181
00:14:40,730 --> 00:14:42,630
There are two here and two here.

182
00:14:43,680 --> 00:14:52,470
This is not creating and our output is correct because first one will be zero, then next one will be

183
00:14:52,470 --> 00:14:52,800
one.

184
00:14:53,100 --> 00:14:55,650
And then I have three, three, two and two.

185
00:14:56,160 --> 00:14:56,560
Right.

186
00:14:56,580 --> 00:15:01,440
So they are just directly returning without sorting them.

187
00:15:02,100 --> 00:15:04,140
And the question they are asking us to sort.

188
00:15:04,190 --> 00:15:06,460
So output should be two, three, three and then four.

189
00:15:07,140 --> 00:15:13,200
So I think the best case is for this problem are not correct because our goal is giving the right output

190
00:15:13,200 --> 00:15:13,580
right.

191
00:15:14,370 --> 00:15:18,390
They are asking us to start before returning and we are sorting before returning.

192
00:15:18,420 --> 00:15:24,980
So it seems very strange that lead court test cases are wrong for this problem.

193
00:15:25,170 --> 00:15:29,250
They are clearly asking us that sort and not according to their values.

194
00:15:29,250 --> 00:15:33,690
And when we are done, we are sorting through our output is correct.

195
00:15:33,690 --> 00:15:38,040
And this problem has definitely some issues with the test cases.

196
00:15:38,040 --> 00:15:38,310
Right.

197
00:15:38,520 --> 00:15:45,090
So our goal is correct and what I will do so I will figure it out by whether we are doing something

198
00:15:45,090 --> 00:15:46,610
wrong or we are doing something right.

199
00:15:46,950 --> 00:15:49,050
So I think we are doing everything right.

200
00:15:49,320 --> 00:15:52,220
And the problem definitely has some issues.

201
00:15:53,730 --> 00:15:55,770
So this is all out this video, guys.

202
00:15:56,010 --> 00:16:02,220
And let me know if you also figure out something, because I'm not able to understand what we are doing

203
00:16:02,220 --> 00:16:02,610
wrong.

204
00:16:03,150 --> 00:16:05,220
So this is all about this device.

205
00:16:05,490 --> 00:16:06,950
I will see you in the next one.

206
00:16:06,960 --> 00:16:07,500
Thank you.