1
00:00:00,740 --> 00:00:01,670
Welcome back, everyone.

2
00:00:01,940 --> 00:00:07,310
So hopefully you got a chance to try and cut out Floyd's hair and tortoise algorithm yourself, let's

3
00:00:07,310 --> 00:00:09,820
just do it together right now here.

4
00:00:09,830 --> 00:00:15,020
What we're going to do is we need to instantiate the hare pointer and the tortoise pointer, which are,

5
00:00:15,020 --> 00:00:20,780
of course, the fast and slow pointers so we can instantiate them as hare and tortoise just because

6
00:00:20,780 --> 00:00:26,920
it's more clear since it is the hare and tortoise algorithm and they both instantiate at the head value.

7
00:00:27,530 --> 00:00:31,010
So tortoise is also going to start at the head.

8
00:00:32,380 --> 00:00:38,950
And they, of course, are pointers and what we want to do is we want to loop over and over until either

9
00:00:38,950 --> 00:00:47,020
the hare and the tortoise overlap at some less node or the hare is pointing at the tail.

10
00:00:47,350 --> 00:00:50,710
Now, the reason why we want to make sure the hare is the one that checks for the tail is because the

11
00:00:50,710 --> 00:00:52,630
hare is the one that moves faster.

12
00:00:52,810 --> 00:00:57,280
So it will reach the tail before the tortoise if a tail does exist.

13
00:00:57,970 --> 00:01:03,640
So here's what we're going to say, is we are going to use a while loop, accept any condition here.

14
00:01:03,640 --> 00:01:04,300
Doesn't matter.

15
00:01:04,310 --> 00:01:08,140
We want to loop what instead we want is we want to loop.

16
00:01:08,140 --> 00:01:15,430
While true, what this means is that this while loop will continually run unless any code inside calls

17
00:01:15,460 --> 00:01:21,610
the brake keyword brake will break out of the wire loop as a whole and end the while iterations.

18
00:01:21,820 --> 00:01:27,070
But we want to keep looping our while loop until we have found either of our two cases.

19
00:01:27,100 --> 00:01:32,710
So this is why we use while true, what we're going to say here is we are going to advance the hare

20
00:01:32,710 --> 00:01:34,780
and the tortoise each one step forward.

21
00:01:35,910 --> 00:01:39,420
So here here is equal to hair next.

22
00:01:40,720 --> 00:01:44,770
And tortas is also equal to tortas dot next.

23
00:01:48,040 --> 00:01:53,020
Now that they've both advanced one step, we need to think and consider that edge case I was mentioning

24
00:01:53,020 --> 00:01:56,570
where the link were received does not have a cycle in it.

25
00:01:57,130 --> 00:02:02,470
The other thing we have to consider is what happens if the linked list we receive is a single note the

26
00:02:02,470 --> 00:02:08,770
moment we advanced our hair next, we are technically pointing to null because if we have a single node,

27
00:02:08,770 --> 00:02:10,680
then this nodes next value is null.

28
00:02:10,900 --> 00:02:15,900
So we have to check for both cases where we have a single node, but also where we have a tail.

29
00:02:16,300 --> 00:02:20,110
So how we can check for that is we can say that if the hair.

30
00:02:21,020 --> 00:02:22,970
Pointer is equal to No.

31
00:02:24,470 --> 00:02:30,620
So that would be this case right here or the hardcourt next.

32
00:02:32,210 --> 00:02:33,260
Is pointing to not.

33
00:02:34,560 --> 00:02:36,270
Which means that we have a tail value.

34
00:02:37,360 --> 00:02:44,290
Then we want to return false from our entire function, because clearly in both of these cases, there

35
00:02:44,320 --> 00:02:45,490
is no cycle.

36
00:02:46,510 --> 00:02:53,720
If this is not the case, then we want to advance the hair one more step so hair equals hair done next.

37
00:02:54,550 --> 00:03:00,760
So through this, we have now advanced the hair, the two steps and the tortoise, the one.

