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.