1
00:00:00,510 --> 00:00:01,500
Welcome back.

2
00:00:01,500 --> 00:00:05,010
In this video, let's try to think how we can solve this question.

3
00:00:05,010 --> 00:00:08,790
Now let's say the linked list which is given to us is this one over here.

4
00:00:08,790 --> 00:00:12,390
So you can see there is a cycle right which is starting at node three.

5
00:00:12,390 --> 00:00:16,050
Now what would be the brute force method of solving this question.

6
00:00:16,050 --> 00:00:18,600
We could use a hash table for example.

7
00:00:18,600 --> 00:00:25,740
And as we go along the linked list using the dot next operation, we will keep storing the nodes that

8
00:00:25,740 --> 00:00:26,670
we have visited.

9
00:00:26,670 --> 00:00:31,950
And then we will just see whether we are coming back to a node which was already visited previously.

10
00:00:31,950 --> 00:00:34,290
So that would be the brute force way of solving it.

11
00:00:34,290 --> 00:00:35,940
So let's just walk through it.

12
00:00:35,940 --> 00:00:37,980
Let's say the hash table is visited.

13
00:00:37,980 --> 00:00:41,100
We call the hash table visited and it's initially empty.

14
00:00:41,130 --> 00:00:42,630
Now we are at the head.

15
00:00:42,630 --> 00:00:44,220
So we have visited this node.

16
00:00:44,220 --> 00:00:45,870
So we say that one.

17
00:00:45,870 --> 00:00:48,210
And then that's the key and the value is true.

18
00:00:48,210 --> 00:00:50,580
And then we use the next operator.

19
00:00:50,580 --> 00:00:52,650
So we come to the next node which is two.

20
00:00:52,650 --> 00:00:54,330
And we mark it as visited.

21
00:00:54,330 --> 00:00:55,680
And then we go to three.

22
00:00:55,680 --> 00:00:56,880
We mark it as visited.

23
00:00:56,880 --> 00:00:59,700
And we keep doing this till we get to nine.

24
00:00:59,700 --> 00:01:04,140
So all these nodes are going to be marked as visited in our visited hash table.

25
00:01:04,140 --> 00:01:09,450
And then when we again you follow the next pointer, we are going to come back over here, which is

26
00:01:09,450 --> 00:01:10,410
at node three.

27
00:01:10,410 --> 00:01:14,160
And at that point we will see that it is already there in our hash table.

28
00:01:14,160 --> 00:01:15,720
So it's there already over here.

29
00:01:15,720 --> 00:01:21,450
And therefore we know that there is a cycle or this, this linked list over here has a cycle and we

30
00:01:21,450 --> 00:01:23,280
can just return the node three.

31
00:01:23,280 --> 00:01:26,250
So this would be the brute force method of solving this question.

32
00:01:26,250 --> 00:01:29,730
And what would be the complexity analysis of this question.

33
00:01:29,730 --> 00:01:35,400
The time complexity would be O of N because we are traversing every node in the linked list.

34
00:01:35,400 --> 00:01:37,950
And let's say there are n nodes in the given linked list.

35
00:01:37,950 --> 00:01:44,100
And the space complexity also is going to be o of n, because in the hash table we are going to store

36
00:01:44,100 --> 00:01:45,450
all the n nodes.

37
00:01:45,450 --> 00:01:51,360
So the time complexity is O of n, and the space complexity for this solution is also O of n.

38
00:01:51,360 --> 00:01:55,710
Now let's try to think whether we can solve this in constant space.

39
00:01:56,310 --> 00:01:58,650
So again this is the linked list that we have.

40
00:01:58,650 --> 00:02:02,190
And we are trying to solve this in constant space.

41
00:02:02,190 --> 00:02:06,600
That is, we're going to try to check whether there is a cycle in the linked list, which is given to

42
00:02:06,600 --> 00:02:07,950
us in constant space.

43
00:02:07,950 --> 00:02:14,190
Now for this, we are going to use a very famous algorithm which is called Floyd's Tortoise and Hare

