**The Key to Solving Difficult Algorithms: Breaking Down Complex Problems**

In the world of algorithms and coding, one of the most important skills to develop is the ability to break down complex problems into manageable parts. This is especially true for challenging problems that require a deep understanding of the underlying mechanics. The problem presented in this article is a classic example of how taking an example and working through it can lead to a clear understanding of the solution.

**Understanding the Problem**

The problem is as follows: given an array of petrol, an array of petrol capacities, an array of distances, and the number of petrol stations, we need to determine if it's possible to complete a tour that covers all the petrol stations. The tour can start at any station, but once it begins, it must continue until all stations have been visited. The petrol capacity at each station is known, as are the distances between each pair of stations.

At first glance, this problem seems daunting, and it's easy to get stuck on how to approach it. However, by taking an example and working through it, we can develop a clear understanding of the solution. This approach is essential for solving difficult algorithms like this one, as it allows us to identify key patterns and relationships that are crucial to finding a correct solution.

**The Power of Insight**

One of the most important insights gained from working through this problem is the realization that we only need to keep track of two variables: surplus and deficit. The surplus represents the amount of petrol available at each station, while the deficit represents the lack of petrol needed to cover the distances between stations. By focusing on these two variables, we can develop a simple and efficient algorithm for solving the problem.

**The Algorithm**

The algorithm is deceptively simple. We start by initializing our sum (surplus) to zero and setting our starting station index to 0. We then iterate through each station in turn, updating our sum and deficit as we go. If our sum becomes less than zero at any point, we know that we will not be able to complete the tour from this station, so we move on to the next one.

However, if our sum plus our deficit is greater than zero after visiting all stations, then we know that we have found a solution. In this case, the starting station index represents the solution to the problem. If our sum plus our deficit is less than or equal to zero after visiting all stations, then we know that there is no way to complete the tour from any station.

**Code**

The code for this algorithm is surprisingly simple, and it's a great example of how the key idea can be implemented in practice. The algorithm consists of a single loop that iterates through each station in turn, updating our sum and deficit as we go. We use two variables to keep track of our surplus and deficit, which makes the code very straightforward.

**The Importance of Example**

One of the most important lessons learned from working through this problem is the importance of taking an example and working through it. This approach allows us to develop a deep understanding of the solution and identify key patterns and relationships that are crucial to finding a correct solution.

When faced with difficult algorithms like this one, it's tempting to rely on memory or guesswork rather than taking the time to work through an example. However, this approach can lead to mistakes and a lack of understanding. By working through examples and developing a clear understanding of the solution, we can develop the skills and confidence needed to tackle even the most challenging problems.

**Space Complexity**

The space complexity of this algorithm is surprisingly low, at O(1). This means that we use a constant amount of extra memory, regardless of the size of the input. This is an important consideration when working with algorithms, as it can have a significant impact on performance and scalability.

**Conclusion**

In conclusion, solving difficult algorithms like this one requires a deep understanding of the underlying mechanics and a willingness to take the time to work through examples. By breaking down complex problems into manageable parts and focusing on key patterns and relationships, we can develop a clear understanding of the solution and implement it in practice. This approach is essential for success in computer science and coding, and it's a skill that will serve us well in the years to come.

