1
00:00:01,520 --> 00:00:02,210
Hi, everyone.

2
00:00:02,240 --> 00:00:05,440
So today we are going to solve this question cycle addiction.

3
00:00:06,140 --> 00:00:13,160
OK, so what we have to do so given a long list, so we will be given a long list and we have to return

4
00:00:13,160 --> 00:00:16,980
a boolean value whether the list contains a cycle or not.

5
00:00:17,000 --> 00:00:19,320
So in this case, we can see it is a cycle.

6
00:00:19,790 --> 00:00:22,490
So since they the cycle is a loop, we have to return.

7
00:00:22,490 --> 00:00:23,540
True in this case.

8
00:00:24,300 --> 00:00:27,500
OK, and if there is no cycle, then we can return false.

9
00:00:27,950 --> 00:00:29,900
So this question is present only.

10
00:00:29,990 --> 00:00:30,300
Good.

11
00:00:30,540 --> 00:00:34,620
OK, so this is the problem now we can see here.

12
00:00:34,940 --> 00:00:42,260
So since this contains this linked list contains a cycle, so we have to return to it was a continuous

13
00:00:42,260 --> 00:00:43,650
cycle we have to return to.

14
00:00:44,060 --> 00:00:47,480
In this case, there is no cycle, so we have to return false.

15
00:00:47,810 --> 00:00:51,280
OK, so this is our challenge.

16
00:00:51,290 --> 00:00:54,340
We have to solve this question using or question memory.

17
00:00:54,350 --> 00:00:57,600
OK, so constant memory, basically open space.

18
00:00:58,280 --> 00:00:59,870
So how are we going to solve this problem?

19
00:01:00,140 --> 00:01:04,069
So the first approach to solve this problem is with the help of map.

20
00:01:04,260 --> 00:01:08,050
OK, so how are we going to solve this problem with the help of MAP.

21
00:01:08,420 --> 00:01:10,130
So the structure of map will be.

22
00:01:11,440 --> 00:01:19,020
List North Star and a Boolean value, OK, so list North Star and also give a loopier.

23
00:01:19,240 --> 00:01:22,700
So this will be Mekki and this will be my value.

24
00:01:23,620 --> 00:01:26,620
So what I will do, I will add it over this link list.

25
00:01:26,980 --> 00:01:31,050
Now I am standing here it so is it present inside the map.

26
00:01:31,060 --> 00:01:33,100
So this is my map.

27
00:01:33,100 --> 00:01:35,680
So initially my map is empty so I will check.

28
00:01:36,070 --> 00:01:37,910
Is it pleasant inside the map.

29
00:01:37,930 --> 00:01:38,980
No it is not.

30
00:01:39,010 --> 00:01:41,230
So I will put it here then.

31
00:01:41,230 --> 00:01:41,770
I will check.

32
00:01:42,110 --> 00:01:43,870
Is one present inside the map.

33
00:01:43,870 --> 00:01:44,280
No.

34
00:01:44,590 --> 00:01:46,330
Then put it inside the map.

35
00:01:46,960 --> 00:01:49,550
So is nine percent inside the map.

36
00:01:50,110 --> 00:01:53,830
No it isn't so but nine inside the map.

37
00:01:54,010 --> 00:01:57,030
OK, so is four present inside the map.

38
00:01:57,040 --> 00:01:58,030
No it does not.

39
00:01:58,030 --> 00:01:59,980
Then push forward inside the map.

40
00:02:00,400 --> 00:02:02,160
So is to present.

41
00:02:02,170 --> 00:02:03,280
No it is not.

42
00:02:03,430 --> 00:02:04,300
Then Pushtu.

43
00:02:04,840 --> 00:02:06,190
So is three present.

44
00:02:06,370 --> 00:02:09,940
No Bush three seven present inside the map.

45
00:02:09,940 --> 00:02:14,170
No Bush seven to present inside the map.

46
00:02:14,170 --> 00:02:17,020
Yes it is present but no it is not present.

47
00:02:17,020 --> 00:02:17,380
Why.

48
00:02:17,620 --> 00:02:20,650
Because we are storing list North Star basically.