44
00:02:14,190 --> 00:02:14,940
algorithm.

45
00:02:14,940 --> 00:02:17,640
Now let's try to understand this beautiful algorithm.

46
00:02:17,640 --> 00:02:19,620
So let's make some space over here.

47
00:02:19,620 --> 00:02:21,810
Now we're going to use two pointers.

48
00:02:21,810 --> 00:02:23,730
Let's call it t and h.

49
00:02:23,730 --> 00:02:26,970
So T stands for tortoise and H stands for hare.

50
00:02:26,970 --> 00:02:30,720
Now tortoise and the hare both are at the head at this moment.

51
00:02:30,750 --> 00:02:36,720
Now the tortoise is going to just move one step at a time, but the hare is going to move two steps

52
00:02:36,720 --> 00:02:37,350
at a time.

53
00:02:37,350 --> 00:02:39,780
So let's trace how they are going to move over here.

54
00:02:39,780 --> 00:02:44,910
So the tortoise moves one node and the hare comes over here because it moves two nodes.

55
00:02:44,910 --> 00:02:48,960
Again the tortoise moves one node and the hare moves two nodes.

56
00:02:48,960 --> 00:02:50,340
We keep doing that.

57
00:02:50,340 --> 00:02:54,780
So the tortoise again moves one node and the hare has moved again two nodes.

58
00:02:54,780 --> 00:02:57,060
And then the tortoise again moves one node.

59
00:02:57,060 --> 00:03:00,810
And the hare has reached over here by moving two nodes.

60
00:03:00,810 --> 00:03:02,400
And we keep continuing this.

61
00:03:02,400 --> 00:03:04,770
So the hare is again going to move two nodes.

62
00:03:04,770 --> 00:03:07,230
So after moving one node the hare is over here.

63
00:03:07,230 --> 00:03:11,430
And then after moving the second node the hare is going to reach node four.

64
00:03:11,430 --> 00:03:13,410
And the tortoise moves one node.

65
00:03:13,410 --> 00:03:15,210
And then we again continue this.

66
00:03:15,210 --> 00:03:18,990
The tortoise is going to one node and the hare moves these two nodes.

67
00:03:18,990 --> 00:03:24,690
And next in the next step you can see that the tortoise is also reaching at node eight.

68
00:03:24,690 --> 00:03:27,360
And the hare also is reaching at node eight.

69
00:03:27,360 --> 00:03:28,770
So they have met.

70
00:03:28,770 --> 00:03:33,000
And therefore we know that there is a cycle in the given linked list.

71
00:03:33,000 --> 00:03:39,300
If there was no cycle, if there was no cycle, then the hare would have reached null, right?

72
00:03:39,300 --> 00:03:43,860
So if there was no cycle, the hare would have reached the end the null pointer, right?

73
00:03:43,860 --> 00:03:47,850
So at that point we would have known that there is no cycle and we would have stopped.

74
00:03:47,850 --> 00:03:50,910
But in this case we can see that because there is a cycle.

75
00:03:50,910 --> 00:03:56,040
Finally they are meeting and therefore we can be sure that yes, there is a cycle in the given linked

76
00:03:56,040 --> 00:03:56,550
list.

77
00:03:56,550 --> 00:03:57,120
All right.

78
00:03:57,150 --> 00:04:01,290
Now let's now also see how to find where the cycle begins.

79
00:04:01,290 --> 00:04:06,000
Because in the question it's mentioned that if there is a cycle, we have to return the node where the

80
00:04:06,000 --> 00:04:08,550
cycle begins, which is this node over here.

81
00:04:08,550 --> 00:04:10,170
So let's see how we can find this.

82
00:04:10,170 --> 00:04:13,260
So we are going to have one pointer which is at the head.

83
00:04:13,260 --> 00:04:18,780
And then there is going to be one more pointer which is where the the hare and the tortoise have met.

