1
00:00:00,720 --> 00:00:01,740
Welcome back.

2
00:00:01,740 --> 00:00:07,290
We have seen in the previous video that we can solve this question and find the duplicate number by

3
00:00:07,290 --> 00:00:09,480
converting this to a linked list question.

4
00:00:09,480 --> 00:00:13,980
So let's say this is the array which is given to us four, three, one, two and three.

5
00:00:13,980 --> 00:00:16,170
The indices are zero, one, two, three four.

6
00:00:16,170 --> 00:00:18,750
Now zero over here is pointing to four.

7
00:00:18,750 --> 00:00:19,080
All right.

8
00:00:19,080 --> 00:00:20,850
So I have zero pointing to four.

9
00:00:20,850 --> 00:00:22,530
And then we have index four over here.

10
00:00:22,530 --> 00:00:27,030
So among this four and this four I'm just writing four over here because we are treating these two as

11
00:00:27,030 --> 00:00:27,600
the same.

12
00:00:27,600 --> 00:00:29,220
So zero is pointing to four.

13
00:00:29,220 --> 00:00:30,990
Now four is pointing to three.

14
00:00:30,990 --> 00:00:32,220
So we write three over here.

15
00:00:32,220 --> 00:00:34,170
So three and this is three over here.

16
00:00:34,170 --> 00:00:35,550
Now three is pointing to two.

17
00:00:35,580 --> 00:00:36,630
So we have two over here.

18
00:00:36,630 --> 00:00:38,610
And then two is pointing to one.

19
00:00:38,610 --> 00:00:40,770
And one is again pointing to three.

20
00:00:40,770 --> 00:00:45,960
So we can see that we have a cycle over here which is starting at the node with value three.

21
00:00:45,960 --> 00:00:49,500
So that's why we can identify that three is the repeating number.

22
00:00:49,500 --> 00:00:51,180
Now let's go ahead and code this.

23
00:00:51,180 --> 00:00:55,050
So for this let's write a function and we can call it get duplicate.

24
00:00:58,070 --> 00:01:00,290
Now this function is going to take in the array.

25
00:01:00,290 --> 00:01:02,060
And let's call this array numb's.

26
00:01:02,950 --> 00:01:06,310
Now inside the function, let's have the hare and tortoise.

27
00:01:06,310 --> 00:01:09,370
So initially both of them are going to be equal to zero.

28
00:01:09,370 --> 00:01:12,790
So hare is equal to zero and tortoise is equal to zero.

29
00:01:15,460 --> 00:01:15,880
All right.

30
00:01:15,880 --> 00:01:19,690
This means that both of them are at index zero over here in the beginning.

31
00:01:20,290 --> 00:01:22,690
Now we are going to have a while loop.

32
00:01:22,690 --> 00:01:24,340
And we know that there is a loop.

33
00:01:24,340 --> 00:01:24,520
Right.

34
00:01:24,520 --> 00:01:27,100
So it's given that one number is repeating.

35
00:01:27,100 --> 00:01:29,080
So definitely there will be a loop.

36
00:01:29,080 --> 00:01:30,640
So we will keep looping.

37
00:01:30,640 --> 00:01:34,420
As long as the hare and tortoise have not met.

38
00:01:34,420 --> 00:01:36,700
And we will come out when they have met.

39
00:01:36,700 --> 00:01:42,370
And once they have met we will go ahead and proceed and identify where they have started, where the

40
00:01:42,370 --> 00:01:43,240
cycle starts.

41
00:01:43,240 --> 00:01:46,930
And for this we are using the Floyd's Hare and Tortoise algorithm.

42
00:01:46,930 --> 00:01:48,400
So let's go ahead.

43
00:01:48,400 --> 00:01:50,590
Now the hare is going to move two steps.

44
00:01:51,010 --> 00:01:51,790
Now over here.

45
00:01:51,790 --> 00:01:52,870
What is two steps.

46
00:01:52,870 --> 00:01:53,950
Let's try to observe it.

47
00:01:53,950 --> 00:01:56,770
It's one step is going from 0 to 4 right.

48
00:01:56,770 --> 00:02:00,790
So four over here is numb's at zero or numb's at hare.

49
00:02:01,210 --> 00:02:02,560
So Numb's at hare.

50
00:02:03,260 --> 00:02:04,580
This is one step right.

51
00:02:04,580 --> 00:02:05,750
So from 0 to 4.

52
00:02:05,750 --> 00:02:08,930
So numb's at here and here is equal to zero gives us four.

53
00:02:08,930 --> 00:02:10,040
So that's one step.

54
00:02:10,040 --> 00:02:14,780
Now we just have to move one more step so we can say numb's at this value over here.

55
00:02:14,780 --> 00:02:16,040
So numb's.

56
00:02:17,080 --> 00:02:18,700
At Numb's at here.

57
00:02:19,090 --> 00:02:20,710
So this is how the hair will move.

58
00:02:20,710 --> 00:02:21,640
Two steps.

59
00:02:21,640 --> 00:02:22,120
All right.

60
00:02:22,120 --> 00:02:26,590
So numb's at here is four and numb's at four gives us three.

61
00:02:26,590 --> 00:02:28,750
So the hair is going from 0 to 3.

62
00:02:28,750 --> 00:02:30,940
And the tortoise is moving only one step.

63
00:02:30,940 --> 00:02:34,480
So the tortoise is going to be equal to numb's at tortoise.

