1
00:00:00,710 --> 00:00:01,640
Welcome back.

2
00:00:01,640 --> 00:00:05,090
Now let's go ahead and discuss how we can approach this question.

3
00:00:05,090 --> 00:00:09,950
Now again, remember, the things that is mentioned in the question is that we are given an array and

4
00:00:09,950 --> 00:00:15,860
it has n plus one integers, and the integers in the array will be from one to n, and both of them

5
00:00:15,860 --> 00:00:20,270
are inclusive and there is exactly one integer repeating itself.

6
00:00:20,270 --> 00:00:24,680
Now let's try to develop some intuition regarding how we can solve this question.

7
00:00:24,680 --> 00:00:26,870
Now let's take an example for this.

8
00:00:26,870 --> 00:00:30,800
Let's say the array which is given to us is 14323.

9
00:00:30,800 --> 00:00:36,620
So you can see that the numbers over here are in the range 1 to 4 and one and four is included.

10
00:00:36,620 --> 00:00:38,780
And then over here we have five integers right.

11
00:00:38,780 --> 00:00:40,130
So n is equal to five.

12
00:00:40,130 --> 00:00:40,670
All right.

13
00:00:40,700 --> 00:00:42,830
Now let's go ahead and write the indices of the array.

14
00:00:42,830 --> 00:00:45,200
So we have 0123 and four.

15
00:00:45,200 --> 00:00:45,650
All right.

16
00:00:45,650 --> 00:00:47,210
So let's take this example over here.

17
00:00:47,210 --> 00:00:48,770
And let's make some space.

18
00:00:48,770 --> 00:00:49,310
All right.

19
00:00:49,310 --> 00:00:52,280
Now over here it's given that n is equal to five right.

20
00:00:52,280 --> 00:00:53,570
So n is equal to five.

21
00:00:53,570 --> 00:00:55,820
And again we're trying to develop our intuition.

22
00:00:55,820 --> 00:01:02,000
And the range of the integers in the given array is 1 to 4 because n is five over here.

23
00:01:02,000 --> 00:01:06,380
And we know that exactly one integer only will repeat itself.

24
00:01:06,380 --> 00:01:12,950
So this means that the numbers one, two, three, four have to occur exactly at least one time, right?

25
00:01:12,950 --> 00:01:15,410
Not exactly one time, at least one time.

26
00:01:15,410 --> 00:01:20,570
And one number has to occur one more time, which is the number which is repeated.

27
00:01:20,570 --> 00:01:25,280
So for example, over here you can see one two, three four occur and then three is repeated.

28
00:01:25,280 --> 00:01:25,610
Right.

29
00:01:25,610 --> 00:01:27,920
So that's the case because we need five numbers.

30
00:01:27,920 --> 00:01:30,320
And we can only use the numbers 1 to 4.

31
00:01:30,320 --> 00:01:31,580
So this will be four numbers.

32
00:01:31,580 --> 00:01:34,520
So to get to five numbers one of them has to repeat.

33
00:01:34,520 --> 00:01:35,690
So at least one of them.

34
00:01:35,690 --> 00:01:39,290
But in the question it is mentioned that exactly one is repeated.

35
00:01:39,290 --> 00:01:44,510
So we can be sure that 123, four will occur at least one time and one number will be repeated.

36
00:01:44,510 --> 00:01:46,850
And that's how we are getting five numbers.

37
00:01:46,850 --> 00:01:47,570
All right.

38
00:01:47,990 --> 00:01:51,560
Now again let's take a look at the indices over here which we have written.

39
00:01:51,560 --> 00:01:54,350
So we can see that in the indices we have zero.

40
00:01:54,350 --> 00:01:58,940
And then we have 1234 which is the same thing that we have over here as well.

41
00:01:58,940 --> 00:01:59,330
All right.

42
00:01:59,330 --> 00:02:04,490
Now let's try to use this information to come up with the method to solve this question.

43
00:02:04,490 --> 00:02:10,070
Now what if we treat these values over here in the array as indices itself.

44
00:02:10,070 --> 00:02:10,430
Right.