84
00:04:18,780 --> 00:04:21,510
Or we can just use the tortoise pointer itself.

85
00:04:21,510 --> 00:04:27,210
Now what we is going to happen is these two pointers are going to move one step at a time.

86
00:04:27,210 --> 00:04:28,410
So let's move them.

87
00:04:28,410 --> 00:04:30,780
So this pointer is moving one step.

88
00:04:30,780 --> 00:04:33,390
And this pointer moved one step and reached over here.

89
00:04:33,390 --> 00:04:36,450
Now again both of them are going to move one step.

90
00:04:36,450 --> 00:04:38,790
And you can see that they are meeting over here right.

91
00:04:38,790 --> 00:04:41,280
So they are meeting where the cycle begins.

92
00:04:41,280 --> 00:04:45,090
So that's how we can find the node where the cycle begins.

93
00:04:45,090 --> 00:04:47,550
And we can just return this node over here.

94
00:04:47,550 --> 00:04:49,560
So this is how we can solve this question.

95
00:04:49,560 --> 00:04:53,730
Now let's take a look at the complexity analysis of this method of solving this question.

96
00:04:53,730 --> 00:04:59,880
Again the time complexity is going to be o of n because Max we are going to do n iterations.

97
00:05:00,320 --> 00:05:05,600
Now you can notice that even though the hair is moving two times two nodes at a time, this is going

98
00:05:05,600 --> 00:05:07,970
to have max n iterations, right?

99
00:05:07,970 --> 00:05:11,270
Because the tortoise will not do more than n moves.

100
00:05:11,300 --> 00:05:12,470
Now why is that?

101
00:05:12,470 --> 00:05:15,440
So let's try to develop an intuition regarding this.

102
00:05:15,830 --> 00:05:20,690
Now let's say when the tortoise is over here, the hair is going to be over here.

103
00:05:20,690 --> 00:05:21,020
Right?

104
00:05:21,020 --> 00:05:23,720
So the tortoise moves from here to here and then to here.

105
00:05:23,720 --> 00:05:25,220
So it makes two steps.

106
00:05:25,220 --> 00:05:29,120
So the hair is going to move from here to here and then from here to here.

107
00:05:29,120 --> 00:05:33,350
So the hair is at node five and the tortoise is at node three.

108
00:05:33,350 --> 00:05:33,920
All right.

109
00:05:33,950 --> 00:05:40,610
Now if the hair let's say let's say the tortoise let's say the tortoise has to move x moves so that

110
00:05:40,610 --> 00:05:41,360
they meet.

111
00:05:41,390 --> 00:05:48,620
Now if the tortoise is doing x moves and they are meeting after these x moves, then we can say that

112
00:05:48,620 --> 00:05:55,610
the hair will do n minus two moves plus x minus two, where n minus two is the number of nodes in this

113
00:05:55,610 --> 00:05:56,000
cycle.

114
00:05:56,000 --> 00:05:56,180
Right.

115
00:05:56,180 --> 00:06:01,430
So if there are n nodes total we are just removing these two nodes which are not part of the cycle.

116
00:06:01,430 --> 00:06:03,080
So that's n minus two over here.

117
00:06:03,230 --> 00:06:08,090
And then you have x minus two over here because the hair is two nodes ahead of the tortoise.

118
00:06:08,090 --> 00:06:12,560
So let's just try to understand this n minus two is the hair is doing one cycle.

119
00:06:13,100 --> 00:06:16,250
And then after one cycle the hair is going to get back to here.

120
00:06:16,250 --> 00:06:19,100
And then again it has to move from here.

121
00:06:19,100 --> 00:06:21,020
From here the there are x moves right.

122
00:06:21,020 --> 00:06:22,700
So wherever the tortoise reaches.

123
00:06:22,700 --> 00:06:28,760
So the difference between this point and wherever the tortoise reaches is going to be x minus two.

124
00:06:28,790 --> 00:06:33,590
Because you can see after doing one cycle the hair is ahead of the tortoise by two nodes.