"WEBVTTKind: captionsLanguage: enso this is a very interesting problem and this problem is called the petrol filling problem or sometimes it's also called as the circular gas station problem because in some parts of the world like the US a petrol or diesel filling station or a petrol pump in in in Britain and all of Britain's colonies or erstwhile colonies I should call them erstwhile colonies like India Sri Lanka South Africa they're called as petrol pumps right in the u.s. they're called as gas stations whatever the name of the problem is the problem is as follows it's called the circular gas station problem or the circular petrol pump problem and the problem is as follows right imagine imagine each of these squares represents a petrol pump or a gas station and the number inside this represents the number of liters of petrol that I have right let's assume this is the number of liters of petrol that AAHA so this gas station has zero lead has one liter of petrol this has two liters this has three liters four liters and five liters and this this this arc the the number three here represents the to travel from this petrol pump to this petrol pump I need the distance here is three kilometres and let's assume that to travel one kilometer I need one liter of petrol okay let's assume that simply okay so as to make the problem easier so to go so the challenge here again Egypt so it's so what is given to me is basically an array like this of petrol capacity in each of the pumps and the distance to the next petrol pump this is what I'm given these two aris literally right so 1 2 3 4 5 this is the capacity in each of the petrol pumps there's a capacity in the zeroeth pump first pump second pump third pump and fourth pump and the distance from the zero at pump to the first pump is 3 the distance from the second pump to the third pump or from from the from the first pump to the second pump is 4 and so on so forth now again here we are making an assumption that would travel 1 kilometer we need 1 liter ok that's a simplifying assumption here now what we want to do here is we want to start from any petrol pump we can start from any petrol pump suppose let's assume I want to start from this petrol pump I can start from any petrol pump here I want to ensure that so when I start here my petrol tank is empty or my gas tank is empty in my car so I can fuel up this whole this whole whole of this whatever is a capacity here I can fill it in my car right let's assume my car has unlimited amount of capacity theoretically ok so I can fill up this whole two litres of petrol in met car and then I can start travelling but with these two liters I can only travel 2 kilometers but the distance is 4 kilometers which means I will stop somewhere in between right so that is a problem here right so what I want to do here is this I want to answer this question is there a petrol pump is there a pump or is there a gas station that I can start from that I can start that we can start from that we can start from and complete this tour I want to complete this whole circle right is there a pump that we can start from and complete the tour and a tour and basically complete this whole tour like why is it it's also called as a petrol petrol tour problem or a gas station problem gas station tour problem because I want to start from one station like this and finish all the other stations and come back to this and is that even possible first that's a question is this is there a pump that we can start from such that I can finish the tour without getting stuck anywhere without without being stuck right so this is the first part of the question if there exists such a pump what is that pump that's the second part of the question now there is there is a there is a brute force solution to this problem right so again think about it I want you to pause this video here I hope you understood the problem here right so I can start from any pump like for example let me show you an example let's say you might start from this pump my gas my my petrol in the car or gas in the car is empty so I fuel up 2 litres and with these 2 litres I can travel 2 kilometers which means ice I start traveling halfway I get stuck which means I can't start a 2 from here now can I start a tour from here let's see let's see if I can start a tour from here let's see can I start a tour from here if I start from here i fuel up one liter but the distance here is three liters which means as soon as a as as soon as I travel 1/3 the route my my petrol in the car is empty right my pet my my my petrol tank or the gas in my car is completely exhausted right now what if what if I start from here so instead of this so look at this instead of this sorry so instead of okay let me just erase this so instead of this can I have a tool that starts from here let's see so i fuel up for i fuel up 4 liters i consume 1 liter by the time I come here I have 3 liters I again fuel this up now I have 8 liters i I take all of this fuel right so I have 8 liters in my in my tank 8 - 2 by the time I reach here I have 6 liters so 6 + 1 now I have 7 liters right so 7 minus 3 I will have 4 liters by the time I come here 4 plus 2 6 liters here right 6 minus 4 look at the 6 minus 4 I have 2 liters by the time I come here now I'll again fuel up 2 plus 3 I have 5 liters so I can again come here so if I start my tour from here I can actually complete successfully right now I want to find a pump from which I can start my tour and successfully complete right that's the challenge here now what is what again since you've seen this example right since you've seen this example let's try to tackle this ok so since you've understood this problem pause this here and think of a simple solution first it's always important that you first think of a simple solution then we'll optimize the solution later so please pause it here and think about it if you come up with a decent solution please write the code for it and make it work ok so I'm assuming enough that you have thought through some simple solution one very simple solution is called the brute force solution one very simple solution is a brute force solution the brute force solution what I'll try is this again this is my 0 with petrol tank right so I will try to start a tour from here and I will see whether I am successful or not so here when I start from here I can even go to the next pump so this can't be my starting point next I tried to start from here right again I try to go through all the all these with all these vertices are all these petrol pumps and see if I can finish the tour if I cannot finish it I'll say I can't then I'll try this then I'll try this and so on so forth so look at this for every petrol pump so I'm trying to consider every petrol pump as a starting petrol pump of mid-tour and try out in all the possibilities so for every petrol pump because see there are n petrol pumps I'll try to use as starting petrol pumps and for any petrol pump that I'm using as a starting as a as my starting spot right I might have to look at all the other petrol pumps I might have to travel this whole thing to decide whether this is a start this is a valid starting point or not right so in total if I apply this brute force solution my time complexity is order of n square because I'm trying to consider every petrol every petrol station as a potential starting point and when I consider any petrol station as a potential starting point I might have to do the whole tour right and then finally decided ok this is not working so I have to try again right in the worst case again this is the worst case time complexity in the worst case I my time complexity could be order of n square this is a brute force solution a simple solution on the list fairly decent enough now here comes the interesting part if you're if you're if you are here for an interview I would say this is a decent fast cut solution very good now can you improve this solution can you improve this solution for me the hint that I'll provide you here is can you build an order of n time complexity solution this is my hint this is my hint my hint here is can you think of an order of n solution for this you've come up with an order of n square worst case time complexity solution very good can you come up with an order of n time complexity solution that's my hint now here again try to pause this video and try to think of an order of n solution and one interesting observation here is if you want an order of n solution which means the moment you visit a V you visit a petrol pump you should not visit it again right you should try to avoid visiting it again ok that's one strategy of building order of n time Gotham's okay so here I'm assuming that you have taught through this you have taught through away or you have not been able to come up with it if you're able if you have been able to come up with an order of n time algorithm please go ahead and implement it otherwise let's look at the solution let me redraw this diagram here okay so that's now here I'll try to explain you how to think about this problem and how to arrive at a solution there is no point in me just to tell you the solution because if I tell you the solution you don't learn how to think I want you to learn how to think that is very very important okay so okay so these are all my petrol pumps let's also write down the distances here three four okay so three okay three four five one and two okay so let's start with the C again in my array I am given this order right of petrol pumps in it I am given this order in my for my distances also so I will start with the very first listed petrol pump right so so one second sorry so I will start here okay I'll start here now when I am starting here I will create two variables the first variable is called as surplus which means how much extra do I have the second variable I'll call it deficit how much fuel am a liking okay these variables are also called as sum and difference variable but the right way to think about them is surplice which means how much extra petrol do I have or how much deficit petrol do I have this is one way to think about it again let's tackle this problem imagine if I start here right if so my starting I'll try to start from the very first very first petrol pump that is given to me right so I will fuel up so I will fuel up now I'll see with this fuel cannot travel this distance right with this fuel cannot travel this distance so what is my starting node this is my starting node enough I will see if I can travel this distance I can't travel this distance I can't travel this distance because I can only fuel one liter of petrol but the distance to be traveled is three kilometers I can't travel but now which means this can't be my starting point so I will arrive here but when I arrived here I want to toward this information that I have there is a lesson that I learned here right that the amount of petrol that is here is less than the distance that I can travel by how much I want to store that value here so what I'll do here is in my deficit so till the time till whatever I have seen till of whatever nodes that I have seen till of or whatever petrol pumps I've seen till now what is the deficit enough this is 1 this is 3 so if so this is the data that I have already said I have seen this node already right and this node can't be the starting node we have decided that this node can't be the starting node but to travel from here to here I need 2 litres extra by the time I arrive here otherwise I can't travel this distance so to travel from here to here there is a deficit so in this petrol pump there is a deficit of minus 2 so I'm trying to store that information here now I will again make my surplus because then this can't be the starting point now I'll try to consider this as a starting point if this is a starting point how much fuel do I have at starting point zero right so now I'll see if I can start if I could if I start here right with zero fuel again this is just additional information to keep track of what we have already learned right I don't want to dump the information that we have learnt by trying to use this as a starting note that this has 2 litres deficit than the distance at vapor travel and trying to keep that information handy okay so that again this information will help me evaluate if there is even a solution or not ok we'll see we'll see how it is useful now I come here now I try to consider this as my starting point ok so if I try to consider this as my starting point what happens nuf now I don't have any surplus if this is my starting point my surplus equals to zero I don't have any I don't have any any fuel to start with now I have two litres of fuel here I have to travel four kilometres with it I can't do that which means this can't again be the starting node now I will try to consider this as my starting node but there is a lesson that I have learned that here also there is a deficit of two litres so I'll try to use this so I'll keep incrementing my deficit or difference right so I have minus two till here again I have minus 2 bill here which means of all the all the petrol pumps I've seen from the zeroeth petrol pump to this petrol pump there is 4 liters of deficit that is that is there in the petrol pumps which means by the time I arrive here I need four liters extra petrol to be able to finish this whole loop right that's a problem that I have enough right now let's see let's see now let's let's continue this circle since again I'm trying to consider this as my starting point at the very beginning how much surplus do I have again this can't be my starting this can't be my starting right now if this is my starting it's starting how much surplus do I have I don't have any surplus my tank is empty right my fuel tank is literally empty now now if my fuel tank is empty now what will I do here look at this now I can fuel 3 litres of petrol here with 3 litres of petrol I have to travel 5 liters here I am to travel sorry 5 kilometers that is also not possible that is also not possible right so again which means this also can't be my starting node ok now I'll try to consider this as my starting node again this can't be my starting node right because I have to travel 5 kilometers here just using 3 litres of fuel I don't have I don't have that right so now again I will keep I'll keep my deficit I will keep incrementing my deficit what is the deficit here again two more liters so my deficit has become minus six right so I have minus four already and then to minus four I'll add 3 minus 5 which is minus 2 so I get minus 6 so now I will consider this as my starting node look at this I've ruled out the possibility that this can be my starting node I've ruled out this I've ruled this out now can this be my starting node let's see let's see again there is a there are cases wherein there may not be any starting pump any pump whether if I start I can completed to successfully we have been able to answer that also so now let's let's see what happens if you are here right so my deficit is minus 6 my sub plus is 0 because I'm starting again here now now here if I fuel up four litres to travel this distance I only I only will consume look at this I only will consume four I only will consume one liter here which means by the time I arrive here there is still a surplus of 3 litres in my petrol pump right in my gas tank in the car or the petrol or the petrol tank of my car I have three litres of extra petrol because I fueled up four liters I only consumed one liter to cover one kilometer here so which means by the time I arrived here by the time I arrived here have this surplus and to travel here there is no deficit I'm not adding any deficit my deficit still stays the same because because I have surplus here I don't have to worry about deficit right this deficit will not be will not will not change now because I have surplus here right now again let's go from here to here okay so I've arrived here okay very good so which means this can still be my starting node okay at least this first hop it has done successfully let's look at the next hop okay let me change the colour slightly okay so this is this is the surplus that I have and this is the deficit I have by the time I come here now look at this now from here now I can fuel up five litres here look at this I can fuel up five litres which means by the time I arrive back here by the time I arrive here so my what is my total gas tank what is what is the petrol pump now three plus five is eight I have eight litres of petrol here and I'm going to consume two liters here which means I arrive here with six litres of petrol and there is no deficit here right there is surplus here my surplus changed my deficit by the time I come here is minus six look at this I've I've touched all the points love and since I started here and I kept counting sucked I kept counting deficit look at this I started here and I kept counting the deficit from this place by the time I arrived here by the time I arrived here look at this by the time I arrived back here I have six litres in my gas tank and there is a deficit of six litres in this pot right now the six litres extra that I have will compensate this deficit that I have right again when these two are same when I add these two look at this if I add s plus D if it is greater than equal to zero if it is greater than equal to zero with this with this amount of fuel that I have here I can traverse the rest of the cycle even though I started here look at this I did not test I do not have to test the whole thing again right because I'm keeping track of the deficit in my petrol pumps I'm tracking this information this is very important information so by the time I traverse through all the elements by the time I traverse through all the elements I have a surplus of six liters in my gas tank or in a petrol petrol tank and in this path there is a deficit of minus six of course these two will tally out as long as my s plus D is greater than zero I can cover this distance but what if your s plus B is less than zero imagine imagine if my surplus was five imagine imagine a case and my deficit is minus six if that's the case by the time I arrive here then I can't complete the tour which means which means if my s plus B is less than 0 there is no tour that can solve this problem right and this this is a very very important idea again the key idea here again this algorithm is order of n because I'm visiting each petrol stations exactly once the key idea here is to keep track of both surplus and deficit how much extra petrol will I have through my journey and how much how much is the lack of petrol in this path across these petrol stations if I just keep track of them I can create an order of an algorithm that is the key insight here ok and now once you have this insight code is straightforward this problem is not about cold this problem is mostly about coming up with this idea that I can keep track of surplus and deficit right what is surplus surplus is the amount of petrol that I have in my petrol tank deficit is the amount is the is the is the lack of petrol to cover some lengths in the petrol stations okay instead of calling them surplus and deficit because they're slightly complex words we they just call them as some mend if write or snd you can call them whatever you want I hope you understood the logic here you can try it with other examples also this is the key observation and this observation you can only arrive it by working out examples when you're given an algorithms problem we're coming up with the solution is coming up with the idea on how to tackle this is important the best way is to take an example best way is to take an example and understand what's happening by while solving this example on a pen and paper so when you when you obtain this idea when you make this observation that I can keep track of both surplus and deficit code is straightforward actually this code is literally this code is literally 10 50 lines of code look at this what am I doing here I am given an array of petrol I'm given an array of patrols petrol capacities I am given an array of distances and the number of petrol stations I'm creating my sum equals to zero sum is nothing but surplus this is my starting petrol station index my difference is nothing but my deficit look at this for loop it's just a simple for loop here for I equals to zero I less than n sum equals to sum plus how much petrol - distance wait see some initially is zero after traveling the I'd say after travelling Africa after filling up using the petrol in the height station and traveling distance I how much surplus is there that's what I'm storing in sum here now if sum is less than zero that means I can't travel so I'm changing my starting node to I plus 1 I am also updating my diff see the very fact that sum is less than equal to zero means there is a there is a deficit which means I need to update my variable diff which is storing the deficit and I make my sum equals to zero to make the I plus 1 node to make the I plus 1 node as a starting node this is what my for loop does and finally I check this if some plus diff is greater than zero then whatever is my starting node right now will be the answer or else it will be minus 1 and minus 1 basically implies that there is no way to complete this tour which is basically like this we have discussed this case write sum plus diff greater than equal to zero basically means there is a solution sum plus diff less than or a surplus plus deficit less than zero basically means there is no way to complete the tour here again this code itself is very very simple again by looking at this code you can look you can easily understand that this is an order of n algorithm because there is a simple for loop here no recursion nothing very fancy the key idea here is these two variables creating a surplus variable and a deficit variable and working through it again the most important part of this problems like this is to actually work out an example and try to understand what's happening okay that is very very important because these types of problems are not testing your coding ability they're testing your ability to solve a tricky problem like this and come up with a reasonable solution by using a bunch of variables again even my space complexity here is order of 1 because I literally have just a constant number of variables that I'm using right again this is a very very interesting very very popular very very popular algorithm and I have seen again from my own experience I've seen some people who remember this by heart literally this is such a popular interview equation at top-notch product based companies people remember the solution by heart so to validate whether they're thinking clearly or not I asked them this question I asked them the solution that you've written prove that it is correct ok I've seen I've seen I've seen some interviewers some some interviewee candidates who just remember this by heart they don't understand the problem in depth they just remember the solution by heart then I tell them argue with an example that the solution that you've designed is correct and if they don't think clearly they'll get caught okay if they remember things by heart you'll get caught the problem solving approach is important and that's what you improve by actually tackling these harder problems and by tackling them using an example even when I had to solve this problem when I was rote writing notes for this for this video I actually took this example and actually solved it on my own a notebook and that's of you that's how you obtain intuition especially for problems like theseso this is a very interesting problem and this problem is called the petrol filling problem or sometimes it's also called as the circular gas station problem because in some parts of the world like the US a petrol or diesel filling station or a petrol pump in in in Britain and all of Britain's colonies or erstwhile colonies I should call them erstwhile colonies like India Sri Lanka South Africa they're called as petrol pumps right in the u.s. they're called as gas stations whatever the name of the problem is the problem is as follows it's called the circular gas station problem or the circular petrol pump problem and the problem is as follows right imagine imagine each of these squares represents a petrol pump or a gas station and the number inside this represents the number of liters of petrol that I have right let's assume this is the number of liters of petrol that AAHA so this gas station has zero lead has one liter of petrol this has two liters this has three liters four liters and five liters and this this this arc the the number three here represents the to travel from this petrol pump to this petrol pump I need the distance here is three kilometres and let's assume that to travel one kilometer I need one liter of petrol okay let's assume that simply okay so as to make the problem easier so to go so the challenge here again Egypt so it's so what is given to me is basically an array like this of petrol capacity in each of the pumps and the distance to the next petrol pump this is what I'm given these two aris literally right so 1 2 3 4 5 this is the capacity in each of the petrol pumps there's a capacity in the zeroeth pump first pump second pump third pump and fourth pump and the distance from the zero at pump to the first pump is 3 the distance from the second pump to the third pump or from from the from the first pump to the second pump is 4 and so on so forth now again here we are making an assumption that would travel 1 kilometer we need 1 liter ok that's a simplifying assumption here now what we want to do here is we want to start from any petrol pump we can start from any petrol pump suppose let's assume I want to start from this petrol pump I can start from any petrol pump here I want to ensure that so when I start here my petrol tank is empty or my gas tank is empty in my car so I can fuel up this whole this whole whole of this whatever is a capacity here I can fill it in my car right let's assume my car has unlimited amount of capacity theoretically ok so I can fill up this whole two litres of petrol in met car and then I can start travelling but with these two liters I can only travel 2 kilometers but the distance is 4 kilometers which means I will stop somewhere in between right so that is a problem here right so what I want to do here is this I want to answer this question is there a petrol pump is there a pump or is there a gas station that I can start from that I can start that we can start from that we can start from and complete this tour I want to complete this whole circle right is there a pump that we can start from and complete the tour and a tour and basically complete this whole tour like why is it it's also called as a petrol petrol tour problem or a gas station problem gas station tour problem because I want to start from one station like this and finish all the other stations and come back to this and is that even possible first that's a question is this is there a pump that we can start from such that I can finish the tour without getting stuck anywhere without without being stuck right so this is the first part of the question if there exists such a pump what is that pump that's the second part of the question now there is there is a there is a brute force solution to this problem right so again think about it I want you to pause this video here I hope you understood the problem here right so I can start from any pump like for example let me show you an example let's say you might start from this pump my gas my my petrol in the car or gas in the car is empty so I fuel up 2 litres and with these 2 litres I can travel 2 kilometers which means ice I start traveling halfway I get stuck which means I can't start a 2 from here now can I start a tour from here let's see let's see if I can start a tour from here let's see can I start a tour from here if I start from here i fuel up one liter but the distance here is three liters which means as soon as a as as soon as I travel 1/3 the route my my petrol in the car is empty right my pet my my my petrol tank or the gas in my car is completely exhausted right now what if what if I start from here so instead of this so look at this instead of this sorry so instead of okay let me just erase this so instead of this can I have a tool that starts from here let's see so i fuel up for i fuel up 4 liters i consume 1 liter by the time I come here I have 3 liters I again fuel this up now I have 8 liters i I take all of this fuel right so I have 8 liters in my in my tank 8 - 2 by the time I reach here I have 6 liters so 6 + 1 now I have 7 liters right so 7 minus 3 I will have 4 liters by the time I come here 4 plus 2 6 liters here right 6 minus 4 look at the 6 minus 4 I have 2 liters by the time I come here now I'll again fuel up 2 plus 3 I have 5 liters so I can again come here so if I start my tour from here I can actually complete successfully right now I want to find a pump from which I can start my tour and successfully complete right that's the challenge here now what is what again since you've seen this example right since you've seen this example let's try to tackle this ok so since you've understood this problem pause this here and think of a simple solution first it's always important that you first think of a simple solution then we'll optimize the solution later so please pause it here and think about it if you come up with a decent solution please write the code for it and make it work ok so I'm assuming enough that you have thought through some simple solution one very simple solution is called the brute force solution one very simple solution is a brute force solution the brute force solution what I'll try is this again this is my 0 with petrol tank right so I will try to start a tour from here and I will see whether I am successful or not so here when I start from here I can even go to the next pump so this can't be my starting point next I tried to start from here right again I try to go through all the all these with all these vertices are all these petrol pumps and see if I can finish the tour if I cannot finish it I'll say I can't then I'll try this then I'll try this and so on so forth so look at this for every petrol pump so I'm trying to consider every petrol pump as a starting petrol pump of mid-tour and try out in all the possibilities so for every petrol pump because see there are n petrol pumps I'll try to use as starting petrol pumps and for any petrol pump that I'm using as a starting as a as my starting spot right I might have to look at all the other petrol pumps I might have to travel this whole thing to decide whether this is a start this is a valid starting point or not right so in total if I apply this brute force solution my time complexity is order of n square because I'm trying to consider every petrol every petrol station as a potential starting point and when I consider any petrol station as a potential starting point I might have to do the whole tour right and then finally decided ok this is not working so I have to try again right in the worst case again this is the worst case time complexity in the worst case I my time complexity could be order of n square this is a brute force solution a simple solution on the list fairly decent enough now here comes the interesting part if you're if you're if you are here for an interview I would say this is a decent fast cut solution very good now can you improve this solution can you improve this solution for me the hint that I'll provide you here is can you build an order of n time complexity solution this is my hint this is my hint my hint here is can you think of an order of n solution for this you've come up with an order of n square worst case time complexity solution very good can you come up with an order of n time complexity solution that's my hint now here again try to pause this video and try to think of an order of n solution and one interesting observation here is if you want an order of n solution which means the moment you visit a V you visit a petrol pump you should not visit it again right you should try to avoid visiting it again ok that's one strategy of building order of n time Gotham's okay so here I'm assuming that you have taught through this you have taught through away or you have not been able to come up with it if you're able if you have been able to come up with an order of n time algorithm please go ahead and implement it otherwise let's look at the solution let me redraw this diagram here okay so that's now here I'll try to explain you how to think about this problem and how to arrive at a solution there is no point in me just to tell you the solution because if I tell you the solution you don't learn how to think I want you to learn how to think that is very very important okay so okay so these are all my petrol pumps let's also write down the distances here three four okay so three okay three four five one and two okay so let's start with the C again in my array I am given this order right of petrol pumps in it I am given this order in my for my distances also so I will start with the very first listed petrol pump right so so one second sorry so I will start here okay I'll start here now when I am starting here I will create two variables the first variable is called as surplus which means how much extra do I have the second variable I'll call it deficit how much fuel am a liking okay these variables are also called as sum and difference variable but the right way to think about them is surplice which means how much extra petrol do I have or how much deficit petrol do I have this is one way to think about it again let's tackle this problem imagine if I start here right if so my starting I'll try to start from the very first very first petrol pump that is given to me right so I will fuel up so I will fuel up now I'll see with this fuel cannot travel this distance right with this fuel cannot travel this distance so what is my starting node this is my starting node enough I will see if I can travel this distance I can't travel this distance I can't travel this distance because I can only fuel one liter of petrol but the distance to be traveled is three kilometers I can't travel but now which means this can't be my starting point so I will arrive here but when I arrived here I want to toward this information that I have there is a lesson that I learned here right that the amount of petrol that is here is less than the distance that I can travel by how much I want to store that value here so what I'll do here is in my deficit so till the time till whatever I have seen till of whatever nodes that I have seen till of or whatever petrol pumps I've seen till now what is the deficit enough this is 1 this is 3 so if so this is the data that I have already said I have seen this node already right and this node can't be the starting node we have decided that this node can't be the starting node but to travel from here to here I need 2 litres extra by the time I arrive here otherwise I can't travel this distance so to travel from here to here there is a deficit so in this petrol pump there is a deficit of minus 2 so I'm trying to store that information here now I will again make my surplus because then this can't be the starting point now I'll try to consider this as a starting point if this is a starting point how much fuel do I have at starting point zero right so now I'll see if I can start if I could if I start here right with zero fuel again this is just additional information to keep track of what we have already learned right I don't want to dump the information that we have learnt by trying to use this as a starting note that this has 2 litres deficit than the distance at vapor travel and trying to keep that information handy okay so that again this information will help me evaluate if there is even a solution or not ok we'll see we'll see how it is useful now I come here now I try to consider this as my starting point ok so if I try to consider this as my starting point what happens nuf now I don't have any surplus if this is my starting point my surplus equals to zero I don't have any I don't have any any fuel to start with now I have two litres of fuel here I have to travel four kilometres with it I can't do that which means this can't again be the starting node now I will try to consider this as my starting node but there is a lesson that I have learned that here also there is a deficit of two litres so I'll try to use this so I'll keep incrementing my deficit or difference right so I have minus two till here again I have minus 2 bill here which means of all the all the petrol pumps I've seen from the zeroeth petrol pump to this petrol pump there is 4 liters of deficit that is that is there in the petrol pumps which means by the time I arrive here I need four liters extra petrol to be able to finish this whole loop right that's a problem that I have enough right now let's see let's see now let's let's continue this circle since again I'm trying to consider this as my starting point at the very beginning how much surplus do I have again this can't be my starting this can't be my starting right now if this is my starting it's starting how much surplus do I have I don't have any surplus my tank is empty right my fuel tank is literally empty now now if my fuel tank is empty now what will I do here look at this now I can fuel 3 litres of petrol here with 3 litres of petrol I have to travel 5 liters here I am to travel sorry 5 kilometers that is also not possible that is also not possible right so again which means this also can't be my starting node ok now I'll try to consider this as my starting node again this can't be my starting node right because I have to travel 5 kilometers here just using 3 litres of fuel I don't have I don't have that right so now again I will keep I'll keep my deficit I will keep incrementing my deficit what is the deficit here again two more liters so my deficit has become minus six right so I have minus four already and then to minus four I'll add 3 minus 5 which is minus 2 so I get minus 6 so now I will consider this as my starting node look at this I've ruled out the possibility that this can be my starting node I've ruled out this I've ruled this out now can this be my starting node let's see let's see again there is a there are cases wherein there may not be any starting pump any pump whether if I start I can completed to successfully we have been able to answer that also so now let's let's see what happens if you are here right so my deficit is minus 6 my sub plus is 0 because I'm starting again here now now here if I fuel up four litres to travel this distance I only I only will consume look at this I only will consume four I only will consume one liter here which means by the time I arrive here there is still a surplus of 3 litres in my petrol pump right in my gas tank in the car or the petrol or the petrol tank of my car I have three litres of extra petrol because I fueled up four liters I only consumed one liter to cover one kilometer here so which means by the time I arrived here by the time I arrived here have this surplus and to travel here there is no deficit I'm not adding any deficit my deficit still stays the same because because I have surplus here I don't have to worry about deficit right this deficit will not be will not will not change now because I have surplus here right now again let's go from here to here okay so I've arrived here okay very good so which means this can still be my starting node okay at least this first hop it has done successfully let's look at the next hop okay let me change the colour slightly okay so this is this is the surplus that I have and this is the deficit I have by the time I come here now look at this now from here now I can fuel up five litres here look at this I can fuel up five litres which means by the time I arrive back here by the time I arrive here so my what is my total gas tank what is what is the petrol pump now three plus five is eight I have eight litres of petrol here and I'm going to consume two liters here which means I arrive here with six litres of petrol and there is no deficit here right there is surplus here my surplus changed my deficit by the time I come here is minus six look at this I've I've touched all the points love and since I started here and I kept counting sucked I kept counting deficit look at this I started here and I kept counting the deficit from this place by the time I arrived here by the time I arrived here look at this by the time I arrived back here I have six litres in my gas tank and there is a deficit of six litres in this pot right now the six litres extra that I have will compensate this deficit that I have right again when these two are same when I add these two look at this if I add s plus D if it is greater than equal to zero if it is greater than equal to zero with this with this amount of fuel that I have here I can traverse the rest of the cycle even though I started here look at this I did not test I do not have to test the whole thing again right because I'm keeping track of the deficit in my petrol pumps I'm tracking this information this is very important information so by the time I traverse through all the elements by the time I traverse through all the elements I have a surplus of six liters in my gas tank or in a petrol petrol tank and in this path there is a deficit of minus six of course these two will tally out as long as my s plus D is greater than zero I can cover this distance but what if your s plus B is less than zero imagine imagine if my surplus was five imagine imagine a case and my deficit is minus six if that's the case by the time I arrive here then I can't complete the tour which means which means if my s plus B is less than 0 there is no tour that can solve this problem right and this this is a very very important idea again the key idea here again this algorithm is order of n because I'm visiting each petrol stations exactly once the key idea here is to keep track of both surplus and deficit how much extra petrol will I have through my journey and how much how much is the lack of petrol in this path across these petrol stations if I just keep track of them I can create an order of an algorithm that is the key insight here ok and now once you have this insight code is straightforward this problem is not about cold this problem is mostly about coming up with this idea that I can keep track of surplus and deficit right what is surplus surplus is the amount of petrol that I have in my petrol tank deficit is the amount is the is the is the lack of petrol to cover some lengths in the petrol stations okay instead of calling them surplus and deficit because they're slightly complex words we they just call them as some mend if write or snd you can call them whatever you want I hope you understood the logic here you can try it with other examples also this is the key observation and this observation you can only arrive it by working out examples when you're given an algorithms problem we're coming up with the solution is coming up with the idea on how to tackle this is important the best way is to take an example best way is to take an example and understand what's happening by while solving this example on a pen and paper so when you when you obtain this idea when you make this observation that I can keep track of both surplus and deficit code is straightforward actually this code is literally this code is literally 10 50 lines of code look at this what am I doing here I am given an array of petrol I'm given an array of patrols petrol capacities I am given an array of distances and the number of petrol stations I'm creating my sum equals to zero sum is nothing but surplus this is my starting petrol station index my difference is nothing but my deficit look at this for loop it's just a simple for loop here for I equals to zero I less than n sum equals to sum plus how much petrol - distance wait see some initially is zero after traveling the I'd say after travelling Africa after filling up using the petrol in the height station and traveling distance I how much surplus is there that's what I'm storing in sum here now if sum is less than zero that means I can't travel so I'm changing my starting node to I plus 1 I am also updating my diff see the very fact that sum is less than equal to zero means there is a there is a deficit which means I need to update my variable diff which is storing the deficit and I make my sum equals to zero to make the I plus 1 node to make the I plus 1 node as a starting node this is what my for loop does and finally I check this if some plus diff is greater than zero then whatever is my starting node right now will be the answer or else it will be minus 1 and minus 1 basically implies that there is no way to complete this tour which is basically like this we have discussed this case write sum plus diff greater than equal to zero basically means there is a solution sum plus diff less than or a surplus plus deficit less than zero basically means there is no way to complete the tour here again this code itself is very very simple again by looking at this code you can look you can easily understand that this is an order of n algorithm because there is a simple for loop here no recursion nothing very fancy the key idea here is these two variables creating a surplus variable and a deficit variable and working through it again the most important part of this problems like this is to actually work out an example and try to understand what's happening okay that is very very important because these types of problems are not testing your coding ability they're testing your ability to solve a tricky problem like this and come up with a reasonable solution by using a bunch of variables again even my space complexity here is order of 1 because I literally have just a constant number of variables that I'm using right again this is a very very interesting very very popular very very popular algorithm and I have seen again from my own experience I've seen some people who remember this by heart literally this is such a popular interview equation at top-notch product based companies people remember the solution by heart so to validate whether they're thinking clearly or not I asked them this question I asked them the solution that you've written prove that it is correct ok I've seen I've seen I've seen some interviewers some some interviewee candidates who just remember this by heart they don't understand the problem in depth they just remember the solution by heart then I tell them argue with an example that the solution that you've designed is correct and if they don't think clearly they'll get caught okay if they remember things by heart you'll get caught the problem solving approach is important and that's what you improve by actually tackling these harder problems and by tackling them using an example even when I had to solve this problem when I was rote writing notes for this for this video I actually took this example and actually solved it on my own a notebook and that's of you that's how you obtain intuition especially for problems like these\n"