49
00:02:20,680 --> 00:02:21,330
What is a list.

50
00:02:21,340 --> 00:02:21,900
North Star.

51
00:02:22,030 --> 00:02:23,500
So basically it is a pointer.

52
00:02:24,740 --> 00:02:28,010
It is a pointer and it is pointing towards a..

53
00:02:29,310 --> 00:02:36,000
So this node contains a value and a next pointer and led to the address of this snorers 800.

54
00:02:36,180 --> 00:02:39,380
So basically List North Star contains 800.

55
00:02:39,420 --> 00:02:44,820
OK, and obviously this node and this node, they will have different address.

56
00:02:44,820 --> 00:02:49,850
For example, this node has a 700 and this node has addressed 900.

57
00:02:50,070 --> 00:02:57,420
So basically at this point, I am storing 700, OK, and I'm comparing is 900 close to 700.

58
00:02:57,690 --> 00:02:58,600
Not it is not.

59
00:02:58,650 --> 00:03:03,270
OK, so basically we are comparing this north to not only the value.

60
00:03:04,080 --> 00:03:07,000
OK, now we will check nine.

61
00:03:07,020 --> 00:03:08,400
So is nine percent.

62
00:03:08,620 --> 00:03:14,640
Yes, nine is present, but no it does not present because we have to compare both the values, we only

63
00:03:14,640 --> 00:03:17,580
compare the value and we will also compare the next pointer.

64
00:03:17,680 --> 00:03:19,690
OK, so basically this is nine.

65
00:03:19,740 --> 00:03:23,880
This nine has a different address and this nine has a different address.

66
00:03:24,150 --> 00:03:25,530
So nine is not present.

67
00:03:25,740 --> 00:03:28,300
OK, then we will again come back.

68
00:03:28,320 --> 00:03:30,110
To do so is to present.

69
00:03:30,390 --> 00:03:32,090
Yes, two is present.

70
00:03:32,250 --> 00:03:36,880
So its address is also seven hundred and its address is also seven hundred.

71
00:03:37,140 --> 00:03:38,400
So since this is present.

72
00:03:38,400 --> 00:03:39,690
So I will return to.

73
00:03:41,040 --> 00:03:45,400
OK, so our output will be true now in this time.

74
00:03:45,630 --> 00:03:50,490
So in this case, with the help of MAP, what is the time and the space complexities of time?

75
00:03:50,500 --> 00:03:52,030
Complexity is basically linear.

76
00:03:52,050 --> 00:03:57,210
We are just operating on the left and the space complexities when we are creating the map.

77
00:03:57,420 --> 00:04:01,990
OK, so when the linked list does not contain a cycle.

78
00:04:02,010 --> 00:04:02,990
So what will happen?

79
00:04:03,000 --> 00:04:05,970
So this is let's say this is the list.

80
00:04:06,030 --> 00:04:06,600
One, two, three.

81
00:04:06,840 --> 00:04:09,960
So in this example, this list does not contain any cycle.

82
00:04:10,120 --> 00:04:10,920
So it will happen.

83
00:04:11,400 --> 00:04:15,090
So when one is inside the map, so initially the map is empty.

84
00:04:15,100 --> 00:04:16,200
No one is not present.

85
00:04:16,500 --> 00:04:17,040
Push one.

86
00:04:17,370 --> 00:04:18,320
So to present.

87
00:04:18,329 --> 00:04:19,380
No, it is not present.

88
00:04:19,380 --> 00:04:21,029
Bush to three present.

89
00:04:21,209 --> 00:04:21,899
No, it does not.

90
00:04:21,899 --> 00:04:22,850
President Bush three.

91
00:04:23,070 --> 00:04:27,010
Then I will come maternal and my linked list is over.

92
00:04:27,180 --> 00:04:28,920
So basically I will return false.

93
00:04:29,550 --> 00:04:37,710
OK, so the time complexities and the space complexities also big of an but the problem askers.

94
00:04:39,200 --> 00:04:40,760
To do it in open space.

95
00:04:41,120 --> 00:04:47,000
OK, so how we can solve this problem in open space, so this approach, which is called slow and fast

