10 Common Coding Interview Problems - Solved!

Key Takeaways

in this course you'll learn how to solve 10 very popular coding interview problems and you'll learn the theory behind the solutions so you'll be better equipped to solve other types of problems as well welcome to the 10 popular coding interview problems course 10 well-chosen problems that cover different algorithms and data structures topics to increase your knowledge and prepare for interviews please try to solve before watching the solution prepare yourself and see you in the first lecture welcome to this video where we will solve the first problem of this course valid anagram a quite easy problem compared to next ones we are given two strings s1 and s2 and we are asked to check if they are anagrams two strings are anagrams if they are made of the same characters with the same frequency just in a different order for example with the strings tender and garden we take one of them we rearrange its characters and we get the other one how are we gonna solve this problem we know that two strings are anagrams if they have the same characters with the same frequency so what we can do is to calculate the frequency of each character in s1 calculate the frequency of each character in s2 and compare the results but what structure do we use to do so we can use an array where each cell represents the number of frequencies they all start at zero then for each character in the string we increment the corresponding cell this solution is suitable when the alphabet is small one of the number of possible characters is not big for example if the strings can only be made of lowercase alphabetical letters we'd need an array of 26 elements it's fine but it's not necessarily the case they can contain all the characters and we have thousands and thousands of existing possible characters the array would take a lot of time and space to create it and traverse it the best structure for our problem is the hash table a structure that maps unique keys to values in our case the key will be the character and the values number of occurrences for example if we have nameless and salesman with nameless we get this hash table and with salesman we get this one here they have the same keys with the same values so they're equal it means that nameless and salesman are anagrams in code we'll first check that both strings have the same length because if they're not it's impossible for them to be anagrams then we create our two hash tables and we start traversing for each character in s1 if the key is already existing in frac 1 we just increment else we create it and we set its value to 1. then for s2 same logic but with frac2 now that we fill them we check that they have the same values for each k and frac 1 if it doesn't exist in frack 2 or for a 1 of key isn't equal to fracture of key we return false it means that either the character of s1 doesn't exist in s2 or they don't appear the same number of times after the loop if we didn't find any difference we return true and in python we don't even need to write all this because we have a class named countering collections module that builds the table of occurrences just by passing the string as an argument and we can compare dictionaries with the equality operator so in reality we'll just return counter of s1 equal to counter of s2 for the time complexity in the worst case s1 and s2 have the same length let's name it n we're traversing n characters at most three times and switching inserting in a hash table cos of one in average we'll get of m plus of m plus of n which gives an off and time complexity and for the space complexity we have of and for each table because they can contain up to n keys each we get an off and space complexity we still have another solution to discuss you have to know that two anagrams have the same lexicographically sorted string for example with nameless and salesman if we sort nameless we get a e e l m n s s and with salesman same thing so in the second solution we just sort both strings and compare the results in code after the equal length condition we return sorted s1 is equal to sorted s2 that's it sorting a string of n characters cos of analog and time we're doing it twice plus and for comparing we get an off analog and time complexity and for the space complexity we have off and for the sorted result twice we get an off and space complexity we reached the end of this video we solved the valid anagram problem i hope that you understood both solutions and see you in the next one welcome back to the course in this lecture we will solve the first and last position problem we are given a sorted array of integers r and an integer target and we are asked to find the index of the first and last position of targeting r if target can't be found in r we turn minus one minus one for example if r is two four five five five five five seven nine nine and target is 5 the output would be 2 6 because the first position of target is 2 and its last position is 6. first of all because the array is sorted all the elements with the same value will be adjacent to each other for example here all positions of the value 5 are consecutive it means that the first possible solution is to start traversing the array from the beginning find the first position of target and keep working until finding the last position with our example we have two four then five we found the first position we keep walking we have five five five five this one is the last one we found the end position return them in code we start traversing indexes of r and if r of i is equal to target it means that we found the start position now we keep walking while the next element exists and is equal to target y i plus 1 is smaller than length of r and r of i plus 1 is equal to target we increment i after the while loop i know represents the position of the last occurrence this is why we return start i and if the for loop ends without having returned the result it means that we didn't find target in r at all we return minus one minus one know that it's possible to have start position equal to end position it happens when there is only one occurrence of target in r for the time complexity when target exists which reverses the part before its first position then its sequence of occurrences and when it doesn't which offers the whole array in both cases whichever is at most add elements where n is the number of elements of r we've got a time complexity of of n and a constant space complexity because we're just using invariables this solution uses linear search which gave an off and time complexity both the array is sorted so we can think of using binary search let's try to use binary search to find the start position with binary search we can find the position of an element in a sorted array but here we're not searching for any position of target we're searching for the first one i is the first position of target if r of i is equal to target obviously but also r of i minus 1 has to be smaller than target smaller because the array sorted so we'll use binary switch normally but to add the second condition before returning mint let's try it with our example left and right started first and last element of r as usual man is left plus right divided by two we get four here it's true that our four is equal to target but it's not enough r of 4 minus 1 is not smaller than target so mid is not the starting position of target but should we go to the left part or to the right part now r of mate is not greater than target so the first position can only be in the left part we continue mid is now zero plus three divided by two we get one our phone is smaller than target so the starting position can only be in the right part we continue it is now two plus three divided by two which is two r of mid is equal to target and r of minus one is smaller than target so omega represents the first position of target we return it in code we can first have an early exit condition for the case where the first element is equal to target would document know that 0 is the starting position we turn zero by the way in solution space on binary search put as much early exact conditions as possible to handle edge cases and avoid out of bounds problems after it we initialize left and right at 0 and n minus 1 respectively 0 and n minus 1 are the indexes of the first and last element of r now while left is smaller than or equal to right we calculate mid index it's left plus right divided by two after it we have three cases the case where both conditions are respected where r of mid is equal to target and r of min minus one is more than target it means that mid is a starting position we return it second case r of made is smaller than target it means that we're still before the starting position this is why we take left to mid plus 1 to start again in the right part else it means that we exceeded the consecutive sequence or we're inside it but not at the beginning so start can only be in the left part we take right to mid minus one and if the while loop didn't return the result it means that target doesn't have an existing r we return -1 now we found the start index but we still need to find the end index we can think of just walking starting from start until we find the last position of target but it would ruin everything we did because in the worst case we need to traverse the whole array which results in an off and time complexity same as the first solution you guessed it to find the end index we will also use binary search but the condition is a bit different from the first time when searching for the start position r of mid had to be equal to target and r of mid minus 1 smaller than target and for the end position r of med has to be equal to target and r of mid plus 1 has to be greater than target next element has to be greater because it would mean that from the right we're not in consecutive target elements anymore so the actual position is the last position of target in code we just change a few things the early exit condition occurs now when the last element is equal to target it means that the last position of target is in the last index of r n minus 1 without clear return then in the three cases the cases where we will turn mid is when rf made is equal to target and r of mid plus 1 is greater than target for the two remaining ones here one hour of maid is greater than target then we exceeded the consecutive sequence we go to the left part right becomes mir minus one else it means that either we're before the consecutive sequence or we're inside it but not at the end so end can only be in the right part left becomes mid plus one now we have our find start function we have our find end function we can move to the main solution function first of all we have some early exit conditions we can identify at least three cases where we can't find target at all when the array has no elements one target is smaller than the first element and when target is greater than the last element in the last two ones because the array is sorted we can deduce a target is not equal to all other elements if at least one of these conditions is true without k return -1 -1 else we call fansa to get the start position we call find n to find the end position and we return start and if target doesn't exist in r start and n will have returned -1 bath we still get the expected result for the time complexity we're using binary search twice and binary search has an offload and time complexity because we keep dividing the input size by two two times offlock and gives an overlock and time complexity and for the space complexity you get of one because we're just using int variables before ending this lecture i want to tell you that if you're not comfortable with binary search you should really work on it because it's a fundamental algorithm technique that appears in many problems like this one find peak first bad version and many other ones we reach the end of this lecture i hope that you understood the solutions and see you in the next one welcome back to the course in this lecture we will solve the kth largest element problem we are given an array of integers and an integer k and we are asked to find the kth largest element for example if we have r equal to 429756713 [Music] and k equal to 4 the output should be 6 because the largest element is 9 the second largest is 7 the third largest c7 and the 4th largest is 6. the first possible solution that we may think of is to remove the maximum element k minus 1 times because after doing so the next maximum represents the kth largest element for example with our array k is 4 so we remove the maximum element 3 times first iteration max is nine we remove it second iteration max is seven we move it third iteration max is seven we remove it now that we finished the three iterations the maximum and remaining elements is the k largest element of the original array it's 6 here we return it in code we have a full loop that is repeated k minus 1 times where we remove the maximum element after the loop we return max of r that's it for the time complexity searching for the maximum cost of n where n is the number of elements and removing it from the array cos n is the worst case because we may need to shift all the n minus 1 elements and our loop is repeated k minus 1 times we have k minus 1 times 2 n plus n for finding the final largest element in total we have k minus 1 times 2 n plus n which is 2 times k times n minus n which gives an o of k times and time complexity where n is the number of elements of r i know that in reality during the iterations n will decrease because we have less and less elements but we get the same time complexity and for the space complexity we're not using input size related variables we have a constant space complexity this solution is a bit slow let's move to the next one the idea of the second solution is to start by sorting the array because by doing so we know that the largest element is of the last cell the second largest element just before it the third largest just before it and so on with our array we sort it and k is four so we turn the fourth element starting from the end in a general way we solve r and we return r of n minus k n minus k represents the index of the kth element starting from the end for the time complexity we have of analog and for sorting the array and one for accessing we've got an off analog and time complexity and for the space complexity it depends on the space complexity of the sorting function this solution is way faster than the first one except in some cases but we still have another solution to discover in the first solution we didn't have to sort which is good but searching for the maximum costs out at each iteration which slows down the process what if instead of and getting the maximum cost lock and only yes it's possible by using a priority queue a priority queue is a queue where the next element to be popped is not the first one that entered but the one with the highest priority and is usually implemented with a heap if you don't know about heaps and priority queues you should really watch my youtube video on the subject you'll find the link below or you can just search for inside code heaps on youtube and after building our priority queue popping the next element costs of log and only so we just have to pay the cost of building the priority queue which is n for example with our array this is what our hip would look like you can see that the element at the top is the greatest one we extract it and it costs offlock and to rearrange notes second iteration will extract the root and it cuts offlock and to rearrange to maintain the order third iteration same thing now that we did the k minus one iterations the next extracted node is the kth largest element we return it here is six in python we have the hip q module but the problem is that it's implemented with a min heap not a max heap so at the top we'll find the smallest element not the greatest to counter that we just multiply values by -1 to reverse the order so we start by replacing r by minus lm for each element in r after doing so we heapify r to make it respect the heap property and now we're ready to start extracting we extract from it k minus one times after the loop we extract the last time and return the result multiplied by -1 obviously to get the original number that was in r for the time complexity we have n to build a new array with reversed values and to hippify it go check the video to know why and then we have k minus 1 iterations each iteration costs offload and to extract after the loop we have offload and to extract one more time in total we have two n plus k minus one times log n plus log n which is two n plus k log n which gives a time complexity of of m plus k log n which is a bit better than the one of the previous solution because k can't exceed n well this solution starts giving interesting time performance difference only when n is huge and k small because when k is close to n of n plus k log n is close to of analog n the time complexity of the previous solution but when k is close to zero o of m plus k log n is close to of n and for the space complexity we have and for the priority queue we get an off and space complexity we reached the end of this video i hope that you understood the three solutions and see you in the next one welcome back to the course in this lecture we will solve the symmetric tree problem we have a binary tree and we want to see if it's symmetric in other words if it's a mirror of itself for example this tree is symmetric because if we take its left part reverse it we get its right powered and vice versa if we take its right part we reverse it we got its left part but this one is not symmetric for example if we reverse its left part we don't get the right part okay how to solve this problem to check if a tree is symmetric what we really need to check is that left and right subtrees are symmetric to each other we will focus on that you need to know that for three problems the solution is usually done recursively we process the root then we call the function on both subtrees and we combine the results for example to get the sum of elements of a binary tree we have the value of the root then we recursively call the function on both subtrees to get the sum of their elements after doing so we return root value plus sum of left subtree plus sum of right subtree this way of traversing is called depth first search and it's how we solve the majority of three problems let's go back to our problem we have two trees root one and root two and we want to check if they're symmetric to each other first case both trees are empty in that case we return true because there's still some metrics to each other there is nothing that breaks the condition second case one tree exists but the other one doesn't in that case would likely deduce that they're not symmetric because the node of the tree that exists doesn't even exist in the other one it's empty we return false third case both trees exist but their roots don't have the same value here also they are not symmetric because in symmetric trees the roots must have the same value because when we reverse a tree the root position doesn't change and last case both trees exist and they have the same root value in this case we still can't say that there's a metric because okay the roots have the same value but we still need to check their subtrees having the same root value is not enough to say that they're symmetric and if we take two symmetric trees we can notice that they have the same root value though the left subtree of the first one is symmetric to the right subject of the second one and that the right subject of the first one is symmetric to the left substrate of the second one we verify that root values are equal so we need to check the remaining two conditions and how are we gonna do so we're gonna do so recursively because if you think about it we're building a function that checks if two binary trees are symmetric which is exactly what we need this is why we'll use the same function it may sound hard to understand but this is what recursion about a function calling itself if you're not familiar with recursion you should really have a look at it before continuing this course because we will use it again in a further problem if you want to learn a question you can check the course i made on the subject it's a complete and well appreciated course that will let you be comfortable with your question let's go back to our problem we said that we used the function we're making we said that we use the function we're making we call it on root one.left and root.right we call it on root1.right and root2.left and we check that both calls return true it means that both conditions are verified that the left subject of root 1 is symmetric to the right subtract root 2 and that the right subject of root 1 is symmetric to the left subject of root 2. let's quickly see an example we want to check if this tree is symmetric so we check if its subtrees are symmetric to each other they have the same root value so we check left subtree of root one with right subtract root two same root value we check left subject of root 1 with right subject of root 2. same root value we check left and right same root value and their children are both null they will return true same root value in symmetric children all conditions are respected it returns true now right subject of root 1 with left subject of root 2 they have the same root value their children are both null both closer to and true all conditions are respected the color turns true back to here all conditions are respected the call returns true now writes up your fruit 1 with leftover root 2. they don't have the same root value the color returns false not all conditions are respected the call returns false we don't even need to check the second call because we already have a non-respected condition the call returns false the initial call return false so our tree is not symmetric in code let's first make our r symmetric function it takes two trees as parameter root one and root two first case both don't exist without clear turn true second case one of them exists but the other one doesn't and third case they have a different root value in both of these cases the trees are not symmetric so return false we'll write if root 1 is none is not equal to root 2 is none or root 1.val is not equal to root.val we return false and now in the last case both trees exist and have the same root value we still need to check subtrees we check that root1.left is symmetric to root to the right and that root1.right is symmetric to root2.left we do so by recursively calling the function twice once with root1.left and root2.right and once with root1.right and root2.left both of them need to return true so return the results combined with the add operator and now when our main solution function is symmetric we first check that the input tree exists because if it doesn't we can directly return true an empty tree symmetric else we check that subtrees are symmetric to each other with the function we made now we return r symmetric root.left and root.write that's it for the time complexity we're just performing a depth first search traversal of the input tree and dfs costs of anti more n is the number of nodes and for the space complexity a symmetric tree has to be balanced and the coolstack saw is needed by a recursive function that traverses a balanced binary tree is an offload add we got an offload and space complexity that's it for this lecture we've seen an interesting problem on trees i hope that you've been able to understand the solution see you in the next lecture welcome back to the course in this lecture we will solve the generate parenthesis problem a problem that we will solve using backtracking by the way in this course i try to include problems on different patterns binary search hash table backtracking depth first search and so on but one problem in each is not enough this is why you need to study more problems for that i suggest you to have a look at my 50 popular coding interview problems course it contains 50 problems different from the ones in this course about many data structures and algorithmic techniques you can have a look at the curriculum and reviews on the main page anyway let's go back to our problem we are given an integer n and we are asked to generate all valid combinations of n pairs of parenthesis for example with n equal to 3 here are all the valid combinations first of all what does a valid combination mean and how to check if a combination is valid a combination that contains one type of parenthesis is valid if every opening parenthesis has its closing parenthesis and it doesn't have a closing parenthesis without having an unused opening parenthesis before it let's see some examples this combination is invalid because these opening parenthesis don't have closing parenthesis the syntax is invalid second example this combination is invalid because we have a closing parenthesis without an unused opening parenthesis before it last example this one is valid because each opening parenthesis has its closing 1 and there is no closing parenthesis without an unused opening one before it now how to check if combination is valid to do so we can maintain a stack where we push when we found an opening parenthesis and we pop when you find the closing one the condition is that we don't try to pop from the stack when it's empty and the stack has to be empty after we finish traversing the combination trying to pop from the stack when is empty means that we have a closing parenthesis without an available opening one before it all ones what we found before have been popped by all their closing parentheses and the second condition is that the stock must be empty at the end because still having elements in the stack after traversing means that we have opening parenthesis that didn't gather closing one yet in both cases the combination is not valid and because we have only one type of parenthesis round ones we don't even need the stack we can just use a variable def that represents the difference between the number of opening parenthesis and the number of closing points it has to be zero at the end and if it becomes negative during the process then it's not valid okay but what's the relation with backtracking in this problem we're not asked to check if a combination is valid we're asked to generate all valid combinations of n pairs and we use backtracking because at each step of building the combination we have two possibilities adding an opening parenthesis and adding a closing one and because we want all combinations we try them both because we get new ones when we add an opening one and all the ones when we add a closing one also in backtracking we can have a condition where we backtrack without continuing it when we know that the actual branch won't lead us to a valid solution in our case it's when death becomes negative it means that the combination we built until now isn't valid it's useless to continue building it we know that it won't give us a valid combination anyway let's see an example with n equal to 3 we'll get this recursion tree if you're wondering why and starts at 6 it's because the n given as input represents the number of pairs and in n pairs we have 2 and parenthesis so we multiply by 2 because we're adding one parenthesis by level when we go to the left we add an opening one in increment diff and when we go to the right we add a closing one and decrement diff we can notice that we have branches that have been stopped earlier those are branches where div becomes negative as soon as diff becomes negative we stop also even with branches that created the combination of n pairs we don't take all of them we take only those where dif is equal to zero remember the validity condition so at the end here are the combinations that get added to our combinations array in code we start by creating a recursive function rack that will fill the combinations array it takes us parameters n the number of remaining parenthesis to add diff the difference between opening and closing brackets calm the actual combination that we're building and comps the array of combinations the one that we're searching for in our problem the first base case is when diff becomes negative here we darkly backtrack without clear return to go back to the previous call the second base case is when we've been able to add all the parentheses we've been able to build a combination but in this case we don't automatically add it to our comp's array we first check if diff is equal to zero remember the condition so if diff is zero we draw the parenthesis of our combination to form a string and we add it to our valid combinations array else we have the recursive case we said that we have two possibilities adding an opening parenthesis and adding a closing one therefore we will have two recursive calls for the first one we add an opening parenthesis to our combination then when we call n becomes n minus 1 because we have one less parenthesis to add and div becomes div 1 because remember that we add 1 when we add an opening parenthesis after the call we remove the opening one we added to put a closing one after doing so we call the function again but this time diff becomes d minus one remember that we subtract one when we add a closing parenthesis and after the call we remove the parenthesis we added to backtrack to the previous call and we made our function by the way we can ever optimize a little bit by darkly returning if d is greater than n because if it's the case it means that we don't have enough remaining parenthesis to close all our opening parenthesis diff is greater than n so we just return if you're confused about what's happening here have a look again another recursion tree and most importantly you should learn more about recursion and backtracking the method we're using here to generate all possible combinations it's common to a lot of problems you should really be comfortable with it and now in the main solution function we first create an array comps where we will put our valid combinations and we call our recruiting function to fill it but the tricky part here is that we pass two times n as an argument not n because the n given as input represents the number of pairs not the number of parentheses and a pair is made of two parentheses so we pass two times n our combinations will be of length two times n after filling comes we just return it for the time complexity in the worst case when n is zero we have a cost of n to draw the parenthesis we write t of zero is equal to n and in the recursive case and again we're moving from the combination cost of one but we have two calls where the input size gets reduced by one and is becoming n minus 1. in total t of n is equal to 2 times c of n minus 1 plus 1. now we keep replacing t of n is equal to 2 times t of n minus 1 plus 1 so t of n minus one is equal to two times t of n minus two plus one we replace we simplify and we get four times t of n minus two plus three we replace again t of n minus two is two times t of n minus three plus one we replace we simplify and we get eight times t of n minus three plus seven this recurrence relation is a common one we can already notice the general form its t of n is equal to two power k times t of n minus k plus two power k minus one we have the value of t of zero so we need to find the value of k to go to t of zero n minus k equal to zero so k is equal to n where plus k by n we get t of n is equal to 2 power n times t of 0 plus 2 power n minus 1. we know that t of 0 is n we replace we get t of n is equal to 2 power n times n plus 2 power and minus which gives an o of n times 2 power and time complexity note that here n represents the length of the combination which is 2 times the number of pairs given as input also n times 2 power n is not the exact power the number of operations will be less than that due to branches where we backtrack earlier o of n times 2 power n would be the exact bound if we had no condition on our combinations if you don't know the technique i used to find the time complexity over this recursive function it's called the substitution method it's an important technique to know you should learn about it and for the space complexity we have m plus 1 for the corsac size the length of the longest branch in the recursion tree but we also need to count the required space to store the combinations the length of a combination is at and it has two possible characters so we have two power and possible and combinations length of each one of them is n so we need n times 2 power and space to store them we get of n times 2 power and a space complexity but not all of them are valid we will need way less than n times 2 power n n times 2 power n is just an upper bound in reality the required space for combinations is n times the number of elements after filling the comps array we reached the end of this lecture i hope that you understood this backtracking solution and see you in the next one welcome back to the course in this lecture we will solve the gas station problem we are given a circular list of gas stations where we can go from station i to the station i plus one and the last one goes back to the first one and we are asked to find the index of the station from where we start to be able to traverse all the stations and go back to the initial one without running out of gas note that we can only move forward the gas tank starts empty gas of i represents the amount of gas at the station i cost of i represents the cost to go from the station i to the next one the answer is guaranteed to be unique and if the station we're switching for doesn't exist we turn -1 we deduce that there will be at most one station from where we can traverse and be able to go back for example if we have these 10 stations the output is 8 because when we start from station 8 we can go back to it without running out of gas we start with no gas as mentioned in the problem we add 4 gas of station 8 and we pay 1 to move to the next station we add 5 guests of station 9 and we pay 2 to move to the next station we add 1 and pay 5 we add 5 and pay 2 we add 3 and pay 2 we add 3 and pay 8 we add 5 and pay 2 we add 3 and pay 4 we add 1 and pay 2 we add 3 and pay 5 and we've been able to go back to station 8. you could see that the amount of gas never became negative which is not the case for all the stations for example with station one we add five and pay two we add three and pay two we add three and here if we pay the a to move to the next station the amount of gas becomes negative which means that we can't continue the station we started from is not the right one let's solve this problem a beautiful solution that darkly comes in our mind is to simply simulate what happens with every station and if we find one that respects the condition we return its index let's try it with our example with the first one we add 1 we pay 5 and the cost becomes negative darkly eliminated next one we add five and pay two we add three and pay two we add three and pay eight and the amount of remaining gas became negative not this one next one we add three and pay two we add three and pay eight and remaining became negative next one we add three and pay eight remaining became negative next one we add five and pay two we have three and pay four we add one and pay two we add three and pay five and remaining became negative not this one next one we add three and pay four negative next one we add one and pay two negative next one we add three and pay five negative next one we have plus four minus one plus five minus two plus one minus five plus five minus two plus three minus two plus three minus eight plus five minus two plus three minus four plus one minus two plus three minus five and we've been able to go back to the station from where we started we darkly return it because we know that the answer is unique in code we create a function that takes us parameters the array gas the array cost and the index of the station from where we start the goal of this function is to tell us if we can finish the cycle by starting from the station start we first need a variable remaining that stores the remaining amount of gas we also need the variable to store our actual position our initial position is the station from where we start so initialize i at start and we also need a boolean variable started to know if we started working yet or not we need this variable in our loop condition we need to keep looping until we go back to start we write while i is unequal to start or not started here not started is important because if we don't use it we won't even enter the loop remember that i is initialized initializer start so i and start are equal we want them to be equal but after traversing the cycle not now this is why we need the variable started to know if we're in the case where i is equal to start because we didn't start yet or because we traverse the cycle and i went back to start let's continue inside the loop we set starter to true because we started then we update remaining we said that at the station i we add the amount of gas in it and we pay the cost to move to the next one so we add gus of i and subtract cost of i after doing that if remaining becomes negative it means that we couldn't go back to start we don't have enough gas return false else we move to the next station the next station is usual at i plus 1 but we need to add modulus of the number of stations to handle the case where we're at the last station i becomes i plus 1 and models and it goes back to zero we write i becomes i plus one modulus the number of stations and if we finish the loop it means that we've been able to go back to start return true now in our main solution function we just try the function we made on each station as we did in the example and we return the actual station as soon as the function returns true and if the function fails with all stations we return -1. for the time complexity because the answer is unique a possible worst case is this one because by starting from station zero we traverse n stations before getting a negative amount from station one we traverse n minus 1 from station 2 which reverses n minus 2 and so on we get the sum n plus n minus 1 plus n minus 2 and so on until 1. after simplifying we found that it's an off n squared we get an off n squared time complexity and a constant space complexity because we're not using input size related variables of n squared is slow for this problem we're getting off n squared because for each station we're traversing again almost all the stations let's see how to optimize it the main thing that you need to understand for the second solution is that if we start from a station at the index start and reach a negative amount of the station i then all stations between start and i inclusive are not valid we don't need to try them we darkly jump to iplus one let me tell you why we have the case where gas of start is smaller than cost of start here the loop stops darkly because remaining becomes negative it stops at start so there are no other stations involved nothing to talk about here but when gas of start is greater than or equal to cost of stock the loop moves to all the stations it can traverse a bunch of stations before remaining becomes negative for example here when we start at station 4 remaining becomes negative at index 7. it means that stations 4 5 6 and 7 are all invalid we start again from i plus one eight but why guess of start is greater than or equal to cost of start in our case the difference is three and this three is considered as an advantage over starting from next stations it's like a bonus by starting from station four we have three more gas than starting from the next one station five and even with that bonus we didn't have enough gas to do a full cycle we stopped at station seven evan with that bonus we couldn't go over station 7 so how do you want to go over it without that bonus it's like you have 500 dollars and they aren't enough to buy a particle pc then you say these 500 weren't enough i'll try with 400s maybe they will be enough it's illogical and this is why when remaining becomes negative we don't try again from the station that comes after the one where we started we skip all the ones we traversed we start again from i plus one with our example we start from the beginning remaining becomes negative we start from i plus one we add five and we pay two remaining becomes three we add three we pay two remaining becomes 4 we add 3 we pay 8 remaining becomes -1 negative what we're gonna do now is to darkly start again from here without trying again from stations two three we'll add five you pay two remaining becomes three we have three we pay for remaining becomes two we add one we pay two remaining becomes one with f3 we play five remaining becomes minus one negative once again we'll directly start again from i plus one we add four we pay one remaining becomes three we add five we'll pay two remaining becomes six and we finish traversing the array the candidate is station eight but it doesn't mean that it can do a full cycle it just means that we can reach the end of the array without reaching a negative amount of gas we didn't check the part before it this is why i said candidate it's a potential valve station we don't know yet to say that a candidate station is valid by starting from there remaining must never become negative when traversing the path from candidate to the end but also when traversing the path from the beginning of the array to candidate exclusive the first part of the cycle is what we verified during the traversal and for the second part of the cycle we just calculate the sum of gas from zero to candidate minus the sum of costs from zero to candidate the result represents the remaining gas after traversing that part if by adding it to remaining the result stays positive then candidate is a valid station else we have no value station for example here the sum of gas from 0 to candidate exclusive is 24 and the sum of costs from 0 to candidate exclusive is 30. the difference is 1 is 6. what remain from candidate to the end is 6. what remains in the pot before candidate is -6 by adding them together we get 0 which is positive so candidate is the value station question what if we got a negative result here then would likely return -1 because there is no valid stations but what if the value station comes after the candidate it's impossible once again the station from where we started candidate has an advantage over next stations we know that gas of candidate is greater than or equal to cost of candidate so even if with that bonus we get a negative remaining amount of gas it will also be the case for next stations let's jump to the code to understand all of this remaining starts at zero and same thing for candidate because at the beginning we assume that the first station is the candidate the potential valley station now we start traversing stations for each station we update remaining gas we add gas of i and subtract cost of i and if remaining becomes negative we said that we start again from ipod 1 it becomes a new candidate and remaining becomes 0 because we will start again after the loop we calculate remaining gaps of the part before candidate the sum of gas minus the sum of costs of the part from zero to candidate exclusive now we have three possible cases we have the case where candidate is equal to n it means that we reach the end of the array without finding a potential station no station made it to the end of the array we return -1 second case we have a candidate but when adding priv remaining we found the negative result it means that it stopped somewhere in the path from zero to candidate we return -1 and third case we have a candidate and remaining plus prime remaining is not negative so candidate is the value station from where we start to be able to do a full cycle we return it in code if candidates is equal to length of gas the number of stations or remaining plus player remaining smaller than zero will return -1 else we return candidate we can even keep track of prep remaining in the first loop to avoid traversing again to calculate the sums for the time complexity we just have a loop that does any iterations all other operations are in o of one we get an off and time complexity where n is the number of stations much better than of n squared add a constant space complexity because we're not using input size related variables basically in the solution we search for the candidate the station that made it to the end of the array without reaching a negative amount of gas then we check if it still bears up when traversing remaining stations those in the path from the beginning of the array until going back to it here is the end of this video i hope that you understood the optimal solution and see you in the next one welcome back to the course in this lecture we will solve the course schedule problem we have n courses labeled from 0 to n minus 1 in classic that we need to take but some of them are prerequisites to other we cannot take a course before taking the other one and we have to determine if it's possible to finish all the courses so we are given an integer n representing the number of courses and an array prerequisites where prerequisites of i is equal to a b means that you first need to take the course b before taking the course a for example if we have this input the output should be false because to take course 3 we must have taken code 0 and to take course 0 must have taken course 1 and to take course 1 we must have taken course 3. which is impossible it's like we have a dependency cycle this is why we cannot finish all the courses we return false but with this input the output is true we can take course 0 then course 3 then course 1 then course 5 then course 2 then course 4 each course will have its prerequisites satisfied when taking it how to solve this problem here we have elements courses and relationships between them a course being a prerequisite of another course and every time you face this situation having elements and relationships between them you should think of using a graph i'm not saying that it will always give the best solution but even if it doesn't it will at least give you a way to visualize the problem with vertices and links between them in our case vertices represent courses and edges represent dependencies and add from u to v means that we first need to take the course u before being able to take the course v okay now we build our graph we got a directed graph what we will do with it our goal now is to search for a dependency cycle if we find one it means that it's impossible to finish all the courses return false else if we don't find one at all it means that it's possible to finish them all return true basically we're searching for a cycle in a directed graph in a linked list a classic way to check if there is a cycle is to traverse a linked list while saving visited nodes and if we step on a node that we've visited before it means that there is a cycle we can think of applying the same logic for graph which are works with depth first search for example while using a set of visited nodes and if we step on a node that has already been visited it means that we have a cycle returned false by the way if you don't know about depth first search it's a way of traversing trees and graphs by diving deep into a direction until we can't move forward anymore go back try another way and so on i made a youtube video about the subject that you can watch you need to know about dfs before continuing this video it's a prerequisite intended pun but this strategy doesn't always work here is a counter example we have this graph let's start traversing we start for example from 2 we put it in visit it we move to 0 we put it in visit it we move to 3 we put it in visit it this one has no outgoing address we backtrack this one has no remaining neighbors to traverse we backtrack from here we move to the second neighbor one we put it in visit it we'll move to four we put it in visited then from here we move to three and it's already in visited so our strategy would return false which is wrong because we can totally finish all the courses here we can start with two then zero then three then one then four all prerequisites are respected what's the solution then well let me first talk about topological sword we have a directed graph where vertices represent tasks and an add from u to v means that u is a prerequisite of v topological sort is the process of finding a linear ordering of vertices such that each vertex comes after its prerequisites in other words for each add from u to v v must come after you in the ordering for example for this graph here is a valid ordering note that a valid ordering is not always unique it's possible to find all the orderings that satisfy the condition but topological sort is not always possible it's not possible when the graph contains a cycle like this one b is a prerequisite of c c is a prerequisite of d d is a prerequisite of e and e is a prerequisite of b so we have no way to order them fortunately while performing the topological sword we can detect the existence of a cycle if it happens we just stop and say that we cannot have a valid ordering of vertices and it's exactly what we want to do in our problem we have courses some of them are prerequisites to other ones and we want to know if we can take all the courses in other terms if a valid ordering