45
00:02:10,430 --> 00:02:15,710
Because we can see that the indices have the same values as the values that we have in the array.

46
00:02:15,710 --> 00:02:16,040
All right.

47
00:02:16,040 --> 00:02:19,910
So what if we treat these values over here as indices.

48
00:02:19,910 --> 00:02:26,660
If we do that then we can convert this question to a cycle detection question in a linked list.

49
00:02:26,660 --> 00:02:30,140
Let's try to draw it out and further develop our intuition.

50
00:02:30,140 --> 00:02:32,330
So again over here we have our example.

51
00:02:32,330 --> 00:02:33,830
Now this is zero.

52
00:02:33,830 --> 00:02:35,600
So let's just write this zero over here.

53
00:02:35,600 --> 00:02:37,640
And again what is it that we are trying to do.

54
00:02:37,670 --> 00:02:41,240
We are going to treat these values over here as indices itself.

55
00:02:41,240 --> 00:02:43,160
So zero is pointing to one.

56
00:02:43,160 --> 00:02:44,600
So we have the value one over here.

57
00:02:44,600 --> 00:02:46,550
So let's say zero is pointing to one.

58
00:02:46,550 --> 00:02:48,890
And at one we have the value four.

59
00:02:48,890 --> 00:02:49,100
Right.

60
00:02:49,100 --> 00:02:50,600
So zero is pointing to one.

61
00:02:50,600 --> 00:02:52,670
So this is one and this is one.

62
00:02:52,670 --> 00:02:55,280
So I'm treating these two as the one and the same thing.

63
00:02:55,280 --> 00:02:56,900
So zero is pointing to one.

64
00:02:56,900 --> 00:02:58,430
So let me just write that over here.

65
00:02:58,430 --> 00:03:00,350
So zero is pointing to one.

66
00:03:00,350 --> 00:03:02,450
And then over here we have one.

67
00:03:02,450 --> 00:03:05,030
And at one we have one is pointing to four.

68
00:03:05,030 --> 00:03:05,270
Right.

69
00:03:05,270 --> 00:03:06,620
So one is pointing to four.

70
00:03:06,620 --> 00:03:08,810
So this four is what I'm going to write over here.

71
00:03:08,810 --> 00:03:10,430
So one is pointing to four.

72
00:03:10,430 --> 00:03:12,290
And then over here we have four.

73
00:03:12,290 --> 00:03:14,480
And four is pointing to three.

74
00:03:14,480 --> 00:03:14,690
Right.

75
00:03:14,690 --> 00:03:16,130
So four is pointing to three.

76
00:03:16,130 --> 00:03:17,810
So let's write that three over here.

77
00:03:17,810 --> 00:03:20,360
Now at index three we have the value two.

78
00:03:20,390 --> 00:03:22,070
So three is pointing to two.

79
00:03:22,070 --> 00:03:22,430
All right.

80
00:03:22,430 --> 00:03:23,960
So three is pointing to two.

81
00:03:23,960 --> 00:03:26,930
And then at index two again we have the value three.

82
00:03:26,930 --> 00:03:28,610
So two is pointing to three.

83
00:03:28,610 --> 00:03:30,230
So we have a cycle over here.

84
00:03:31,190 --> 00:03:31,580
All right.

85
00:03:31,580 --> 00:03:35,960
Now you can see that this is our singly linked list and zero is pointing to one.

86
00:03:35,960 --> 00:03:40,190
One is pointing to four, four is pointing to three, three is pointing to two, and two is again pointing

87
00:03:40,220 --> 00:03:40,880
to three.

88
00:03:40,910 --> 00:03:44,780
Now again, one more interesting thing to observe over here zero is pointing to one.

89
00:03:44,780 --> 00:03:46,460
So I have these two ones right.

90
00:03:46,460 --> 00:03:48,620
So I'm just treating that as this one over here.

91
00:03:48,620 --> 00:03:50,630
And one is pointing to four.

92
00:03:50,630 --> 00:03:53,060
Again four is pointing to three.

93
00:03:53,060 --> 00:03:54,620
So this four and this four is one.