64
00:02:36,130 --> 00:02:40,030
So initially the tortoise is at zero and numb's at zero gives us four.

65
00:02:40,030 --> 00:02:41,230
So from 0 to 4.

66
00:02:41,230 --> 00:02:43,510
So the tortoise is moving one step.

67
00:02:43,630 --> 00:02:44,020
All right.

68
00:02:44,020 --> 00:02:45,820
So these keep moving in this manner.

69
00:02:45,820 --> 00:02:48,730
Now we will check if the hare and tortoise have met.

70
00:02:48,730 --> 00:02:51,490
So if hare is equal to tortoise.

71
00:02:52,710 --> 00:02:58,620
Now, the remaining part of whatever we're going to do in the while loop will only happen when the hare

72
00:02:58,620 --> 00:02:59,670
and tortoise meet.

73
00:02:59,670 --> 00:03:06,750
So when they meet, we should have a pointer established at the head and at the meeting point and in

74
00:03:06,750 --> 00:03:11,130
in the meeting point, as we have discussed in the question where we discussed the Floyd's Hare and

75
00:03:11,130 --> 00:03:14,580
tortoise algorithm, we will use the tortoise pointer itself.

76
00:03:14,580 --> 00:03:15,030
All right.

77
00:03:15,060 --> 00:03:16,410
Now once they have met.

78
00:03:16,410 --> 00:03:17,400
So let's have a pointer.

79
00:03:17,400 --> 00:03:19,080
So we'll say let pointer.

80
00:03:19,080 --> 00:03:21,570
And the pointer is going to point at the head.

81
00:03:21,570 --> 00:03:23,970
And the head of this linked list is index zero.

82
00:03:23,970 --> 00:03:25,650
So pointer is equal to zero.

83
00:03:25,650 --> 00:03:31,980
And now the pointer and the tortoise will keep moving one step as long as they have not met.

84
00:03:31,980 --> 00:03:34,410
So while pointer.

85
00:03:35,090 --> 00:03:37,040
Not equal to tortoise.

86
00:03:39,340 --> 00:03:43,030
As long as this is the case, the pointer will move one step.

87
00:03:43,030 --> 00:03:46,450
So pointer is going to be equal to numb's at pointer.

88
00:03:48,230 --> 00:03:50,690
And the Toto is also will move one step.

89
00:03:50,690 --> 00:03:53,540
So Toto is equal to Numb's at tortoise.

90
00:03:55,130 --> 00:03:59,930
All right, so once we come out of this while loop, the pointer and the tortoise have met.

91
00:03:59,930 --> 00:04:03,650
So over here they would be meeting at the starting point of the cycle.

92
00:04:03,650 --> 00:04:07,820
And then we can just return that particular value so we can just return the pointer.

93
00:04:08,750 --> 00:04:09,080
All right.

94
00:04:09,080 --> 00:04:10,850
And the pointer will be the value three.

95
00:04:10,850 --> 00:04:12,950
So this is how we can solve this question.

96
00:04:12,950 --> 00:04:14,600
Let's now test our code.

97
00:04:14,600 --> 00:04:17,780
Now for this let's call our function get duplicate.

98
00:04:17,780 --> 00:04:19,880
And let's pass in the same array over here.

99
00:04:22,720 --> 00:04:27,130
Now the array is four, three, one, two and three.

100
00:04:28,520 --> 00:04:31,610
Now let's run our code and see what's happening.

101
00:04:34,030 --> 00:04:34,300
All right.

102
00:04:34,300 --> 00:04:37,270
You can see we're getting three, which is the repeating value over here.

103
00:04:37,300 --> 00:04:39,400
Now let's just test a few more cases.

104
00:04:39,400 --> 00:04:43,390
What if we have, um, let's say we have more numbers.

105
00:04:43,390 --> 00:04:45,280
Let's say we have five also.

106
00:04:45,280 --> 00:04:47,110
And let's say this is the same thing.

107
00:04:47,110 --> 00:04:50,140
So again we run it and again it's working right now.

108
00:04:50,140 --> 00:04:53,680
What if we have um, uh, five repeating two times.

109
00:04:53,680 --> 00:04:55,390
So we should be getting five.

110
00:04:55,780 --> 00:04:57,310
And you can see we're getting five.

111
00:04:57,310 --> 00:04:58,870
So yes, our code is working.

112
00:04:58,870 --> 00:05:01,480
Now what about the space and time complexity?

113
00:05:01,480 --> 00:05:07,180
The space and time complexity is the same as the space and time complexity of the Floyd's Hare and Tortoise

114
00:05:07,180 --> 00:05:07,870
algorithm.

115
00:05:07,870 --> 00:05:10,570
Now over here you can see we keep moving, right?

116
00:05:10,570 --> 00:05:16,870
The tortoise is in the worst case will move completely throughout the cycle once it will not start looping,

117
00:05:16,870 --> 00:05:17,140
right.

118
00:05:17,140 --> 00:05:21,220
So before the tortoise goes ahead from one, they would have met.

119
00:05:21,220 --> 00:05:24,310
So we have discussed that in the Floyd's Hare and tortoise algorithm part.

120
00:05:24,310 --> 00:05:30,910
So the time complexity of this solution is going to be O of N, and the space complexity is constant

121
00:05:30,910 --> 00:05:31,240
space.

122
00:05:31,240 --> 00:05:34,840
Because we are not using any auxiliary space to come up with the solution.