125
00:06:33,590 --> 00:06:34,130
All right.

126
00:06:34,130 --> 00:06:41,000
So we have seen that when the tortoise moves x nodes the hair is going to do n minus two plus x minus

127
00:06:41,000 --> 00:06:41,510
two nodes.

128
00:06:41,510 --> 00:06:46,760
So again we are just trying to develop an intuition why the tortoise will not do more than n moves.

129
00:06:46,760 --> 00:06:52,640
Now we know that the hair is moving twice at the speed of the tortoise, so we can say that two times

130
00:06:52,640 --> 00:06:55,670
into x will be equal to what we have over here.

131
00:06:55,670 --> 00:07:01,880
So we can say n minus two plus x minus two is equal to two x or x is equal to n minus four.

132
00:07:01,880 --> 00:07:02,150
Right.

133
00:07:02,150 --> 00:07:03,860
So x is equal to n minus four.

134
00:07:03,860 --> 00:07:05,960
And that's how we know that they are meeting over here.

135
00:07:05,960 --> 00:07:06,200
Right.

136
00:07:06,200 --> 00:07:09,050
N is equal to nine nine minus four is equal to five.

137
00:07:09,050 --> 00:07:11,360
And you have 1234 and five.

138
00:07:11,360 --> 00:07:13,310
So that's how they are meeting over here.

139
00:07:13,310 --> 00:07:17,000
You can see that the tortoise is not going to do more than n moves.

140
00:07:17,000 --> 00:07:20,270
That is the tortoise is not going to cycle again over here.

141
00:07:20,270 --> 00:07:20,690
Right.

142
00:07:20,690 --> 00:07:26,780
So the hare might do multiple cycles depending on the length of the cycle and how how big this initial

143
00:07:26,780 --> 00:07:27,260
part is.

144
00:07:27,260 --> 00:07:29,810
But the tortoise is not going to do any cycle.

145
00:07:29,810 --> 00:07:31,940
So the tortoise will do max n moves.

146
00:07:31,940 --> 00:07:35,030
Let's say the hare somehow was here when the tortoise reached over here.

147
00:07:35,030 --> 00:07:40,280
In that case we will have n minus two plus x minus one, right?

148
00:07:40,280 --> 00:07:41,750
Because there is just a difference of one.

149
00:07:41,750 --> 00:07:44,240
And we would have get x is equal to n minus three.

150
00:07:44,240 --> 00:07:47,600
And in that case n minus three is nine minus three which is six.

151
00:07:47,600 --> 00:07:48,890
And they would have met over here.

152
00:07:48,890 --> 00:07:50,030
So that's the worst case right.

153
00:07:50,030 --> 00:07:53,750
So in this worst case also the tortoise would have just done n moves.

154
00:07:53,780 --> 00:07:54,320
All right.

155
00:07:54,320 --> 00:07:57,800
So the time complexity of this solution is still O of n.

156
00:07:57,800 --> 00:08:00,680
Now what about the space complexity of this solution.

157
00:08:00,680 --> 00:08:08,240
Now remember we tried to get to a better solution because the previous solution was taking O of n space.

158
00:08:08,240 --> 00:08:13,640
But in this case we are not using any extra space or any auxiliary space.

159
00:08:13,640 --> 00:08:17,450
And therefore the space complexity of this solution is O of one.

160
00:08:17,450 --> 00:08:21,410
So the time complexity is O of n and the space complexity is O of one.

161
00:08:21,410 --> 00:08:24,920
And in the next video let's try to understand why.

162
00:08:24,920 --> 00:08:30,740
If we have a pointer over here and the pointer at the place where these people are meeting, and if

163
00:08:30,740 --> 00:08:35,870
we keep moving the pointers one at a time, why is it that they will again meet at the starting point

164
00:08:35,870 --> 00:08:36,650
of the cycle?

165
00:08:36,650 --> 00:08:39,710
So let's look at the proof for this in the next video.