94
00:03:54,620 --> 00:03:56,870
And the same thing and four is pointing to three.

95
00:03:56,870 --> 00:03:58,340
So that's how we get this over here.

96
00:03:58,340 --> 00:04:01,580
So this is how we have converted this into a singly linked list.

97
00:04:01,580 --> 00:04:06,740
Now also notice that the cycle over here is starting at the value three over here.

98
00:04:06,740 --> 00:04:08,900
And that is the repeated value.

99
00:04:08,900 --> 00:04:10,880
We can see three is repeating two times.

100
00:04:10,880 --> 00:04:12,890
And that's the repeated number.

101
00:04:12,890 --> 00:04:14,810
So this is how we can solve this question.

102
00:04:14,810 --> 00:04:18,650
And again because we're just detecting a cycle in a linked list.

103
00:04:18,650 --> 00:04:22,910
And we know we have earlier discussed Floyd's hare and tortoise algorithm.

104
00:04:22,910 --> 00:04:27,260
So we know how to do this in constant space without modifying the array.

105
00:04:27,260 --> 00:04:27,410
Right.

106
00:04:27,410 --> 00:04:31,910
We are not modifying the array because we don't need to go ahead and even we don't need to use extra

107
00:04:31,910 --> 00:04:35,990
space because we're not going to create this singly linked list using extra space.

108
00:04:35,990 --> 00:04:36,350
Right?

109
00:04:36,350 --> 00:04:41,180
All we are going to do is that we are going to treat this array over here as a linked list.

110
00:04:41,180 --> 00:04:42,350
So what do I mean with that.

111
00:04:42,350 --> 00:04:43,790
So let's just discuss that as well.

112
00:04:43,790 --> 00:04:45,230
So over here I have zero.

113
00:04:45,680 --> 00:04:47,840
Now this one over here is nothing.

114
00:04:47,840 --> 00:04:50,720
But if I call this array let me just call this array Numb's.

115
00:04:50,720 --> 00:04:51,290
All right.

116
00:04:51,290 --> 00:04:55,280
So this one over here is nothing but numb's at zero.

117
00:04:56,060 --> 00:04:58,760
Now this for over here is nothing but numb's.

118
00:04:59,920 --> 00:05:01,690
At numb's.

119
00:05:01,840 --> 00:05:02,560
At zero.

120
00:05:02,560 --> 00:05:02,980
Right.

121
00:05:02,980 --> 00:05:07,780
Because numb's at zero gives me one and Numb's at one gives me four.

122
00:05:07,780 --> 00:05:11,920
So you can see we don't need to use up extra space and create the singly linked list.

123
00:05:11,920 --> 00:05:16,120
We can just treat the given array as a singly linked list in this manner.

124
00:05:16,150 --> 00:05:21,070
All right so one is numb's at zero and four is numb's at numb's at zero.

125
00:05:22,260 --> 00:05:22,650
All right.

126
00:05:22,650 --> 00:05:23,820
So let's now go ahead.

127
00:05:23,820 --> 00:05:25,080
Now we have established this.

128
00:05:25,080 --> 00:05:30,090
We have established how we can treat this question and convert this question into a cycle detection

129
00:05:30,090 --> 00:05:31,950
question in a singly linked list.

130
00:05:31,950 --> 00:05:37,110
And if we can just find where the cycle starts, we will be able to find the repeated number.

131
00:05:37,110 --> 00:05:43,170
Now, we have already discussed how we can find a cycle in a singly linked list using Floyd's Hare and

132
00:05:43,170 --> 00:05:44,280
tortoise algorithm.

133
00:05:44,280 --> 00:05:46,380
Let's quickly revise that over here.

134
00:05:46,380 --> 00:05:49,620
So we have the hare and tortoise both at the head initially.

135
00:05:49,620 --> 00:05:54,540
Now the hare is going to move two steps at a time, and the tortoise is going to move one step at a

136
00:05:54,540 --> 00:05:54,810
time.

137
00:05:54,810 --> 00:05:55,710
So let's see that.