38
00:03:01,850 --> 00:03:07,040
Once we've advanced these steps, we now want to check if the hare and the tortoise are now overlapping

39
00:03:07,430 --> 00:03:11,840
and we can do this with a simple if check that says if the tortoise.

40
00:03:13,240 --> 00:03:21,360
Is equal to the hair, if they're both pointing at the same little node, then we want to break.

41
00:03:21,760 --> 00:03:26,470
So here we can just right break, which is a bit of JavaScript shorthand.

42
00:03:26,800 --> 00:03:28,870
We don't have to add our braces.

43
00:03:30,410 --> 00:03:37,250
The moment that we break, we now know the hare and the tortoise are both pointing to that meeting point

44
00:03:37,250 --> 00:03:37,740
listener.

45
00:03:38,330 --> 00:03:44,600
So what we want to do now is instantiate the two pointers that will traverse together to see if they

46
00:03:44,600 --> 00:03:47,980
can find the list node that represents the start of the cycle.

47
00:03:48,590 --> 00:03:57,260
And here we can just let two pointers, one called P1, which instantiates at the head value and P2,

48
00:03:57,260 --> 00:03:59,860
which instantiates at either the hare, the tortoise.

49
00:03:59,870 --> 00:04:00,470
It doesn't matter.

50
00:04:00,500 --> 00:04:02,690
They both point to the same value.

51
00:04:02,960 --> 00:04:05,810
So here I'm going to say that it points to the tortoise.

52
00:04:06,350 --> 00:04:12,570
And now that we have one MP two, we want to advance them together until they meet.

53
00:04:12,740 --> 00:04:14,540
So we're going to use another while loop here.

54
00:04:15,140 --> 00:04:22,010
And we're going to say while P one does not equal P two, then we want them to keep advancing.

55
00:04:22,700 --> 00:04:25,220
So P one is just equal to P one.

56
00:04:25,430 --> 00:04:29,870
Next P two is equal to P to Dot next.

57
00:04:31,880 --> 00:04:39,110
And once this while loop breaks, meaning that one MP to have overlapped, as we saw, this is the list

58
00:04:39,110 --> 00:04:44,510
node that represents the start of our cycle so we can just return either one or two.

59
00:04:44,660 --> 00:04:45,890
So I'm going to turn one.

60
00:04:47,520 --> 00:04:55,410
And that is the Floyds Hare and Tortoise algorithm, so looking at this, we see that what we were doing

61
00:04:55,410 --> 00:05:01,230
is we are iterating through and times as far as our time complexity goes.

62
00:05:01,380 --> 00:05:09,240
So time complexity is still going to be oh, of end because despite the fact that the hare moves two

63
00:05:09,240 --> 00:05:14,400
steps forward, meaning that there's a chance that it might loop over and over again within the cycle

64
00:05:15,000 --> 00:05:17,540
and touch multiple nodes over and over again.

65
00:05:18,090 --> 00:05:24,390
Technically speaking, it's all happening within one while loop, which means that this iteration,

66
00:05:24,750 --> 00:05:32,280
despite the hare touching possibly the same nodes more than one time, the code is only iterating nine

67
00:05:32,280 --> 00:05:36,210
times until it reaches the meeting point.

68
00:05:36,240 --> 00:05:41,400
In fact, it's less than an hour turtle pointer or our tortoise pointer, which moves slower, will

69
00:05:41,400 --> 00:05:44,490
not ever step in a loop in the cycle.

70
00:05:45,430 --> 00:05:50,500
So now that we know that, then we understand that our time complexity is then.

71
00:05:52,040 --> 00:05:57,110
As for our space complexity, all we instantiate are four different pointers, which always point to

72
00:05:57,110 --> 00:05:58,010
a single value.

73
00:05:58,250 --> 00:06:03,290
So this means that we end up with a space complexity of o of one.

74
00:06:04,340 --> 00:06:10,250
So here we see that this is why it's such a great solution, because we've managed to bring our space

