1 00:00:01,040 --> 00:00:02,060 Welcome back. 2 00:00:02,060 --> 00:00:07,190 Now, I have just visualized this over here, the, uh, the graph that we just now dealt with. 3 00:00:07,190 --> 00:00:09,260 So let me just make some space over here. 4 00:00:09,260 --> 00:00:11,750 And we have these prerequisites. 5 00:00:11,750 --> 00:00:16,430 For example we have two comma zero over here which is this edge from 0 to 2. 6 00:00:16,430 --> 00:00:18,920 And then we have one comma zero over here which is this one. 7 00:00:18,920 --> 00:00:21,200 From one we have we are moving towards two. 8 00:00:21,200 --> 00:00:21,380 Right. 9 00:00:21,380 --> 00:00:23,300 So let me just take a pen. 10 00:00:23,900 --> 00:00:24,200 All right. 11 00:00:24,200 --> 00:00:25,730 So over here we have two comma zero. 12 00:00:25,730 --> 00:00:27,230 So that's from 0 to 2. 13 00:00:27,230 --> 00:00:29,570 Then we have one comma zero over here which is this one. 14 00:00:29,570 --> 00:00:29,840 Right. 15 00:00:29,840 --> 00:00:31,790 So that's going from 0 to 1. 16 00:00:31,790 --> 00:00:33,410 And then we have two comma one. 17 00:00:33,410 --> 00:00:35,720 So that is this link from 1 to 2 etc.. 18 00:00:35,720 --> 00:00:36,140 All right. 19 00:00:36,140 --> 00:00:39,740 So this is the visualization of these prerequisites. 20 00:00:39,740 --> 00:00:40,850 So this is our graph. 21 00:00:40,850 --> 00:00:43,010 And at this point n is equal to five. 22 00:00:43,010 --> 00:00:49,280 Now the adjacency list we will get back over here right the adjacency list and the indegree array for 23 00:00:49,280 --> 00:00:50,210 this particular graph. 24 00:00:50,210 --> 00:00:53,060 So it's going to look like this for index zero. 25 00:00:53,060 --> 00:00:56,660 For node zero we have two vertices which are going out right. 26 00:00:56,660 --> 00:00:57,920 So we have one over here and two. 27 00:00:57,920 --> 00:00:59,480 So we have one comma two over here. 28 00:00:59,480 --> 00:01:02,300 And for one we just have a connection towards two. 29 00:01:02,300 --> 00:01:06,920 So just two over here for two we have just one outgoing connection to three. 30 00:01:06,920 --> 00:01:10,280 So we have three over here for three we have four and for four we have two. 31 00:01:10,310 --> 00:01:11,990 So this is the adjacency list. 32 00:01:11,990 --> 00:01:15,410 And the indegree array is going to be like this for index zero. 33 00:01:15,410 --> 00:01:17,960 That is for this vertex we have nothing coming in. 34 00:01:17,960 --> 00:01:20,660 So it's going to have an indegree factor of zero. 35 00:01:20,690 --> 00:01:23,750 For vertex one it has an indegree factor of one. 36 00:01:23,750 --> 00:01:27,950 For two it has an indegree factor of three because one, two and three. 37 00:01:27,950 --> 00:01:28,250 Right. 38 00:01:28,250 --> 00:01:30,830 So there are three edges coming into it. 39 00:01:30,830 --> 00:01:33,770 And then for three it has an indegree factor of one. 40 00:01:33,770 --> 00:01:36,350 And for four it has an indegree factor of one. 41 00:01:36,350 --> 00:01:37,250 So let's proceed. 42 00:01:37,250 --> 00:01:42,110 So we are inside this function and we have got our adjacency list and the Indegree array. 43 00:01:42,110 --> 00:01:49,460 Now we come over here and for I is equal to zero I less than five I plus plus we are going to loop through 44 00:01:49,460 --> 00:01:51,260 this array over here the indegree array. 45 00:01:51,260 --> 00:01:51,680 Right. 46 00:01:51,680 --> 00:01:55,760 And whenever the indegree factor is zero we are going to push it to our stack. 47 00:01:55,760 --> 00:01:57,620 So let's have our stack over here. 48 00:01:57,710 --> 00:02:02,150 Now we see that the indegree factor is zero only for this vertex right. 49 00:02:02,150 --> 00:02:04,250 So we're just going to push this to our stack. 50 00:02:04,250 --> 00:02:06,650 And then we initialize count to be zero. 51 00:02:06,650 --> 00:02:08,330 So count is now equal to zero. 52 00:02:09,490 --> 00:02:12,370 Now we see that we our stack is not empty. 53 00:02:12,400 --> 00:02:14,020 We have something in the stack. 54 00:02:14,020 --> 00:02:17,950 So we come inside the while loop and then we are just going to pop from the stack. 55 00:02:17,950 --> 00:02:21,220 So we take this out and we increment count over here. 56 00:02:23,120 --> 00:02:27,860 Now over here, we are going to find the neighbors of the current vertex, which is zero. 57 00:02:27,860 --> 00:02:30,710 So for this we make use of the adjacency list. 58 00:02:30,710 --> 00:02:35,150 And adjacency list at zero gives us this array over here which is one comma two. 59 00:02:35,150 --> 00:02:36,680 So for these two right. 60 00:02:36,680 --> 00:02:38,300 So initially I is going to be zero. 61 00:02:38,300 --> 00:02:41,510 Then I is going to take the value of one because the length over here is two. 62 00:02:41,540 --> 00:02:44,420 So for I is equal to zero I less than two I plus plus. 63 00:02:44,420 --> 00:02:49,190 So we come inside and we find the neighbor at index zero initially which is one. 64 00:02:49,190 --> 00:02:49,670 Right. 65 00:02:49,670 --> 00:02:55,820 And we are going to decrement the indegree factor for this vertex over here or for this node by one. 66 00:02:55,820 --> 00:02:56,810 So that's over here. 67 00:02:56,810 --> 00:02:59,000 We are going to reduce this by one. 68 00:02:59,000 --> 00:03:02,090 And the indegree factor of this vertex becomes zero. 69 00:03:02,090 --> 00:03:05,180 Now again I is incremented I becomes equal to one. 70 00:03:05,180 --> 00:03:10,700 So we get this neighbor over here and we are going to decrement the indegree factor for node two also 71 00:03:10,700 --> 00:03:11,300 right by one. 72 00:03:11,300 --> 00:03:14,450 So we get the indegree factor of this to be equal to two. 73 00:03:14,480 --> 00:03:17,180 Now we come out of this for loop again. 74 00:03:17,360 --> 00:03:19,160 Uh we check if anything is zero. 75 00:03:19,160 --> 00:03:19,370 Yes. 76 00:03:19,370 --> 00:03:20,360 We got this to be zero. 77 00:03:20,360 --> 00:03:23,450 That's why over here we are going to push this to our stack. 78 00:03:23,450 --> 00:03:26,000 So now this node is pushed to our stack. 79 00:03:26,000 --> 00:03:29,510 Now again we come out of the for loop and we come to the while loop. 80 00:03:29,510 --> 00:03:31,430 We check over here if there is something in our stack. 81 00:03:31,430 --> 00:03:33,170 Yes we have one in our stack. 82 00:03:33,170 --> 00:03:37,190 So we pop this, we come inside and we increment our count right. 83 00:03:37,190 --> 00:03:39,710 So our count now becomes equal to two. 84 00:03:39,740 --> 00:03:40,820 Initially it was one right? 85 00:03:40,820 --> 00:03:42,230 So initially it was zero. 86 00:03:42,230 --> 00:03:44,630 Then when we came inside first it became one. 87 00:03:44,630 --> 00:03:46,010 Now it's equal to two. 88 00:03:46,010 --> 00:03:50,180 Now we come over here and the current node is equal to one right. 89 00:03:50,180 --> 00:03:53,360 So we are going to take the neighbors of one which is just two. 90 00:03:53,360 --> 00:03:53,570 Right. 91 00:03:53,570 --> 00:03:54,560 So which is just two. 92 00:03:54,590 --> 00:03:59,150 So we come over here and we decrement the indegree factor of this node by one. 93 00:03:59,150 --> 00:04:03,050 So over here this minus one gives this equal to one. 94 00:04:03,050 --> 00:04:06,020 So the indegree factor of node two is going to be now one. 95 00:04:06,020 --> 00:04:09,020 And we check if we have anything zero right. 96 00:04:09,020 --> 00:04:11,870 We don't have anything at this point to be equal to zero. 97 00:04:11,870 --> 00:04:14,390 So we don't add anything to our stack. 98 00:04:14,390 --> 00:04:16,040 And then we come out of the for loop. 99 00:04:16,040 --> 00:04:18,980 And when we come over here we see that there is nothing in our stack. 100 00:04:18,980 --> 00:04:19,160 Right. 101 00:04:19,160 --> 00:04:20,990 So the stack is empty at this point. 102 00:04:20,990 --> 00:04:24,980 So we come out and now the count is just equal to two. 103 00:04:24,980 --> 00:04:27,110 But n is equal to five right. 104 00:04:27,110 --> 00:04:30,140 So that's why we can be sure that there is a cycle. 105 00:04:30,140 --> 00:04:35,660 That's why we did not get all the elements or all the vertices uh, to our stack. 106 00:04:35,660 --> 00:04:35,900 Right. 107 00:04:35,900 --> 00:04:38,600 So the stack did not get all the vertices in it. 108 00:04:38,600 --> 00:04:42,620 So we can be sure that there is a cycle and hence we return false. 109 00:04:42,620 --> 00:04:42,800 Right. 110 00:04:42,800 --> 00:04:46,010 Because two is not equal to five and therefore we return false. 111 00:04:46,010 --> 00:04:47,870 So this is how our code works. 112 00:04:47,870 --> 00:04:52,940 So if the count is not equal to n then there is a cycle and we return false. 113 00:04:52,940 --> 00:04:55,190 If it was equal we would have return true. 114 00:04:55,190 --> 00:04:55,700 All right. 115 00:04:55,730 --> 00:05:00,320 Now let's take a quick look at the space and time complexity of our solution over here. 116 00:05:01,230 --> 00:05:03,990 First, let's take a look at the time complexity. 117 00:05:04,020 --> 00:05:06,390 Now for this what all do take time. 118 00:05:06,390 --> 00:05:08,220 So we start over here with this function. 119 00:05:08,220 --> 00:05:10,350 Let's take a look at this function over here. 120 00:05:10,350 --> 00:05:16,530 So over here we calculate we compute or we we get the adjacency list and the indegree right. 121 00:05:16,530 --> 00:05:18,630 So let's take at this helper function over here. 122 00:05:18,630 --> 00:05:20,610 What's the number of operations that we have. 123 00:05:20,610 --> 00:05:21,990 Do we have to do over here. 124 00:05:21,990 --> 00:05:25,230 Now over here to make this adjacency list which is empty. 125 00:05:25,260 --> 00:05:27,840 We will be doing n number of operations. 126 00:05:27,840 --> 00:05:28,020 Right. 127 00:05:28,020 --> 00:05:30,420 Because because we have to map through this array. 128 00:05:30,420 --> 00:05:33,420 And then we have to make every element an empty array. 129 00:05:33,420 --> 00:05:35,490 So over here we are going to do n operations. 130 00:05:35,490 --> 00:05:39,480 And then over here we are going to loop through the prerequisites. 131 00:05:39,480 --> 00:05:41,640 So let's say there are p prerequisites. 132 00:05:41,640 --> 00:05:44,100 So over here they are going to be p operations. 133 00:05:44,100 --> 00:05:50,910 So we can say that over here to get our adjacency list and our indegree we are going to do O of n plus 134 00:05:50,910 --> 00:05:51,690 p operations. 135 00:05:51,690 --> 00:05:51,990 Right. 136 00:05:51,990 --> 00:05:54,810 So again here also we are having an array of n elements. 137 00:05:54,810 --> 00:05:57,030 So this also is going to take n operations. 138 00:05:57,030 --> 00:06:02,670 So in total our helper operation helper function is going to do n plus p operations. 139 00:06:02,670 --> 00:06:04,470 So let's just keep that aside. 140 00:06:04,470 --> 00:06:08,790 Now let's come back to our main function which is check if can finish. 141 00:06:08,790 --> 00:06:11,670 So what are the other operations that we are going to do. 142 00:06:11,670 --> 00:06:17,370 Once we are over here we are again going to loop through the vertices and check the indegree for every 143 00:06:17,370 --> 00:06:17,700 index. 144 00:06:17,700 --> 00:06:17,850 Right. 145 00:06:17,850 --> 00:06:21,870 So again this is going to be another n operations over here. 146 00:06:23,730 --> 00:06:25,020 Now let's continue. 147 00:06:25,050 --> 00:06:28,890 Now we come to this part over here where we have the while loop. 148 00:06:28,890 --> 00:06:32,400 Now in the while loop, how many times are we going to loop through it? 149 00:06:32,430 --> 00:06:36,690 Now in the worst case, if there is no cycle right. 150 00:06:36,690 --> 00:06:40,350 So every element at some point is going to come into the stack. 151 00:06:40,350 --> 00:06:40,710 Right? 152 00:06:40,710 --> 00:06:44,940 So because if there is no cycle then finally the count has to be equal to n. 153 00:06:44,940 --> 00:06:49,380 So in that case we can say that this while loop will do n operations. 154 00:06:49,380 --> 00:06:56,280 And each time it comes in this for loop over here is going to go through the number of edges that particular 155 00:06:56,280 --> 00:06:56,880 node has. 156 00:06:56,880 --> 00:06:57,180 Right. 157 00:06:57,180 --> 00:07:02,490 So if we add up all of those instances together that would be e one plus e two, etc.. 158 00:07:02,490 --> 00:07:02,940 Right. 159 00:07:02,940 --> 00:07:08,910 So first it would be for in this case if n is equal to five let's say n is equal to five, then it would 160 00:07:08,910 --> 00:07:15,900 be e zero where e zero is the number of edges from zero, then e one, then e two, etc. up to e four. 161 00:07:15,900 --> 00:07:20,190 So if we add all of this up together, we will just get the number of edges right. 162 00:07:20,190 --> 00:07:26,730 So we can see that over here in this while loop part, we are going to do a total of N plus E operations. 163 00:07:26,730 --> 00:07:34,080 Again notice it's n plus E because whenever this E zero is going to happen in one instance right. 164 00:07:34,080 --> 00:07:37,320 So this while loop is going to have n iterations. 165 00:07:37,320 --> 00:07:41,160 So in each iteration we may do e zero, e one, e two, etc.. 166 00:07:41,160 --> 00:07:43,350 So all of this together is equal to e. 167 00:07:43,350 --> 00:07:45,990 And this over here is going to do n iterations. 168 00:07:45,990 --> 00:07:52,920 So when we do n iterations over here we will be having e zero plus e one plus E two etc. over here in 169 00:07:52,920 --> 00:07:53,910 this for loop part. 170 00:07:53,910 --> 00:07:58,680 So that's why the total of these two together is going to be n plus E operations. 171 00:07:58,680 --> 00:08:05,130 Therefore, we can say that the time complexity of this solution is going to be n plus p plus n plus 172 00:08:05,130 --> 00:08:09,330 e which is two n plus p plus e and two is just a constant. 173 00:08:09,330 --> 00:08:10,410 So we can avoid that. 174 00:08:10,410 --> 00:08:16,080 And we can say that the time complexity of this solution is of the order of n plus p plus e. 175 00:08:17,000 --> 00:08:22,280 Where n is the number of vertices, e is the number of edges, and p is the number of prerequisites. 176 00:08:22,280 --> 00:08:24,500 So this is the time complexity of this solution. 177 00:08:24,500 --> 00:08:26,450 And what about the space complexity? 178 00:08:26,450 --> 00:08:28,580 Let's take a look at the space complexity also. 179 00:08:28,580 --> 00:08:31,760 Now we can see over here what are the things that take up space. 180 00:08:31,760 --> 00:08:32,960 We have our stack. 181 00:08:32,960 --> 00:08:35,300 Then we have our adjacency list. 182 00:08:35,300 --> 00:08:37,070 We have our indegree array. 183 00:08:37,070 --> 00:08:38,960 So these are the things that take up space over here. 184 00:08:38,960 --> 00:08:44,180 Right now the adjacency list is going to have all the n vertices and the edges right. 185 00:08:44,180 --> 00:08:49,670 So this is going to take space of the order of n plus e where n is the number of vertices and e is the 186 00:08:49,670 --> 00:08:50,660 number of edges. 187 00:08:50,780 --> 00:08:55,280 Now the indegree array is just going to take space of the order of n, because there are going to be 188 00:08:55,280 --> 00:08:56,480 n indices inside it, right? 189 00:08:56,480 --> 00:09:00,110 So the indegree factor for each vertex is going to be there inside it. 190 00:09:00,110 --> 00:09:03,050 So this is going to take space of the order of n. 191 00:09:03,050 --> 00:09:09,620 And in the stack we are just going to have the elements which have their indegree factor to be equal 192 00:09:09,620 --> 00:09:10,040 to zero. 193 00:09:10,040 --> 00:09:16,730 So in the worst case the graph is such that um there is all the all the vertices are just disconnected, 194 00:09:16,730 --> 00:09:17,000 right. 195 00:09:17,000 --> 00:09:20,270 So in that case all the vertices have nothing coming in. 196 00:09:20,270 --> 00:09:24,740 So we could say that all of them have their indegree factor to be equal to zero. 197 00:09:24,740 --> 00:09:27,530 And in that case the stack can take O of n space. 198 00:09:27,530 --> 00:09:29,540 So again that's the worst case for the stack. 199 00:09:29,540 --> 00:09:32,660 So we can say that among all of these the greatest is this. 200 00:09:32,660 --> 00:09:37,760 So hence the space complexity of this solution is going to be of the order of n plus e.