138
00:05:55,710 --> 00:06:00,000
So the hare comes over here and the tortoise comes over here.

139
00:06:00,000 --> 00:06:05,400
In the next iteration the hare again moves one step and the the hare moves two steps and the tortoise

140
00:06:05,400 --> 00:06:06,300
moves one step.

141
00:06:06,300 --> 00:06:08,670
So the hare comes over here and the tortoise is over here.

142
00:06:08,670 --> 00:06:09,750
And this continues.

143
00:06:09,750 --> 00:06:09,930
Right.

144
00:06:09,930 --> 00:06:12,480
So again the tortoise moves and the hare moves.

145
00:06:12,480 --> 00:06:14,850
So the hair moves one step to two steps.

146
00:06:14,850 --> 00:06:16,470
So the hare is again over here itself.

147
00:06:16,470 --> 00:06:21,870
And in the next step you can see the tortoise and the hare both meet over here right.

148
00:06:21,870 --> 00:06:24,480
So the tortoise is over here and the hare is over here.

149
00:06:24,480 --> 00:06:25,860
So this is the meeting node.

150
00:06:25,890 --> 00:06:30,030
Now we know how we can find the beginning of the cycle if we know the meeting point.

151
00:06:30,030 --> 00:06:30,390
Right.

152
00:06:30,390 --> 00:06:34,920
So for this we will need a pointer at head at the head which is zero over here.

153
00:06:34,920 --> 00:06:37,050
So our pointer is going to point to zero.

154
00:06:37,050 --> 00:06:41,010
And then we are going to again use the tortoise pointer over here.

155
00:06:41,010 --> 00:06:47,310
And both the pointer and the tortoise is now going to move one step at a time till these two meet.

156
00:06:47,310 --> 00:06:48,780
So the pointer moves.

157
00:06:48,780 --> 00:06:51,330
And the hare or the tortoise also moves.

158
00:06:51,330 --> 00:06:55,020
And again the pointer moves and the tortoise moves.

159
00:06:55,020 --> 00:06:56,460
Again the pointer moves.

160
00:06:56,460 --> 00:06:57,870
And the tortoise also moves.

161
00:06:57,870 --> 00:07:00,690
And you can see both of them are meeting at three.

162
00:07:00,690 --> 00:07:03,180
And that is the beginning of the cycle.

163
00:07:03,180 --> 00:07:06,390
And again for our purpose this is the repeated value.

164
00:07:06,390 --> 00:07:08,370
So this is how we will solve this question.

165
00:07:08,370 --> 00:07:12,840
Now let's take a quick look at the time and space complexity of this solution.

166
00:07:12,840 --> 00:07:18,300
Now it's going to be the same time and space complexity which we have discussed for Floyd's Hare and

167
00:07:18,300 --> 00:07:19,260
Tortoise algorithm.

168
00:07:19,260 --> 00:07:25,770
Now over here, the maximum number of movements that the tortoise is going to make is going to be having

169
00:07:25,770 --> 00:07:27,180
the upper bound of n, right.

170
00:07:27,180 --> 00:07:31,200
Because we have seen that the tortoise before, the hare and tortoise is going to meet, they are not

171
00:07:31,200 --> 00:07:32,880
going to, um, come.

172
00:07:32,880 --> 00:07:33,180
Right.

173
00:07:33,180 --> 00:07:35,850
They're not the tortoise is not going to enter the cycle.

174
00:07:35,850 --> 00:07:41,160
So to identify their meeting point, we would want at most n operations.

175
00:07:41,160 --> 00:07:46,440
And then we will have another some operations which again can be treated as a multiple of n for the

176
00:07:46,440 --> 00:07:48,000
pointer and the tortoise to meet.

177
00:07:48,000 --> 00:07:50,610
So overall it's just a constant into n.

178
00:07:50,610 --> 00:07:54,060
So we can say the time complexity is of the order of n right.

179
00:07:54,060 --> 00:07:56,250
Because again we have to identify the beginning point.

180
00:07:56,250 --> 00:08:01,170
And the space complexity is constant space because you're not using up any extra space.