96
00:04:47,000 --> 00:04:47,900
Brender approach.

97
00:04:48,000 --> 00:04:51,780
OK, slow and fast point.

98
00:04:51,780 --> 00:04:55,090
That approach now in slow and fast point, that approach.

99
00:04:55,130 --> 00:04:55,880
What will happen.

100
00:04:56,300 --> 00:04:57,390
So slow pointer.

101
00:04:57,410 --> 00:04:58,880
I will take two pointers.

102
00:04:59,030 --> 00:05:02,660
OK, I will take two pointer.

103
00:05:02,660 --> 00:05:08,090
So the name of the first pointer is slow and the name of the second point that is fast.

104
00:05:08,710 --> 00:05:14,480
OK, so if a slow pointer takes a jump of one, then fast pointer will take a jump of two.

105
00:05:15,260 --> 00:05:19,600
OK, so fast pointer will run twice the speed of slow pointer.

106
00:05:19,850 --> 00:05:24,470
OK, so how we can use this approach of slow and fast point in this question.

107
00:05:24,910 --> 00:05:28,370
OK, now let's first draw the diagram.

108
00:05:28,370 --> 00:05:30,050
OK, let us first take an example.

109
00:05:30,560 --> 00:05:32,860
We will take a big, big example to understand.

110
00:05:32,870 --> 00:05:37,040
OK, so let's say this is it then.

111
00:05:37,070 --> 00:05:42,260
I have one nine four again let's say two.

112
00:05:42,830 --> 00:05:46,340
I am taking the same example, the example that we discussed above.

113
00:05:46,460 --> 00:05:52,960
OK, so three, then seven, then let's say two nine.

114
00:05:53,390 --> 00:05:54,830
And this is two again.

115
00:05:54,860 --> 00:06:02,630
OK, so this is my long list and now we will try it in our slow and fast pointer approach.

116
00:06:02,630 --> 00:06:07,290
We will see how and how this law enforcement approach will help us to solve this problem.

117
00:06:07,310 --> 00:06:11,920
OK, so as we discussed, we will take two pointers low and fast.

118
00:06:12,260 --> 00:06:18,360
So initially, both slow and fast pointer, they will be present at the head of the list.

119
00:06:18,380 --> 00:06:19,900
So this is the head of the linked list.

120
00:06:20,270 --> 00:06:24,680
So initially, both slow and fast pointer are at present.

121
00:06:24,680 --> 00:06:26,210
At present at the head of the linked list.

122
00:06:26,330 --> 00:06:29,340
Now lowpoint, they will take a jump of one and fast point.

123
00:06:29,340 --> 00:06:30,580
They will take a jump of two.

124
00:06:30,860 --> 00:06:34,010
OK, so after one jump, what will happen?

125
00:06:34,400 --> 00:06:35,870
Slow pointer will come here.

126
00:06:36,800 --> 00:06:40,310
And at the same time, first point they will take a jump of two.

127
00:06:40,550 --> 00:06:42,280
So fast pointer will come here.

128
00:06:43,160 --> 00:06:43,610
OK.

129
00:06:44,670 --> 00:06:50,250
Now, again, slow, that will take a jump of one, so slow pointer will come here.

130
00:06:52,170 --> 00:06:58,200
Now, first point, I will take a jump of two, so one and two, so first point, I will come here.

131
00:07:00,360 --> 00:07:02,330
OK, now, slow point.

132
00:07:02,370 --> 00:07:05,580
We'll take a jump off one, it's this low point that will come here.

133
00:07:07,630 --> 00:07:09,700
Now, point I will take the jump off to.

134
00:07:11,200 --> 00:07:17,710
So one and two, so first point, I will come here now against lowpoint, jump of one.

135
00:07:19,350 --> 00:07:26,960
Fast point to jump off, too, so this is fast now, slow appointer takes a jump of one.

136
00:07:27,000 --> 00:07:27,930
This is slow.

137
00:07:29,220 --> 00:07:32,010
Fassbinder, take the jump off one and two.

138
00:07:33,780 --> 00:07:36,900
Now, see, slope equals fast point.