75
00:06:10,250 --> 00:06:14,520
down as much as possible and we've managed to keep our time out of end.

76
00:06:14,990 --> 00:06:19,730
It's also a really easy algorithm to reason about, and it's relatively simple to implement.

77
00:06:19,730 --> 00:06:25,820
The only trick here in terms of the technical implementation was understanding that we had to do, while

78
00:06:25,820 --> 00:06:32,240
true, to run our loop, because if we took our condition that we needed in order to break knowing when

79
00:06:32,600 --> 00:06:40,820
this tortoise was equal to the hair, we had a value of our tortoise and hare equal to the node that

80
00:06:40,820 --> 00:06:43,280
we knew indicated the meeting point.

81
00:06:44,150 --> 00:06:48,800
We could not have done this with the traditional method that we were used to while writing a while loop

82
00:06:48,800 --> 00:06:54,890
where we put the condition inside of the actual logic, because the reason why we can't do that is that

83
00:06:54,890 --> 00:07:00,080
when we instantiate the function for the first time, hare and tortoise are both pointing to the head,

84
00:07:00,350 --> 00:07:05,150
which means that this condition is equal when our while loop runs.

85
00:07:05,150 --> 00:07:10,790
Initially, the only way that we were able to write this conditional while true loop and have a break

86
00:07:10,790 --> 00:07:16,130
while aiming for the exact same goal, which is making sure that one of these pointers or both of these

87
00:07:16,130 --> 00:07:22,430
pointers in this case, we're pointing to the appropriate less note that we were looking for was by

88
00:07:22,430 --> 00:07:25,370
doing it like so where we had a while.

89
00:07:25,370 --> 00:07:30,470
True, that would then break because we knew the moment that tortoise and the hare were equal after

90
00:07:30,470 --> 00:07:34,670
running through a certain amount of iterations that we're unsure of what that would be.

91
00:07:35,710 --> 00:07:42,190
The moment that they were equal, we knew that immediately we had our meeting point listener, so this

92
00:07:42,190 --> 00:07:43,830
was really the only technical trick.

93
00:07:43,840 --> 00:07:50,680
But now that we know what to do, if we ever encounter any cycle detection in a link less question as

94
00:07:50,680 --> 00:07:57,250
either the main question or as the sub problem or a potential sub problem, we know exactly what to

95
00:07:57,250 --> 00:07:59,050
do in order to detect the cycle.

96
00:07:59,800 --> 00:08:04,210
Now, this is actually the exact same for doubly linked list as it is for singly linked lists.

97
00:08:04,210 --> 00:08:06,830
The addition of the previous pointer doesn't change anything.

98
00:08:06,880 --> 00:08:08,350
This method still works.

99
00:08:09,360 --> 00:08:15,420
So we're at the point now where you might be wondering why is it that this method works if that question

100
00:08:15,420 --> 00:08:16,470
lingers in your head?

101
00:08:16,680 --> 00:08:23,460
There is a optional video that I'm going to show you in the next lesson that will prove why this method

102
00:08:23,610 --> 00:08:24,470
is effective.

103
00:08:24,660 --> 00:08:28,860
It does involve math and it does involve deriving functions.

104
00:08:28,860 --> 00:08:32,070
So if you are interested in that, there's no need to watch.

105
00:08:32,070 --> 00:08:33,480
It is entirely optional.

106
00:08:34,020 --> 00:08:40,580
But I will say that you don't ever really need to know the proof when it comes to your interview.

107
00:08:40,590 --> 00:08:42,810
It's really just for your own curiosity.

108
00:08:42,970 --> 00:08:45,350
So if you're curious, definitely watch it.

109
00:08:45,360 --> 00:08:46,700
I'm going to do it in the next video.

110
00:08:46,980 --> 00:08:51,060
If not, you can easily move on to the next lesson after the next video.

111
00:08:51,510 --> 00:08:53,750
So I will see you in whichever one you choose.