139
00:07:37,080 --> 00:07:43,320
So at the point at the moment of time when slow equals fast, slow and fast point that they are equal,

140
00:07:43,590 --> 00:07:45,300
that means there is a loop.

141
00:07:45,650 --> 00:07:48,540
That means there is loop or basically cycle in the long list.

142
00:07:49,440 --> 00:07:53,610
OK, so how we can see when slow and fast point our meeting then.

143
00:07:53,610 --> 00:07:55,910
On what basis I can say slow.

144
00:07:55,950 --> 00:08:05,460
There is a cycle in the long list because think like this, a person is moving at a speed of X and another

145
00:08:05,460 --> 00:08:14,850
person is moving with the speed of two X, so and then they are meeting so they can only meet when there

146
00:08:14,850 --> 00:08:16,690
is some cycle, ok.

147
00:08:16,920 --> 00:08:18,960
They can only do it when they do some cycle.

148
00:08:18,970 --> 00:08:21,880
For example, let's say this is the structure.

149
00:08:22,110 --> 00:08:25,050
So this is the first person and this is the second person.

150
00:08:25,170 --> 00:08:29,270
So the second person is moving twice the speed of the first person and they are meeting.

151
00:08:29,460 --> 00:08:36,030
So if if there's a straight road, then obviously this is the first person, this is the second person,

152
00:08:36,030 --> 00:08:38,700
then these two person can never meet, OK?

153
00:08:38,700 --> 00:08:43,919
Because the second person is twice is running with twice the speed of the first person.

154
00:08:44,100 --> 00:08:46,400
And if there is a straight they will never meet.

155
00:08:47,100 --> 00:08:53,700
They can only meet when there is a cycle, OK, only when they the cycle then only they can meet.

156
00:08:54,600 --> 00:08:59,940
OK, so this problem, this slow and fast pointer approach, this is also used to find the midpoint

157
00:08:59,940 --> 00:09:00,680
of the linked list.

158
00:09:00,740 --> 00:09:03,450
OK, so how we can find the midpoint of a long list.

159
00:09:03,930 --> 00:09:05,680
So suppose so.

160
00:09:05,700 --> 00:09:07,400
Suppose this is a long list.

161
00:09:07,560 --> 00:09:08,460
So what will happen.

162
00:09:08,940 --> 00:09:09,810
Slow and fast.

163
00:09:09,820 --> 00:09:11,010
Point the boat out here.

164
00:09:11,130 --> 00:09:17,700
So slow pointer will move with the speed of one basically X and point will move with the double speed,

165
00:09:18,210 --> 00:09:22,170
then slope will come here and fast pointer will reach the end of the linked list.

166
00:09:22,380 --> 00:09:29,850
So when the fast pointer reaches the tail of the linked list, then at that time the slope pointer will

167
00:09:29,850 --> 00:09:33,260
be at the middle point, the midpoint of the linked list, obviously.

168
00:09:33,660 --> 00:09:36,300
OK, so slow pointon fast pointer.

169
00:09:36,450 --> 00:09:41,280
Initially they both were present at the height of the list, but the slope point is moving.

170
00:09:41,280 --> 00:09:44,630
The speed of X and fast pointer is moving with the speed of the weeks.

171
00:09:44,940 --> 00:09:51,070
So when the fast pointer will reach the tail then obviously the slope when they will reach the midpoint.

172
00:09:51,360 --> 00:09:56,460
OK, so this approach, this fast and slow pointer approach, this is also used to find the midpoint

173
00:09:56,730 --> 00:09:57,930
and we are using that.

174
00:09:58,380 --> 00:10:03,240
We are using that same approach to detect whether there is a cycle in the linked list or not.

175
00:10:03,900 --> 00:10:06,920
OK, so now let us implement both the approach.

176
00:10:07,860 --> 00:10:09,900
So let us implement.

177
00:10:10,080 --> 00:10:12,430
I am implementing both the approaches.

178
00:10:12,450 --> 00:10:13,140
OK, so.

179
00:10:15,140 --> 00:10:17,850
First, let us implement the map approach.

180
00:10:17,880 --> 00:10:18,280
OK?

181
00:10:19,620 --> 00:10:28,050
So let's not start and bull, let's say the name of the map is my map, so what we have to do, we simply

182
00:10:28,050 --> 00:10:31,710
have to it over the linked list.

183
00:10:32,280 --> 00:10:34,350
So while it's not a closed tunnel.

184
00:10:35,400 --> 00:10:36,450
Now, what we have to do.

185
00:10:38,000 --> 00:10:41,120
Check whether this note is present inside the map or not.

186
00:10:41,150 --> 00:10:44,630
OK, so my map not count.

187
00:10:47,010 --> 00:10:54,180
A, if the north is pleasant inside the map, that means there is a cycle, if there is a cycle, we

188
00:10:54,180 --> 00:10:55,790
can simply return true from here.

189
00:10:56,740 --> 00:11:02,440
Otherwise, what we have to do, we will push this node inside the map, so my map of a.

190
00:11:04,000 --> 00:11:05,110
It's basically true.

191
00:11:06,410 --> 00:11:10,270
And at the end at the end of the Vilo begins and it unfolds.

192
00:11:11,200 --> 00:11:11,570
OK.

193
00:11:19,010 --> 00:11:21,320
OK, so basically spelling mistake.

194
00:11:30,240 --> 00:11:33,540
OK, so we are returning to and output is false.

195
00:11:38,230 --> 00:11:43,570
OK, so whether the mistake equals the next offie.

196
00:11:50,840 --> 00:11:52,460
OK, so our court is working.

197
00:11:54,540 --> 00:12:00,090
Time, complexity of this map approach is basically one time and one space.

198
00:12:00,110 --> 00:12:02,070
OK, so how does current function works?

199
00:12:03,620 --> 00:12:11,180
So basically this can't function, this can't function will count how many times the node appears inside

200
00:12:11,180 --> 00:12:11,720
the map.

201
00:12:11,750 --> 00:12:12,920
OK, so.

202
00:12:13,950 --> 00:12:20,220
The count can be zero or the count can be any positive integer, OK, so that only two values in the

203
00:12:20,220 --> 00:12:21,070
count will be zero.

204
00:12:21,090 --> 00:12:24,360
So if the zero, that means the node is not present.

205
00:12:24,360 --> 00:12:27,900
And if the count is a positive integer, that means it is Besant.

206
00:12:27,930 --> 00:12:30,600
OK, so then we will return.

207
00:12:30,600 --> 00:12:30,890
True.

208
00:12:30,900 --> 00:12:36,080
So we will only return true only when the output is a positive integer.

209
00:12:36,090 --> 00:12:37,650
So the output is a positive integer.

210
00:12:37,650 --> 00:12:39,240
This condition will become true.

211
00:12:39,960 --> 00:12:42,170
If this condition is true, then only we are returning.

212
00:12:42,450 --> 00:12:46,250
OK, so the complexities oint and the space complexities also join.

213
00:12:46,520 --> 00:12:49,830
OK, now let us implement this law and the Fassbinder approach.

214
00:12:51,660 --> 00:12:59,100
So we need two pointers and initially both the pointers will point towards the head of the linked list.

215
00:12:59,100 --> 00:13:06,960
So slow is pointing towards a and similarly, the fast pointer is also pointing towards a OK now fast

216
00:13:06,960 --> 00:13:07,260
point.

217
00:13:07,260 --> 00:13:13,500
I will run with twice the speed of X so while fast and then the next of fast.

218
00:13:15,310 --> 00:13:20,740
So why I'm doing this, why the condition is this because fast has to take doorjambs.

219
00:13:22,160 --> 00:13:30,080
So fast is going to take two jumps, so fast is next off, next of fast.

220
00:13:31,770 --> 00:13:35,640
Fastest making two jumps and slow will take only one jump.

221
00:13:36,000 --> 00:13:39,000
Slow, slow, slow equals the next slow.

222
00:13:44,500 --> 00:13:53,290
And if at any point slow and fast article, that means there is intersection, OK, that means there

223
00:13:53,290 --> 00:13:56,050
is a loop in the linked list.

224
00:13:56,260 --> 00:13:58,990
OK, and finally we can return false.

225
00:14:00,460 --> 00:14:01,960
So let's test with good.

226
00:14:05,170 --> 00:14:11,560
OK, so our court is working, so the complexity of this slow and fast winter approaches or in one speech.

227
00:14:12,640 --> 00:14:17,930
Now you might get confused why I have written this condition first and next of.

228
00:14:18,460 --> 00:14:20,530
So basically, take this example.

229
00:14:20,540 --> 00:14:21,250
One, two, three.

230
00:14:21,610 --> 00:14:28,300
OK, and let's say for so fast is currently at the head position so fast is going to take two jumps.

231
00:14:28,340 --> 00:14:32,200
OK, fast is taking two jumps so fast.

232
00:14:32,200 --> 00:14:34,080
It was next of next door faster.

233
00:14:34,090 --> 00:14:36,580
So basically fast likely wants to come here.

234
00:14:37,060 --> 00:14:45,150
OK, so in this case fast exist and the next hour fast exist so I can reach here so fast will come here.

235
00:14:46,530 --> 00:14:49,590
Now, when this loop will run again, so what will happen?

236
00:14:50,400 --> 00:14:51,820
Let's take one more example.

237
00:14:52,020 --> 00:14:56,390
OK, now fast exist and the next fast exist.

238
00:14:56,400 --> 00:14:59,900
So fast can take two jumps, fast can come here.

239
00:15:01,300 --> 00:15:06,910
Now, at this point, I will again check Flast exist and the next office does not exist, since the

240
00:15:06,910 --> 00:15:09,720
next afast does not exist, I will not go inside the loop.

241
00:15:09,730 --> 00:15:11,740
I will reach here and I will return false.

242
00:15:12,460 --> 00:15:17,110
OK, so basically, in short, this condition, because I'm going to take two jumps.

243
00:15:17,110 --> 00:15:19,000
So here I am digging doorjambs.

244
00:15:21,810 --> 00:15:24,990
So to avoid the segmentation fault, we have to put this condition.

245
00:15:25,590 --> 00:15:29,010
OK, try to think in this manner when I take only one jump.

246
00:15:29,010 --> 00:15:34,780
So when I write EQUASS the next toffy when I take only one jump.

247
00:15:34,800 --> 00:15:36,180
So what is my condition?

248
00:15:36,180 --> 00:15:37,570
My condition is very simple.

249
00:15:37,650 --> 00:15:39,240
While it is not external.

250
00:15:40,550 --> 00:15:46,220
OK, so this is my condition when I do quiz next of it, because if the value of it is nil.

251
00:15:47,500 --> 00:15:49,400
Then I will get segmentation fault.

252
00:15:49,420 --> 00:15:54,220
That's why I have only one condition, but now I am going to take two condition here.

253
00:15:54,220 --> 00:15:57,940
I have to condition first and the next of first.

254
00:15:59,860 --> 00:16:06,340
OK, so because I am going to take two jumps, so I have to take two conditions to avoid the segmentation

255
00:16:06,340 --> 00:16:07,980
fault or to avoid that entire matter.

256
00:16:08,290 --> 00:16:16,270
So basically this means wildfire's is not a question or basically while fast exist and the next of fast

257
00:16:16,270 --> 00:16:16,820
exist.

258
00:16:16,900 --> 00:16:19,570
OK, this is essentially this only.

259
00:16:22,130 --> 00:16:23,630
That was a short way of writing.

260
00:16:23,670 --> 00:16:23,990
OK?

261
00:16:26,420 --> 00:16:34,070
OK, so our goal is working, so there is no need to write this thing, you can simply write very fast

262
00:16:34,070 --> 00:16:36,020
exist and the next fast exist.

263
00:16:38,710 --> 00:16:45,130
OK, so to avoid segmentation fault, we have to avoid runtime error.

264
00:16:46,650 --> 00:16:50,780
OK, so that's why we have to two conditions here, OK?

265
00:16:51,080 --> 00:16:52,560
So I hope this court is fine.

266
00:16:52,570 --> 00:16:54,040
If you have any doubt, you can ask me.

267
00:16:54,060 --> 00:16:54,540
Thank you.

