otten the wrong answer at this point after we append it we check is this a leaf node it is a leaf node it does not have any children so at this point we found our answer this is the first time we're returning true so we're going to return true so we're going to return true from two back up to the parent over here and from here we know we were calling leaf path on the right subtree over here and so since that evaluated true we can return true from there and then all the way at the root node we're going to execute this again and it would return true so then we did find the path and in our path variable that we passed in it would now be populated with the path that we were looking for four one two so backtracking is an algorithm that can actually be used on more than just binary trees it's similar to the recursive algorithms we talked about earlier like the Fibonacci sequence but understanding the fundamentals that we talked about here will serve as a really good foundation for understanding more complicated versions of backtracking the ideas are the same where you maintain some kind of solution keep adding values to it as we're trying to search for a solution but as we find out that we went down the wrong way we pop from the solution then by the way in this case since in the worst case we would have to traverse over the entire tree the time complexity for both of the backtracking algorithms we talked about would be big O of n where n is the size of the input tree and that's usually the case for backtracking it usually is a brute force algorithm so it would in the worst case run over all possibilities in this case that means the size of the tree next let's look at another really important data structure which is called a heap slash a priority queue let's start with kind of the meaning behind priority queue we already talked about regular queues where first value in is the first value out of the queue but we might want to order the queue a little bit differently instead of ordering it by the first in first out we could order it based on some type of priority value for example we add some values like 7, 3, 9 so now which value are we going to pop first well it depends on the priority of the values there's typically two variations of this one is you know the minimum priority and the other is the max so in this case we could prioritize the minimum values first so if we did it like that we would first want to pop the 3 and then pop the 7 and then pop the 9 now this is dynamic meaning as we add values we might choose to pop a different one right now we want to pop the 9 if we pop a next value but if we add a smaller value suppose a 4 in that case we're going to want to pop the 4 first and then pop the 9 that's if we did it based on minimum of course we could do it based on the maximum as well in that case we do 9 first then 7 and then 3 so the idea is actually pretty straightforward now the reason we have two different names here is kind of the same idea when we originally had queues those queues were actually implemented with linked lists so in this case the relationship between these two terms is similar the interface that we're using is called a priority queue right that's kind of the idea behind it but underneath the hood that's implemented using a heap so people kind of use these two terms interchangeably so you'll see that a lot I'll probably be doing the same and outside of this course people use these generally interchangeably I think it's more common to use the term heap just probably because it's shorter to be honest but in this case a priority queue is going to be implemented with a binary heap which is this data structure that we have here this is what we're going to talk about and by the way that heap that binary heap could either be a min heap or a max heap depending on how we want to implement our priority queue whether we care about minimums or maximums I'm mainly going to be focusing on the minimum case generally it's more common to use a min heap rather than a max heap that's what this is here but the implementation is pretty much exactly the same it would just be swapped you know instead of taking minimums we would take the maximums I'll talk about that more now now at first glance this looks like a binary tree and that's because it is a binary tree but it's not a binary search tree and you can tell because the root here is 14 with a binary search tree every value in the right subtree would be larger than 14 which it is in this case and every value in the left subtree would be smaller than 14 but that's definitely not the case actually when you look at the root node here it's smaller than every single descendant in the tree that's going to be the order property that we talk about in a minute but let's first start with the structure property a binary heap is essentially a binary tree that is considered a complete binary tree so a complete binary tree basically means we have a tree where every single level in the tree is going to be completely full there's not going to be any holes anywhere except possibly the last level the last level might have some holes but every other level in the tree is not going to have holes so you can see that that requirement is satisfied in this case now maybe if we're missing this node it would not be the case because we're supposed to have four nodes in this level but we only have three so if any of these four nodes is missing we don't have a complete binary tree if any of these two nodes are missing we don't have a complete binary tree now the last level here we can have some missing nodes that's perfectly okay but if we insert a node over here now regardless of the value tell me is the structure property satisfied definitely not because because while the last level has some missing nodes that's okay the second to last level now also has missing nodes that's definitely not okay now another thing about the structure property as we add values you can see they're added left to right it's not enough that only the last level is allowed to have missing nodes if it does have missing nodes they should be at the end of that level meaning that as we add nodes to it like assuming that this level doesn't even exist as we add nodes we'd first add the node here and then add the node here and then add a node here then here then here then here so it's kind of intuitive that we want to have a complete binary tree and as we add nodes we're adding them in a pretty straightforward way right in the next available position essentially so that's the structure property next is the order property remember the whole point about having this heap aka priority queue is about finding either the minimum or the maximum value really quickly really easily that's a that's the entire point of having a priority queue in this case we're talking about minimums so it makes sense that we would want the minimum value among all of these to be at the root because from the priority queue we want to be able to find the minimum easily by looking at the root we can do that pretty quickly we can look at it in oh of one time as long as we're not removing this so what order property should we give this to do that well we should say recursively for this tree we want every value in the left subtree to be greater than 14 and every value in the right subtree to also be greater than 14 that's the only requirement we have but it's recursive that means that for this subtree for the root node of this subtree we want every value in its left subtree to be greater than 19 that is the case as you can see here and we want every value in the right subtree to be greater than 19 that's also the case as you can see here same thing for 16 19 should be greater than 16 it is 68 should be greater than 16 and technically in heaps we're actually allowed to have duplicates you can see we have two 19s so so actually when we look at this value we don't necessarily need every value in the left and right subtree to be greater than the node than the root node it's okay if they're equal as well that wasn't true for binary search trees but it is true for heaps we could have some duplicates and that's okay it's just that for every node all the descendants have to be greater than or equal to that node at least when you're talking about min heaps which is what we're doing here obviously for a max heap we would want the opposite we would want for every node all of its descendants should be smaller than it because in that case we would want the maximum to be the root now one of the most interesting things about binary heaps is that while we draw them as binary trees that are connected via pointers and nodes and all that they're actually implemented under the hood using arrays and another interesting thing is that we actually don't start at index zero for this array we essentially don't care about the zeroth index and I'll show you why so what we're going to do is put the root node at index one that's always going to be the case the root is always going to be at index one so we got the root node next we fill in the next level we go left to right so for the 19 we're going to put it at index two for 16 we're going to put it at index three and we're just going to continue going like this but one thing I want to point out is that we know the root is at index one to get its left child we go to index two to get its right child we go to index three let's continue this and then I'll show you what's the pattern behind it and then we'll understand exactly why we use arrays rather than nodes and pointers so filling in the next level we have 21 which goes at index four 26 which goes at index five 19 which goes at index six and 68 which goes at index seven and the last couple nodes we have 65 and 30 they're going to go in index eight and index nine so the main reason we skip index zero is to get the math to work out what do I mean by math well for index one to get its left child we basically have a few formulas so for any node so for 14 which is at index one to get its left child we simply take the index that it's at and multiply by two so we know that its left child is going to be at index two which is 19 that is the case over here we know its right child is going to be two times i plus one i in this case is one so two times that plus one is going to be over here so just the next position over 16 is its right child and as we continue so for 19 we want to get its left child we multiply by two we get 21 that is the case to get its right child we multiply by two plus one that would land us over here 26 is the right child now these properties by the way are only true because we have a complete binary tree which means every node is filled except possibly the last level this would not be true for a regular binary tree or a regular binary search tree that's why we use these for binary heaps because they're complete binary trees that's also why we can use this array to represent the binary tree because if we had holes and stuff over here right like this 26 doesn't exist then it wouldn't really make any sense to use an array because we just have random holes everywhere using a regular binary tree but with a binary heap like this one what we're never going to have holes that's the entire point of having a complete binary tree and by the way if we can go from any node multiply by two to get its left child multiply by two plus one to get its right child then from any node we should also be able to go to its parent and we can do that by dividing by two now it's pretty obvious why if we multiply by two here to get the child we can divide by two to get to the parent but why is that also true for the plus one case if we multiply by two plus one we get to the child and then if we divide that by two we get to the parent why is that the case well pretty much because when we divide by two we round down we know that this number is always going to be even you know we're multiplying some number by two so by definition it has to be even we know that this number is always going to be odd because we're we have an even number and we're adding one to it this is the odd number nine when we take this and divide it by two we're essentially getting rid of this two so we're left with i plus one which is also divided by two and we know we always round down pretty much every language will round down automatically with python you have to use double slashes but we can still do that and when you round down this term is basically eliminated and then we're left with a single i that that would be the exact same if we took this and divided it by two we would just get rid of this we'd be left with a single i so when you take nine divide it by two you get 4.5 you can round that down that leads us back to four so for example if we wanted to you know start at this node we'd start at index one suppose we want to go to the left we would just take its index multiply by two that would lead us over here in the array now suppose from here we wanted to actually go right we would take the index multiply by two which leads us to four plus one which leads us to five then we'd be here or here using the tree representation and from here maybe we want to go to the left child so we take the index and multiply by two that leads us to 10 that's out of bounds because it's greater than the last index therefore you know we reach null so you know it basically can be used the exact same as we traverse a regular tree as long as you have these properties you can traverse it as if these were pointers so this is kind of a good introduction to heaps the structure property the order how they're implemented using arrays next we're going to talk about how we can actually insert values into a heap and remove values into a heap while maintaining the structure and the order properties because that's very important without these properties we don't have a heap anymore so now let's talk about inserting into the heap aka pushing into the heap that's usually the term that's used when it comes to heaps or priority queues so if we want to push a new value into the heap suppose we want to push the value 17 well thinking about the structure property the obvious place we would want to put the node is over here I mean we could I guess put it here but then there's like a hole over here we want these to be contiguous we always want to insert in the next available position we definitely don't want to put it here so we're going to put the value here it's a little bit messy over here but bear with me so we have a 17 over here so the good thing is that the structure property has been satisfied what about the order property well remember this is a main heap so for every node we want its children to be greater than it so for this node that we just inserted we want its parent to be smaller than it so let's compare the value here to the parent by the way in our array it's going to look something like this the 17 would have been inserted over here and we want to compare this to the parent how do we get the parent take the index divide by two so from 10 we would compare it with what's at index five clearly you know that's the same value and in this case the parent is actually larger but it should be smaller I mean technically they're allowed to be equal but in this case they're not equal so these should be reversed the smaller one should be the parent so what we do here is just simply swap the two values in our array so it's a bit messy but we swapped the values in our array and that means that the tree representation would look something like this and then we would continue the algorithm for the node now that we you know moved over here we want to compare it to its parent now we want to make sure that the order property is being satisfied we know of course it's satisfied everywhere else in the tree but with this new node it might not be satisfied so we look at it compare it to its parent its parent would be five divided by two rounding down so at index two in that case you can see that that's you know also the same node so the parent should be smaller but the parent in this case is larger than the child so again we want to swap these two values so now we swapped these two values 17 is at index two it's over here 19 was moved down here now before we compare this one to its parent I want to mention we moved the 17 up here the reason we don't have to compare this now to its left child and pretty much everything over here is because we already knew 19 which was in this position was valid 19 was allowed to be here because 19 was smaller than all of the values over here but now we replaced 19 with a value even smaller than it which is 17 so therefore 17 must also be smaller than all the values over here that's just basic math and logic so we don't have to compare it to every single value that's a descendant of it but now doing our last comparison comparing this to the root node 17 should be greater than 14 and in this case it actually is we compare this to the parent and the order property actually is being satisfied so in this case we know we're allowed to stop that's how you insert aka push into a men heap it would work similarly with a max heap just you know the order would be the opposite now in the case that we had an even smaller value suppose instead of 17 we had a value like 10 in that case we would end up swapping it with the root node then 10 would be over here and then we 10 would not have a parent right this is the root node it would not have a parent so at that point we would stop so either we go all the way up to the root or we get to a spot like this one where the order property is already being satisfied now taking a quick look at the code of what we've talked about so far this is what the class implementation of a heap would look like so for the constructor we would initialize the heap as just a single value array where the value in this case is just a zero that would just be kind of the dummy we know that the zeroth index is actually not going to be used so this is essentially an empty heap that we've initialized now to actually push values into the heap we would do what i just talked about which is taking that new value that we're inserting and appending it to the heap so putting it at the last index so the heap itself remember is just an array a dynamic array but essentially an array then we would get the index that we just inserted at which would be the length of that array minus one so we would be at index 10 and then we would do something called percolate up that's pretty much what i just talked about where we insert the node here the node that we did was 17 and then we percolate up which is basically shift it up while the order property is not being satisfied so you know we shifted 17 up here then we shifted it up here and then we stopped so this code is essentially doing the exact same thing you can see that index i which would be 10 initially is being compared to its parent i divided by two in python we use double slashes when we want to round down but the general idea is going to be the same in any language we're going to compare it to its parent if it's less than its parent then we're going to swap it with its parent so we you know have a temporary variable move the parent into the child position move the child into the parent position and then we want to take our index and then divide it by two because we just went from here to the parent position and now we want to potentially from here swap this with its parent or at least compare it with its parent and then we would continue the loop to do that comparison and keep doing that until this is no longer true until the node is in the correct position what would be the time complexity of this by the way well essentially the height of the tree and in this case we actually know that the tree is always going to be balanced that's kind of the point of having a complete binary tree so in this case we can definitively say that the time complexity is basically going to be log n where n is the number of values in our heap aka in our array next let's talk about removing from the heap aka popping from the heap we don't actually specify a value that we want to pop because remember our priority queue is about popping the priority element and we know that the minimum is going to be at the root so that's the one that we're always going to pop so it seems simple enough but actually popping is more complicated than inserting if we just wanted to read the top element we just wanted to read what the minimum element is in our priority queue we could just go to index one and then return that that would be easy but to actually pop it is going to be a little bit more complicated because we have to maintain the structure and order properties now after removing this node or removing that value from the array your first instinct might be to just take the minimum of its two children and replace it with that that would kind of maintain the structure because we have a hole here we need to fill we can fill it with one of its children and the order property we want to make sure that the minimum value goes here so the minimum must be one of these two children because all of these are going to be greater than 16 and all of these are going to be greater than 19 so the minimum has to be one of these two it seems simple enough but if we do it like that we're going to put the 16 over here which works and then we have to replace this with the minimum of its children which is 19 so we remove the 19 and then put the 19 over here now the order property is being satisfied but not the structure property notice how this level is full this level is full this level is not full we introduced a hole over here we didn't want to do that if we're removing a node we should remove it from the bottom level but we weren't able to do that this is why this way doesn't work it's a good idea but it doesn't work to get pop to work and to maintain the structure and order property and do it efficiently we actually have to use sort of a genius technique but it's actually a relatively simple one once you know it what we actually do is remove the 14 and replace it with the last value in the array the last node in our tree which would be over here because remember that's the way to maintain the order property so we remove this node and move that 30 over here and of course under the hood this would actually be going on in our array but i'm not going to be drawing all that out because it's actually going to get kind of complicated here now the good thing here is we satisfied the structure property but not the order property but we can fix that instead of percolating up like we did when we inserted a node we can do the opposite by taking this and percolating down because we don't know that this is in the position it should be at we need the minimum to be in this position we know that this is probably not the minimum the minimum is one of these two so what we do is we take the minimum of our two children the left and right the minimum is 16 so now we compare that minimum to this node 30 which one of these is smaller 16 is smaller therefore we're going to swap these two nodes we're going to put 16 over here and 30 is going to go down here now we already know 16 is smaller than all of these because it's smaller than 19 which is smaller than all of these remember heaps have a recursive order property but we're not done yet because we need to satisfy that recursive order property 30 should be smaller than all of its descendants meaning it should be smaller than both of its children so let's take the minimum of the two children it's 19 is 30 smaller than 19 nope that means we need to perform a swap so let's swap these two values move the 19 to be in this node and the 30 will now be in this node it's definitely gotten pretty messy sorry about that but we're pretty much done at this point so it's really counterintuitive that we would do it this way we would literally just take the last node move it to the root and then percolate down but that is the most efficient way to do it that's why I say it's a genius thing to do because you wouldn't really come up with it but once you know it it seems really simple and now our min heap is satisfying all the min heap properties now let's take a quick look at what the code would look like for this it's actually a little bit complicated so this is what pop would look like in python self is just a python thing which gives us access to all the member variables of the class we're assuming that this is inside some class I didn't write out all the code because we're already kind of running out of space but remember the ideas that we're talking about here could be applied to any language so when you pop from a heap first of all if our heap is empty there's nothing to pop and we know it's empty if the length of it is equal to one because remember we have like a dummy value in it so in that case we would return null if it's equal to size two that means we just have a single value the root we would remove it from our array and then return that value so we would return 14 and then remove this then we'd have nothing but the complicated case is if we have you know multiple values in the heap so we'd first assign the result we would take 14 copy it into some temporary variable because we know that's what we're going to end up returning but before we return that we actually have to delete it from the heap and then you know reorder the heap so next we're going to take the last value and move it into the root position so we're popping the last value in our array and then moving it to index one so we're putting the 30 over here next we set our i to index one that would mean our pointer is at the root node and then we would percolate down so this is a lot of code and there are many different ways to write this but what's important here is the logic so we know that there's multiple cases when we're at a node it could have both children it could have just a left child for example if this node didn't exist then this node would only have a left child it wouldn't have both children now it's impossible for a node to have a right child and not have a left child because that doesn't satisfy our complete binary tree definition so we only worry about the cases where we have two children or just a left child and the third case is of course we don't have any children so that's what these conditionals are all about the first case is where we have both children but before that first of all this loop of percolating down is only going to be running while we at least have a left child how do we know we have a left child well we take where we're at this is where our i pointer is at and we take two times i which will give us the pointer to the left child and we check that that is less than the length of our heap at this point that means we do have a left child so next in our loop we check do we also have a right child we know for sure we already have a left child but do we also have a right child we can check that by saying two times i plus one that's going to be the pointer here we do have a right child and if the right child is smaller than the left child which in this case is true 16 is smaller than 19 and the current node that we're at is greater than the right child in this case the current node that we're at is actually going to be 30 because remember we swapped it with this node down here so then we compare these two 30 is greater than 16 so all three of these conditions are met and they're anded together logic anded so therefore in this case we're going to end up swapping this with the right child and that's kind of the code down here to do that now if these were not satisfied for any reason then we would check maybe we want to swap this with the left child instead and we would only do that of course if 30 the current value that we're at is greater than the left child which is 19 so in that case we would potentially swap it with the left child but let's just continue it on this example so suppose we put 16 over here and we put 30 down here now we're going to go to the next iteration of the loop and before we actually continue to the next iteration of the loop we would want to update our eye pointer initially it was over here now we want to put it wherever we moved the node to which was here so we would take i and set it to two times i plus one so now our eye pointer is over here does this at least have a left child yes it does so that means possibly we might continue to shift it down let's check first of all does it have a right child yes it does is the right child less than the left child nope it's not so in this case we don't execute this first if statement we take a look at the else if else if 30 the current value is greater than the left child which is 19 then we swap it with the left child that's exactly what we're doing in this case so we moved 19 up here and we moved 30 down to this node and in that case we would set i equal to two times i because we're taking it from being pointing over here to now being pointing at the left child and then we would execute the loop again but we would see actually that in this case we don't have a left child anymore so we can stop the loop and at that point we would return the result which was the original root node that we were trying to get rid of now the last thing that i didn't kind of go over the last case would be you know suppose we had a 16 here we were moving the 16 down here we would compare it to its right child it's not greater than its right child we would compare it to its left child 16 is not greater than its left child that would mean that the last else case would be the one that would execute and that would basically break us out of this while loop so then the while loop would terminate and then we would return the result why we would execute it like that is basically we know that the node that we're percolating down is already in the proper position we don't want to swap it anymore we don't want to shift it down it's already where it needs to be that's why we would break out of the loop so this is definitely pretty complicated there are many ways of writing this i tried to write it where there are distinct cases for each of the things we're doing swapping right swapping left not swapping at all most likely you won't actually have to implement this in a real interview i think it's pretty rare but knowing the general idea of how this works can definitely be helpful now the time complexity is again going to be the height of the tree we know it's a balanced binary tree so the height is basically going to be log n so that's the big o time complexity and that essentially comes from a percolating down so we already talked about one of the advantages of heaps over binary search trees we can get the min or the max depending on what kind of heap that we've actually implemented we can do that in constant time whereas if you had a binary search tree you would need to do it in log n time because you have to kind of go all the way left in the tree now another advantage of heaps is how we can actually build them we know that when we have a binary search tree you have to insert a node every single time to build that binary search tree and the time complexity of that is n log n because we have to do n insertions and to insert each one takes log n time now for heaps you can do it the exact same way you can keep pushing elements into the heap and it will also take n log n time but there's actually a special algorithm with heaps which is sometimes called heapify or just build heap and the idea is that we could be given some set of values some list of values suppose in the format of an array like this and we can take those values and there in no particular order and we can take them and turn them into a heap that satisfies the properties of a heap and we can do that in o of n time let me show you how first of all if we're given an array in this format it doesn't even satisfy the structure property because we know that we don't really want to have a real value at the zeroth index so the simple thing to do here since we know these are already in no particular order let's just take this one and move it to the last position so at this point with this array what would our heap look like it would look exactly like this here we would have the 50 in the root position then the 80 then the 40 etc etc so we satisfied the structure property pretty easily but now we have to satisfy the order property and remember the order property is recursive it essentially means that for every single subtree every node should have a value that's smaller than all of its descendants so that's what we're gonna do for every single node we're gonna check does it have a value that's smaller than all of its descendants and that's because we're doing this for a min heap for a max heap you would just do the exact opposite so we can start at the bottom nodes and then move our way upwards so we can start at the last node over here but when we get here we know it doesn't have any children anyway so there's no point in doing any kind of comparison here same thing for this node same thing for this node and this node and this node they don't have any children so we have nothing to compare them with anyway so that's actually going to be true for half of the nodes so what i'm saying here is we can actually just skip all of these if we want to i mean we could start at the end and you know run the algorithm like that but there's no need to so to be a little bit smarter we can just skip half of these how would we do that in terms of code well we can get the number of nodes in the heap which is not necessarily the number of nodes in the array because we know we have a dummy so we would take the length which in this case would be 10 minus one which would give us nine because we know there's nine actual nodes here and then we would take that and divide it by two so nine divided by two rounding down of course would lead us to be at index four so 30 is the first node that actually has children taking a look at our picture that is definitely true if you don't end up remembering a fact like this it's okay to still start at the end and then go backwards anyway it shouldn't change the overall time complexity but this is how it's taught in most courses so we already know that all of these subtrees are valid they don't even have any children anyway but now moving to 30 let's check is 30 valid is it smaller than all of its children well it has two children it's smaller than 90 and it's smaller than 60 so we don't have to do anything notice how what we're actually doing here is the same percolating down algorithm that we talked about earlier when we were removing nodes this is the exact same thing what we're doing here essentially is going through every single node that has children and percolating down if it can be moved down so we did it for 30 we didn't need to you know perform any swaps now let's move to the next one 40 take a look let's compare it first does it have two children yes it does is the right child smaller than the left child yes it is is the right child smaller than the parent yes it is so we swap it with the right child so now that we've done that we already knew this subtree was a valid heap this subtree was a valid heap now we know this entire subtree is also a valid heap now let's move to the left we get to 80 that's this node over here does 80 have two children yes it does is the right child smaller yes it is so if we're going to swap 80 with something it would probably be this one so let's compare these two together is 10 smaller than 80 yes it is so let's swap 80 with this node over here so originally we already knew this subtree was valid and this subtree was valid now we know that we've you know percolated down for this that this entire thing is valid now when we are percolating down we are going to keep percolating down but at this point this one doesn't have any children anyway so there's nothing for us to do now we get to the last node in our array well the first node actually 50 it's the root so time to percolate let's compare the two children together which one of them is smaller 10 is smaller so if we're going to swap 50 with anything it's probably going to be this one let's compare 50 to 10 is 10 smaller than 50 yes it is so let's swap these two now it's definitely starting to get a bit messy now but let's try to continue we're almost done we're at the 50 now we're continuing to percolate this down let's compare the two children together because we have two children which one of them is smaller 30 is smaller so let's compare 50 with the smaller child 30 is 50 bigger than 30 yes it is so let's swap them and at this point I'm not even going to be maintaining this array because I think it's getting too complicated but you get the idea that anytime we perform swaps here under the hood there's an actual array that's maintaining all of that so the 30 is now going to be over here and the 50 is going to be over here now continuing to percolate this let's check we have two children still let's compare the two children this one is smaller now let's compare that smaller child with 50 is 50 bigger than 60 nope so 50 can stay exactly where it is we found the correct spot to put the 50 so now at this point this is what our heap would look like and tell me does it look valid to you or not well it's a little bit hard to read because it's gotten messy but the smallest value is in the root 20 is smaller than all of its descendants 30 is smaller than all of its descendants 50 is smaller than all of its descendants 80 doesn't have any descendants and the rest of these nodes don't have any descendants either so we definitely were able to do this now let's take a quick look at the code so the heapify algorithm is pretty similar to remove that we talked about earlier only in this case heapify or build heap you could call it is going to be passed in some input array and when we're when we have that input array we're basically going to take the 0th element and move it to the last position that's what append is doing it's basically pushing it to the end and then we're just assigning that array to be our heap we know it satisfies the structure property now it's time to satisfy the order property we have a current index we basically take the length of the heap subtract one and then divide it by two just like I talked about earlier this is integer division in python it'll round down but most languages will round down by default and current is going to be at this point just like we showed in the walk through and then we're going to have another copy of current we're going to call it i and at that point we're just doing the exact same percolate down algorithm I talked about earlier when we were doing removing or popping from the heap so I won't go super into detail it'll be the exact same idea but after we've percolated this down in this case we wouldn't actually do any swaps we're going to be done with this while loop and then we're going to take our current index and subtract by one because remember we're going in reverse order we're going to go to this node and then we're going to go to this node and then we're going to go to this node and for each of these we're going to percolate them down if we can now if you were actually implementing your own class for a heap you'd probably put this in like a helper function since it's being used not only here but it's also being used in heap pop so you could probably just put this in a helper function the reason I wrote this out explicitly is just to kind of show you exactly what is going on with the heapify algorithm now why is this heapify algorithm a linear time algorithm because at first glance it seems to be an n log n algorithm because we're going through pretty much every node in the tree and having to percolate it down percolating down might be a log in operation let's say so why is the big O time complexity a big O of n well first of all I'll just say that you're probably never going to have to prove this or even argue that it is a linear time algorithm just knowing it is enough but I'll quickly go over the general intuition of why it's the case first of all if we had to take every node and percolate it up or if we had to take every node and percolate it down which one would we rather do which one seems more efficient well if we're percolating down then only the root node actually has to go through the whole height of the tree and then these two have to go to the whole height minus one and then a bunch of nodes here go an even smaller distance and we get more and more nodes as we go down because remember this is a complete binary tree but if we're percolating up it's worse because now we have a bunch of nodes that have to go the whole height of the tree and then we have a smaller amount of nodes that have to go the whole height minus one so percolating down is going to be more efficient when we get to the root node we just have a single node here that doesn't have to be percolated up whereas if we percolate down we have a bunch of nodes that don't have to be percolated down so shifting these down is generally going to be more efficient if we have to do it for all the nodes now let's say n is the total number of nodes in the tree and let's say we in this case we actually had a full binary tree just to make the math a little bit more simple we know that roughly half of the nodes are going to be in the last level right that's kind of something we talked about earlier in the course right this is going to be one two four a each term is going to be roughly equal to all the previous terms combined let's say we have roughly n divided by two nodes in the last level now for each of these nodes how much are we going to have to percolate them down well remember the last level doesn't need to be percolated at all so we get a zero times n divided by two what about the next level well that's going to have half of the nodes that this level had so we can call that n divided by four how much are we going to have to percolate these down well one each so we're adding these two terms together zero times n divided by two and one times n divided by four and if we expand that we get a summation that looks like this now the number of terms that we're going to be adding together is going to be roughly equal to the height of the tree so so if you remember your math you know we'll get something like this but at this point you probably don't care and this would roughly evaluate to n so we know that the big O time complexity of this is indeed big O of n you won't have to memorize this don't worry and you most likely don't care about it either i just wanted to mention it for the sake of completeness but the important thing here is that just because we can be given some random n elements and then turn that into a heap doesn't mean we can actually sort all of them in O of n time because just because we have a heap if we wanted to turn that heap now into a sorted array we first built the heap in O of n time but then we'd have to pop every single element in the heap we know popping is still going to be a log n time operation if we have to do it for n elements then it'll take n log n so what i'm saying here is we can actually use heaps also to sort values and we can do that also in n log n time just like binary trees just like merge sort and the rest so this is yet another example of sorting so we talked about some of the advantages of heaps over binary search trees we can get the min and max in constant time we can heap a five we can build the heap in O of n time but the downside of heaps is that we can't just search for a random element and then do that in log n time like we can with bsts with a heap suppose we're looking for the value 30 we get to the root node we're at 14 it's not 30 well we know all values in the right subtree are greater than 14 and we know all values in the left subtree are greater than 14 so the 30 could be in both subtrees it could be here or it could be there we don't know where it is we haven't narrowed it down so to search for an element we'd have to go through every single node in the tree that would be an O of n time operation but with binary search trees it's log n so binary heaps are not good for searching but that's okay because they're not intended for that they're intended to get the priority element which is either the min or the max and the last thing i want to mention about heaps is that when it comes to coding interviews you actually have to use a heap more often than you have to use a binary search tree at least i'm talking about like a built-in data structure where your where the data structure is a part of the solution bst problems are also common but it's usually you're implementing a part of the bst you're searching for something you're calculating something but when it comes to problems where you actually have to use the data structure as like a utility data structure it's pretty rare that you end up actually needing binary search trees it's more often than you that you need a heap because it's more often that you need like a minimum or maximum value you need to continue doing that there are a ton of algorithms where heaps are really important so it's a very good data structure to understand you should at the very least understand that heapify runs in linear time and you can push and pop from the heap in log n time and you can get the min or the max depending on what type of heap you have in constant time those are all important to know even if you don't necessarily remember how to implement all of them so next let's move on to probably the most common data structure you're ever going to use whether we're talking about coding interviews or real coding at your job or projects or anything like that hash maps and hash sets are really really useful and to start with i'm going to be focusing on the application of these rather than the implementation because it's much more important to know how to use these than it is to actually implement them we already talked about sets and maps earlier specifically the ones that are implemented with binary search trees now i talked about how sets are just kind of a set of values like one two three whereas maps are a little bit more complicated that is kind of a set of keys which are then mapped to a different value we gave the example of like a phone book where some name is mapped to you know the phone number one two three something like that right so we're primarily going to be focusing on maps because they are generally more common and they're a little bit more complex but the main ideas behind a map are nearly exactly the same as a set instead of just having a set of keys we're going to have that set of keys except each key is going to be mapped to some separate value but the key is what's used to sort the binary search tree it's also what's used to access values from the hash set or the hash map first let's compare tree maps and hash maps though there are typically three main operations you want to do when you have a map you want to insert when it comes to tree maps the big oh time complexity is log in to insert into that tree that's definitely better than maintaining a sorted array because inserting into a sorted array in the worst case would be big O of N removing from the tree is the exact same it's also log N likewise with searching we essentially run binary search on the tree map and we can search for any value in log N time that's pretty good and there are other bonuses of tree maps because they're ordered we can iterate through it in sorted order if we have that tree map we can iterate through it in sorted order in O of N time so that's like our in order traversal just by having a tree map we are kind of maintaining that sorted order with a hash map though things get interesting inserting is actually a constant time operation removing is also a constant time operation and searching is also a constant time operation so you can already see why hash maps are probably the most useful data structures you're ever going to use they really just beat tree maps out of the water but there's a bit of a caveat here that this is actually not the worst case time complexity even though i'm writing it as big O which means worst case hash maps actually don't have this as the worst case time complexity for these three operations this is actually the average case time complexity but the vast majority of the time people still assume that it is the worst case time complexity so we write it as big O of one like if you're ever doing a coding interview it's safe to assume that these operations run in constant time that's what people assume in jobs and just in general i think if you ask them most people don't actually know that these operations are actually average case in the worst case inserting removing and searching actually could be O of N time depending on how you implement the hash map but that's not so important and we'll actually touch on that a little bit later now the downside of hash maps and there's always a downside when you have something this good it's that hash maps don't maintain any kind of ordering actually so if you wanted to iterate through all the keys of the hash map you could not do it in O of N time you'd basically have to take all of the keys and then sort them and then you know depending on what sorting algorithm you use you could use you know merge sort you could even use a binary tree sort that it would be N log N typically though so that's sort of the downside but you can see that the positives definitely outweigh the negatives especially if you don't need to traverse it in order and you just need to insert remove and search which is what we would probably do with a phone book then hash maps are very important so let's take a look at a common use case of hash maps let's say we were given a list of names maybe in the form of an array and we want to count for each name how many times does it show up in this array so how would we use a hash map to do that well the obvious way would be to map every single name so use that as the key and the value in this case will be an integer with the count of that name so initially our hash map is going to be empty we start at the first name it's Alice so we go ahead and add Alice to our hash map but before we would even do that what we could do is run search on our hash map we would check is Alice already in the hash map no it's not and remember search will run in constant time so it's not in the hash map so when we do insert it into the hash map we should put the value one because this is the first time we're seeing this name next we would go to the next position by the way for us to have done that for us to have gone through one position we did it in constant time if we were doing it with a tree map in the average case that would actually run in log n time I mean we know that inserting a node into an empty tree is probably going to be of one but in general it's going to be log n so now we're going to get to the second name Brad we're going to search for it in our hash map that search is going to be of one it doesn't exist so we're going to do the same thing with Brad we're going to add it as a key and the value initially is going to be one we're going to get to the third one we're going to get to the third name Colin do the exact same thing Colin is also now added to the hash map the value the count of it is one now we're going to get to our first duplicate Brad we've already seen Brad so when we search our hash map we're going to find that it already exists in the hash map and it's at this position so instead of assigning one here we don't know the count could be anything right now it's one it could have been two it could have been three it could be some value we know it's not going to be zero though so what we should do here is instead of assigning it to one we should add one to it which would put it to be two so we overwrite that value with a two by the way doing that iterating through this position was also a constant time operation and notice we don't have duplicates in this hash map I mean we could have added another entry for Brad and put one here but that isn't what we're trying to do for Brad we're trying to count how many times did it show up it doesn't make any sense to add a second entry and this brings us to a property of hash maps they cannot contain duplicates duplicates are not allowed in hash maps because it doesn't really make sense for us to do that that's not the use case for a hash map why would we want multiple copies of the same thing and that's the exact same with binary search trees remember we don't allow duplicates and binary search trees so a tree map is also not allowed to have duplicates so now let's go to the next position Dylan it doesn't exist in our hash map we figure that out by searching which is an o of one operation so we add Dylan to the hash map and the count is going to be initially assigned to one we get to the last person Kim and they also are not in the hash map we add Kim and then set the count to be one now for each position in the input array we basically did a few of one operation so that means to have gone through this entire array and built this data structure it would have been an o of n time algorithm now also the space complexity would also be o of n because in the worst case every single name could have been unique that would have led the size of our hash map to have been o of n but this is definitely better than using a tree map a tree map would have had the same amount of space roughly speaking it would have been o of n but the time complexity for each one of these insertions and searches would have been a log n operation and we know we have n values in the input so the overall time complexity would be n log n with a tree map if we were doing it but now we have a hash map hash maps are much more efficient by the way the code for this type of algorithm using a hash map would look something like this in python suppose we're given an input array names and you know the same exact names that we have listed up here we create our hash map this is how you do it in python it's a little bit different than most languages but in most languages you would declare like a hash map data structure with like a constructor or something like that we're calling it count map then we're going through every single name in our list of names and remember we have two cases if count map does not contain this name now in python the syntax for that is like this if name not in count map but most languages will have a count map data structure and that will have a method or function which is called let's say contains and then you'd pass in this key as the parameter to that method call but basically we're checking this name does not exist in this count map therefore we're going to assign that name to have an initial value of one the else would be that the name already exists in the count map therefore we would increment that count by one like we did for brad so it's a pretty straightforward algorithm it runs in linear time next let's talk about how we can actually go about implementing a data structure like this now let's talk about the implementation of a hash map now most likely you'll probably not be asked to actually implement a hash map in an interview it's pretty rare that you have to do that and the implementation of hash maps can get really really complicated we'll be talking about the general concepts and then we'll be coding up a relatively simple hash map but i think the concepts are what you should really focus on because the concept of hashing and the other ideas we're going to be talking about definitely come up in software in general so this is definitely not the last time you're going to be hearing about these ideas of hashing key value pairs and things like that first of all under the hood a hash map is actually implemented with an array so in this case we'll have some index and that index will be mapped to the key value pair and just because we have an empty hash map right now does not mean the size of our array is zero even an empty hash map is going to be non-zero in this case let's say we have an empty hash map but our array is of size two we have index zero and index one now the actual key value pair in this case suppose it's just null right some kind of default value it's empty we're basically indicating that we don't actually have anything stored here just yet now with an empty hash map the first thing we would probably want to do is start inserting some values but how does an insertion actually work in this case let's say we're calling it put it could be called insert or something like that in this case the key value is going to be a string and the value itself is also going to be a string that doesn't necessarily have to be the case you know this could be an integer or this could be an integer or they could be some other type it could actually even be an object but what's important here is that we have a way to convert the key we don't care so much about the value but the key should be able to be converted into an integer and how we're going to do that is called hashing we're going to have some kind of hashing function which is going to take the key value and then convert it into an integer and when we have that mapping you can see where i'm going we're going to use that integer as the index and that's how we're going to decide where to put that pair that key value pair into our array so in this case this array is actually an array of objects where the object itself is a pair a key value pair well the simplest thing would be able to map each character to some integer for example the first character a could be mapped to zero i think l is the 12th character so that could be mapped to the integer 11 and we could do that for every single character and then we would add them up and we would get some big integer let's just assume that the integer we get is a 25 i'm just making that up but the idea is that we converted each character to an integer then added them all up and we got another integer 25 now the only problem here is our array is only of size two so this is not really a valid index for our array how can we fix that well this is where a little bit of math is going to come in we can take any integer no matter how big it is as long as it's positive and we can take it and then mod it by the size of our array so in this case mod it by two if you're not familiar with modding we're basically dividing 25 by two and we're getting the remainder that's left over so in this case 24 divided by two would equal well we're the remainder of one because two can keep fitting into 25 until we get to 24 and then if we add a two we're going to get to 26 so that's too big with 24 we have a remainder of one left over now if we instead instead of 25 we actually had 24 and we were modding it by two then we would have a remainder of zero because two does fit into 24 perfectly 12 times and then we're left with a remainder of zero and those are really the only two possibilities but what's important to notice here is that when you mod by the length of the array no matter what integer you're modding you're always going to get a valid index as the output the result that we get would always be a valid index if we're modding by the size of the array which in this case is two it could have been three it could have been four but the mod is always going to result in a valid index and the reason behind that is pretty simple no matter what integer we're modding by it could have been five the result the remainder is always going to be less than five because the remainder always has to be less than five it always has to be less than the number we're modding by because if it wasn't then it wouldn't really make any sense right we can't say 25 modded by five is equal to five because we can still divide this by five and then get zero right so that's it's just a little bit of math but that's the main idea so we mod by the size of the array to get to convert any integer like 25 to a valid index so modding this by two in this case would lead to one so then we'd say alice is going to be inserted at index one so in this case alice is going to be at index one the key is going to be alice and the value is going to be the city that she lives in which let's say is new york city in this case now we're going to insert a couple more values but suppose we wanted to first get alice we could do that in o of one time we call get on alice we would using our exact same hashing function take alice convert it to an integer let's say again it's 25 mod that by two then we get one so in constant time we were able to get the index that alice is stored at then over here we could go to that index and then say okay what city does alice live in again well it's new york city so that's the idea and that's why it's so efficient now we're going to run into a few problems though let's say we now want to add brad to the hash map let's say we convert brad to some integer right taking the sum of the characters and by the way when we actually convert a character to an integer most likely we're going to be using the ascii representation of the character there are more complicated ones but if you're using a set of 128 characters so if we had a relatively small alphabet size we could do this basically it's a way of converting each character into a integer and in that case capital letters are actually different than lowercase letters like for example capital b could be evaluated to like 70 lowercase b could be something like 40 4 but that's not so important let's just assume that we have a way to convert each character to some integer but let's say we took brad and the integer that it turned out to be was 27 now we mod this by two we get one again so what are we going to do we're going to say okay at index one let's insert brad but alice is already at index one so we can't really do that without losing the information we've already stored this is a problem and this is the problem with pretty much all hashing it's something that you can't entirely avoid it's called a collision clearly it's bad to have collisions but there are ways that we can work around it we can minimize collisions and we can try to work around them but we can't entirely get rid of them that's really important to know hashing collisions pretty much always happen now first let's understand how we can try to minimize collisions there's sort of a problem here no matter what we convert brad into no matter what integer it gets converted to modding it by two is either going to lead to a zero or a one if our hash map is half full like one of the spots is already taken we basically have a 50 50 chance of having a collision or getting the position that's empty those aren't great odds so typically what happens with hash maps is we keep track of the size of the array and we keep track of how many keys are actually inserted into the array in this case the size of the array is two and we only have one key actually inserted in the array so we say that the hash map is half full and typically when it becomes half full is when we resize the array and resizing the array actually works pretty much exactly the same as when we did it with dynamic arrays meaning we take the size and roughly double it and we would have done that not at the time that we're inserting brad we would have done that as soon as we inserted alice we inserted alice and then we realized our hash map is half full so at that point we would have resized the array we would have doubled it roughly so the array would now have index two and index three so four elements now but ignoring brad for a few more seconds what if now we try to get alice well we convert alice to the integer 25 we mod it now instead of modding it by two we're actually going to mod by the size which is four and it turns out that the index is one again so we see that okay alice is still in the correct spot in this case it works out but it's not always going to work out for example what if instead of alice being a 25 was a 27 in that case when we mod it by two it would have gone at index one exactly where it's still at but then when we resize and we try to get alice again we try to search for it we mod this by four now because the size has increased and modding 27 by four leads us to three so we would say okay alice is probably at index three we would check and we'd see that no alice is not there what i'm saying here is when we resize the array we can't just leave the values where they previously were because the size changed therefore the index using our hashing function might have also changed so what we have to do when we resize we take every single key that's already in the hash map we recompute the hash of it using the new size and then move it to where it should now be for alice's case 25 modded by four is still one so it can stay where it is but if it wasn't we would have to move alice to the new position by the way we call this process of increasing the array size and then moving all the elements to their new position we call that rehashing the array and since we're doing it when the size is half full and we're doubling it every time it's still relatively efficient because it's going to be infrequent that we have to do this rehashing obviously it's pretty expensive because we're going to have to go through every key that's in our hash map but as long as we double it the same way that we did with a dynamic array it's going to be relatively efficient in the average case so now finally let's get back to brad instead of modding it by two now that our hash map is size four we're going to be modding this by four 27 modded by four is three so in this case we don't have a collision and it makes sense because our chances of a collision have definitely decreased we have a bunch more empty positions so brad is going to go over here and the city that brad lives in is chicago and since once again our hash map is half full we're going to again resize it so we would double the size so now it would be of size eight i'm not going to draw out the whole thing because it's not super important but let's just assume that the size of this has now become eight this will help us minimize the chance of a collision but we're going to insert one more person now callin let's assume that after hashing the name callin we get an integer value of 33 we mod that by the size of our array now which is eight we mod that by eight we get a remainder of one so even though we tried to minimize the chance of a collision which is good sometimes we still run into the case where we have a collision we are going to insert brad or callin at index one even though alice is already there and by the way when we resized this from four to eight we would have actually had to recompute the position for each of these and then potentially moved it to that position so for alice since i think alice was 25 that was the hash of alice and then we'd have to mod it by eight which in this case would have been one once again so alice actually would have stayed exactly where they are the hash of brad was 27 we would mod that by eight and that actually would have also been three exactly where it still is that's mainly just a coincidence to be honest i didn't even plan that but it's convenient for us because we don't have to redraw this now how would we actually handle this now i mean if we really wanted to we could resize the array and maybe that would decrease the chance of this being a collision but it still might end up being a collision so we need a different way of handling collisions and there are actually multiple ways of doing that one way of doing it is actually at every index instead of just storing a single pair we actually store a linked list of pairs so we could actually have multiple pairs occupying the same index now the downside of that approach is we have to kind of maintain that memory and the pointers and all that and when we actually run the get operation and we arrive at let's say index one we're looking for colon we would first see in the linked list we'd have to traverse through the entire linked list we'd first see alice is there that's not who we're looking for we'd go to the next position in our linked list and then we'd see oh colon is over here and then we'd return whatever value we're storing for colon which in this case is seattle but that's kind of the downside of and that linked list approach is commonly referred to as chaining there's another approach called open addressing and it's called that because we kind of loosely define the position that a key should go at like the index it should go at even though we computed the index one for colon we don't have to put it here we can say well this is already occupied let's try the next position so we take that index one and add one to it so we try index two is this empty in this case it is so we can go ahead and put colon over here and the city that they live in see for sure now in this case when we run get on colon we're looking for colon what city does colon live in we would compute the hash 33 mod by eight we would again get one we would see well this is not where colon is so if colon exists maybe they're at the next index maybe we open address this so let's try the next index we look at the key well this is the same key we were looking for colon so we found him and the city he lives in is seattle now possibly we weren't looking for calling we were looking for somebody else named dylan who actually does not exist in the hash map maybe we somehow computed the exact same index for dylan we would look at index one we'd see this is not dylan we would open address we would try the next available address is dylan over here no they're not we try the next available address is dylan over here nope is dylan over here nope and at this point we know we can stop we don't have to search through the entire index first of all that wouldn't be efficient that would be o of n and we definitely don't want to do that but we know that if dylan did exist the hash of dylan would be at one but this was occupied so we would have put dylan over here but dylan was not over there so then we would have tried the next position dylan would have been inserted over here but he's not there and then we would have tried the next position over here but this is empty so if dylan existed he would have been here but he's not therefore dylan does not exist in our hash map this will make a little more sense if i explain how we would insert dylan so let's say instead of getting dylan we're inserting dylan let's say hashing dylan we got the index one then we tried to insert dylan over here well this is occupied so now we try the next available index this is occupied next available this is occupied next available well we're going to insert dylan over here and whatever city that they happen to live at so this is a sort of naive way of doing open addressing because we're just trying the next available position every single time the downside of this approach is we're going to cluster the hash map potentially if we have a really big hash map and we get a lot of collisions all the keys are going to be stored close to each other there are better ways of doing this open addressing instead of just computing the plus one maybe we take that value and square it and do other things with it but the important thing to focus on here is that we have collisions and we have ways of handling those collisions and there are you know more optimal ways of handling that and you could spend a lot of time learning about that it's pretty math heavy to be honest so we won't go too in depth into it and you likely won't need that kind of knowledge for coding interviews but it's important to know that there are ways of handling things like this now the last thing i want to mention before we actually take a look at a simple code implementation of a hash map is that when we maintain the size of the array it's more optimal for the size to actually be a prime number for math reasons that ends up resulting in less collisions for the hash map so typically the size of the array is going to be a prime number so instead of this being eight it would actually be better for the size to be seven and then instead of actually doubling this to be 14 because 14 is not a prime number we would actually you know just try to find the next available prime number let's say it's 17 in this case and we would roughly double this but roughly double it to a number that is prime so maybe the next one would be something like 37 if that's prime i'm not even a hundred percent sure but that's the main idea now this is kind of complicated to implement this in code so i won't be doing that and it's very rare you'd actually be asked to implement a hash map like this i mean if you're asked to implement a hash map and you have to do it so perfectly for the size of it is prime and you're doing all these kind of crazy optimizations that would be a very very long interview question and it's very unlikely you'll be asked that even if you are asked to implement a hash map it's probably okay to do it a very simple way that's why i'm going to be showing you the simple way to do it right now so first let's look at how we would kind of initialize our hash map like i said we're actually going to be storing pairs in this array this is one way to implement that we have like a class and that class will store two values the key and the value of that pair you know in our case we were doing strings but these could be any kind of type as long as you have a way of hashing the key and this implementation will mostly focus on if we had strings as keys and strings as values so initializing our hash map this is python but of course you could implement this with any language the logic will be pretty similar we're going to initialize the size of the hash map the size is the actual number of keys in our hash map initially that's going to be set to zero we're also going to initialize the capacity i'm arbitrarily setting this to two but it could be any number optimally it should be a prime number but in this case it's two just like we kind of started with in the example and then our map itself remember it's maintained as an array and in this case there's only two values remember and to indicate that it's empty i'm initializing the two values as null if they were non-empty we would have some pair for those values the next really important thing for a hash map is to have some hashing function given some key we should be able to convert it into an integer that fits within the boundaries of our array in this case it's size two so it should fit in our array of size two assuming the key is a string we go through every single character in the key and we convert that character to some integer this in python will convert it into the ascii value of the character but that's not super important as long as we have a way of converting the character to some integer we're going to take that integer and just sum all of them up so initially our index is going to be zero we're just going to keep adding that integer to our index we could have some really big integer it could be out of bounds of our capacity so what we're going to do before we return is mod it by the capacity so if our index ended up being something like 10 we would mod it by our capacity which is two we would get zero if our index is actually not out of bounds for example maybe it's one we would mod that by two and we would still end up getting one which is still in bounds anyway so if it's in bounds that's okay if it goes out of bounds then we'll mod it to bring it within bounds so by the time we return the integer for this hashing it will be some index that is in bounds of our array now let's move on so first let's look at searching for a key aka the get operation so given some key we want to return the value of that key if it exists if it doesn't exist we can return null or we could throw an exception or we could do something but the details aren't super important we care mostly about the logic so first we're going to convert that key into an index using the hashing function we talked about a second ago and then we're going to loop this implementation by the way is assuming we're doing open addressing where if we find a collision we're just going to try the next index so given that index first we're going to check is it non-null suppose we're searching for alice and we get an index of one we would look here it's non-null so then we would check is the key of what we're storing here of that pair equal to the key that we're searching for in this case it's alice what we can do is just return that value we found what we're looking for but maybe we're actually looking for somebody named colon in that case we would have not found what we're looking for this is not colon so instead we would have not returned we would have incremented our index right try the next index and here the reason why we're modding by the capacity is assume that actually this part of our array didn't exist we're looking for colon we took one and incremented it by one well that took us out of bounds to bring us back in bounds we can mod the index by the capacity just like we were doing earlier that would bring us up to index zero now we're still looking for colon we execute the loop but at this point we see that there's null here this is empty that means if colon existed in the hash map he would have been here but he's not therefore we know he doesn't exist and our loop stops we can return null or we can throw an exception we can somehow indicate that the key colon does not exist in the hash map now let's insert into the hash map a.k.a put we pass in some key and some value we want to insert that into the hash map the idea is similar we convert the key to some index and then we start looping we're looping wild true because at any point that one of these executes we're going to return immediately anyway so this is just kind of a convenient way that I like to write it so there's two possibilities one that this key does not exist in the hash map let's say we're trying to insert colon the index we computed was one our loop would execute like this first we would check is this index empty it's not empty if it was then we would insert colon over here but it's not then we execute the else if case else if the key of this is already equal to colon in that case we would just overwrite it but this is not colon this is alice so then neither of these execute we just increment the index by one and modding it to make sure it stays in bounds so then we would try this index and we would go back to our loop we would see that this index is actually empty so what we can do is create a new pair for colon and whatever value colon has assign it to this index increment the size by one and this is important remember if the size is greater than or equal to the capacity we are going to call our rehash function which i'm going to show you in just a second and after we do that then we can go ahead and return now assuming we were inserting alice and we wanted to change her city from new york city to something else then the else case would have executed we would have found alice is already here we would just simply overwrite the value we don't have to increment the size by one because we're not adding anything we're just overwriting the value and then we could return immediately so lastly let's look at the rehash function it doesn't really take any parameters because we already have all the member variables of the hash map we know we're going to double the capacity at least that's the naive way to do it more optimally we could find the next prime number that's roughly double so we're going to declare a temporary variable for our new map it's going to be an empty array so far but we want it to be of the size of the capacity that we're trying to do which is roughly double the previous capacity so we could do a loop for that we could just append null to it to indicate that there aren't any actual pairs in this just yet and then we're going to take our current map our current member map and assign it to a temporary variable old map then we're going to take our new map and then assign it to the member variable so now our new map is the map that we're maintaining but all we have to do now is take the values from the old map and then put them in the new map so as we iterate through every pair in the old map if that pair is non-null we're just going to run the insert function or the put function that we talked about earlier putting the key of this pair with the value of this pair the reason we reset the size to be zero is because we know internally this put function is going to be incrementing the size by one each time anyway so that will give us the correct size so that's why we reset this to one here so these are the main ideas i wanted to talk about you don't have to focus so much on memorizing every detail just understanding the main concepts behind collisions rehashing increasing the size to minimize collisions having some kind of intelligent hashing function where we also minimize collisions having the size be prime also helps to minimize collisions these are the important concepts to understand when it comes to hash maps and even more important than that is just understanding how to use hash maps and hash sets which we talked about earlier we didn't talk too much about the details behind why inserting removing and searching runs in o of one time on average the analysis could get complicated and i don't think it's super important to understand it's pretty safe to assume that those operations run in o of one time that's what most people do and to be honest most people don't even understand what we've discussed so far so if you understand even half of this you're far ahead of most people next let's talk about graphs which are a really common topic when it comes to real coding interviews and they're actually pretty challenging there's a lot to cover here but the good news is that we've actually already been talking about graphs since pretty much the beginning of the course linked lists are actually a form of graphs there are a subset of graphs and another subset that we talked about are actually trees whether it's binary trees or other kinds of trees a graph is essentially made up of nodes like we have over here and possibly some pointers connecting them together we've been calling these nodes throughout the course but another way of referring to them is as vertices so it's kind of a synonym vertices is essentially the same thing as a node typically and when we talked about pointers connecting nodes together another word for that is edges so suppose we had a graph that looks like this i mean this is sort of shaped like a tree right this node could have some kind of child maybe you know it has another pointer that's pointing to null in this case it doesn't what i'm getting at here is that we could have graphs of all kinds of shapes when we talked about binary trees and binary search trees we mentioned that they never have cycles but what if i take an edge from c and connect it to a here you can see we have a cycle going from a to b to c and then back to a so when it comes to regular graphs to some generic graph that we have there are no restrictions we could have any number of nodes and any kinds of edges connecting them together in any way now technically there are some restrictions and that is that e is going to be less than or equal to v square now this is math so maybe it's a little bit scary at first but v just refers to the number of vertices that we have a k a nodes in this case you can see we have three nodes so let's write that down three squared is of course equal to nine so we're saying that the number of edges is going to be less than or equal to nine but why is that the case here well what we're saying is from every single node a k a vertex vertex is basically the singular for vertices from every single vertex we could have a pointer going to every other vertex so a pointer a k a an edge going here to one node and then going to the second node and actually we can have an edge going in on itself so a node can be pointing to itself so we really don't have any restrictions here so for every single node we could have v edges where v is the total number of nodes so you can see that's how we're getting v squared from to actually draw it out let's now go to b b could have a pointer going to a it could have a pointer going to c it could have a pointer coming onto itself same thing would see it could have an edge going to a it could have an edge going to b and it could have an edge coming into itself so each node has three edges going out of it so we get three times three edges right this is the maximum number of edges we could have i mean technically you could have duplicate edges but usually we don't consider that when it comes to graphs so you're pretty safe to assume that we never really have duplicate edges one thing you might have noticed here is that we have a pointer from a going to b we also have a pointer from b going to a so that means we can go between a and b you know back and forth and you know you could also say that there's a cycle formed between these nodes and you know there's many other cycles throughout this graph that i'm sure you can find another thing to mention about this graph is notice how every single pointer aka an edge has a direction this is referred to as a directed graph a directed graph means that the pointers the edges have a direction so you know maybe we don't actually have pointers going both ways so an example would be from b and c from b we can go to c but from c we can't necessarily go to a that probably makes sense to you because we've already seen instances of directed graphs trees are directed graphs linked lists are directed graphs but what does an undirected graph look like well when it comes to actually drawing them they can be drawn um you know many ways like you can just have a pointer that looks like this this indicates that this edge is undirected meaning you can go in either direction you can go from b to a or a to b another way of drawing that and i think it's more common is just to draw like this without any direction so if we had an undirected graph that looks like this that would essentially mean that every single one of these edges you can go in either direction and that would be true for every single edge that we add to the graph in case we had more nodes or something like that so this is a bit of background and this graph that we've been looking at is a very generic form of graph it's most common to represent a graph like this using adjacency lists which we'll talk about in a bit but first we're going to start with matrices or matrix if you're just talking about a singular matrix and we're going to go through all three of these because these are three very common ways of representing graphs and to be honest this second one adjacency matrix is much less common the most common ways especially when it comes to coding interviews is a matrix or an adjacency list so those are the two that we're really going to be focusing on throughout this section so let's start with a matrix we haven't really talked about this much throughout this course and you might already be familiar with what a matrix is but in case you're not i'll go over it briefly it's essentially a two-dimensional array but it can be used to represent a graph which is what we're going to do in this case but like i said it's a two-dimensional array so in a language like python it would look kind of like this you have one array this is the first row then you have the second array which is the second row and we keep going like that so in this case you can see we have four rows and four columns sometimes people use x and y to you know refer to the coordinates which in my opinion can get confusing because because in math x is actually commonly used to refer to a row and y is used to refer to a column which is something you might not be used to especially you know when you think about the x y coordinate system right when it comes to algebra or something like that so this can get confusing that's why i very much prefer to think of it in terms of rows and columns so i use r and c to do that and i would recommend that you do the same thing whenever i've conducted an interview i've seen so many candidates get messed up when they're using x and y to implement their coordinates so moving on how would you access some arbitrary coordinate like for example this one well remember that everything is indexed by zero so this is the zeroth row this is the first row this is the second row this is the third row this is the zeroth column this is the first second third column so if we want to access this point we'd go to row equals one and column equals two so with this coordinate system we would say grid at index row equals one so this will give us the first row remember this represents a array so this is not an accord this is not a coordinate this is a array before we had grid which is a two-dimensional array we've accessed index one this gives us a one-dimensional array so now within this one-dimensional array we can access a value like you normally would with a one-dimensional array we want to access the value at index two aka column two so we would get this and this is equal to zero right we're not assigning it to zero i'm saying here that this is already equal to zero this is the value that would be a returned when we do this so that's a bit of the basics now let's talk about how this is commonly used to represent a graph you might have a scenario like this in this case you can see this matrix is populated with zeros and ones let's say that zero represents a free space meaning you know this is a space that we're allowed to be located at any zero is something we can if we're creating a path somewhere throughout this matrix we can move along the zeros we can move there we can go here we can you know go there and there and maybe here and then down here right we can go through all these positions we can't access any of the ones because they're blocked we say right this is just how i've defined it and this can be a common way when it comes to coding interviews to define things so how exactly does this represent a graph well you might have already noticed typically when it comes to two-dimensional grids you're allowed to move left right up or down so you're allowed to move in four directions you might be able to move diagonally but it's typically less common so again how does this represent a graph well you could say that we have a bunch of nodes let's say that in this case the free spaces are nodes so just to draw a circle you know basically everywhere we have a node it would look something like this and of course the ones are going to be blocked out now here we have nodes but where exactly are the edges well remember i said we can move left right up and down so this is what the edges would look like in this case let me ask you are the edges directed or are they undirected well since we can move left right up and down typically they're going to be undirected from here we can move to the left from here we can move to the right so these edges are undirected but what about you know over here well we can move up i said but there's nothing above here so you know this is essentially you could say a null pointer but in reality this matrix does not have pointers at all these edges are implicit these nodes are also implicit these edges exist because of the rules that i defined i said we can move left right up and down maybe i could have defined you know us being able to move diagonally two spaces that's pretty uncommon i've never seen that happen before but we could define it that way so this is a really really common way of representing graphs when it comes to coding interviews and for now we're just going over how this is represented later on we'll actually talk about how common algorithms can be implemented using this there can be a lot of edge cases as you might have noticed so next let's talk about what an adjacency matrix is and these like i said are much less common than regular matrices and adjacency lists and we'll talk about why so we're going to use pretty much the same matrix we had before just for simplicity but that does not mean that these are nodes themselves when it comes to an adjacency matrix the dimensions represent the nodes so typically it's a square matrix let's say in this case the size is v times v where v represents the number of vertices so that that's of course why it has to be square because it's going to be you know this is going to represent the vertices and this is also going to represent the vertices we can't have you know a fourth column here because then we have to have a fourth row but if this represents the zeroth vertex and this also represents the zeroth vertex then what does the value here actually mean well typically it's going to be a zero or a one a zero in this position for example means that there does not exist an edge going from zero to one a one in this position means that there is an edge going from one to zero a little bit more formally if we have let's say our adjacency matrix which is this aka this represented in code and we have some arbitrary index here i earlier mentioned that we're using row and column but that's usually for actual matrices when it comes to a adjacency matrix we know that the index represents a vertex itself so in our example let's say we're talking about the first vertex that's what v one is and the second one where we're talking about the zeroth vertex so this means an edge exists from the first vertex to the second so in this case this is a directed edge if the value is one that means that we have an edge if the value is zero that means an edge does not exist from v one to v two but what if we wanted to go the other way what if instead we want to know if there exists an edge from zero to one well we just swap the order of these two more formally we would look if there is an edge from v two to v one the order that you index it represents the order that we're checking we know where an edge exists what direction the edge is going if v one is first then we're checking v one to v two if v two is first then we're checking v two to v one so just to draw out how this would look if we drew it as like nodes and edges let's just go through every single one well first let's actually draw each vertex we have a zero we have a one we have a two and we have a three remember the vertices are from you know the dimensions so let's just go through every single one so from one to zero we have an edge that means from one to zero we draw an edge going like that of course we don't have an edge going from zero to one how do i know that well let's look at our grid from zero to one we don't have a one here so there's no edge going here we have an edge going from one to one what does that mean there's a self loop so there's an edge going in on itself so notice how an adjacency matrix can basically represent the same information for an entire graph right we can have self loops we can have you know from each node we can have edges going to every other node so what's the maximum number of edges we could have with an adjacency matrix well if this is v the number of edges is going to be equal to v squared so that's consistent with what we talked about earlier running through the last couple edges we have to going from two to three so that would look like this and we could have going from three to a one which is over here so we have the three going to the one over here so why is it rare to use an adjacency matrix well take a look at how much space we used here no matter how many edges we actually have to represent a graph we're using an entire matrix that means the space complexity here is going to be v squared where v is the number of nodes or vertices that we have in our graph we could represent the exact same information like look at this graph here it's not a lot of information we have four nodes and how many edges do we have we literally have four edges so we could reduce the space complexity to v plus v right the number of nodes plus the number of edges which in this case is also equal to the number of nodes so you know in terms of big O that would be big O of v we could represent it this way so why would we use a matrix which takes up a bunch of extra space and doesn't provide you know a ton of information anyway well that's what leads us to our next way of representing graphs which is adjacency list that is essentially what we have drawn over here let's talk about it in more detail so now let's take a look at adjacency lists and these are typically the most common way of representing graphs especially when it comes to coding interviews I mean using a matrix can also be pretty common though so I think these two are good approaches to get familiar with so it's very similar to linked lists and trees that we talked about so we'll have something like a graph node let's say or you know you could just call it a regular node or vertex or whatever you want to call it but the important thing is that there's really two things when it comes to nodes right we know a node could have some type of value whether it's an integer or a character or a string or maybe the value itself is some object like it represents a person right or a city for example right and you want to know how are these cities connected together or something like that or if it represents a person maybe you want to know how are these people connected like maybe it could be a social network maybe person one follows person zero but person zero doesn't follow anybody because there's no edges going out from person zero that's just one example now what exactly would a self-loop mean in that context well it's hard to say that's why maybe we don't allow self-loops and that type of graph who knows but graphs are obviously very important now when it came to linked lists we could have either had a next pointer or a previous pointer when it came to binary search trees we could have a left or a right pointer but with generic graphs we could have any number of pointers so how do we represent it well here you can see in python we use let's call it neighbors or you know you could say following if you're in the context of like a social network but neighbors is a pretty generic thing to use and instead of just having one or two or three or five or you know pre-defining the number of pointers we could have we use a list now in python this isn't clear but what type is this list aka this array going to be it's going to be an array of neighbors aka neighbor graph nodes so how would we represent this graph when it comes to graph nodes well graph node zero would have a value of one and its neighbors would be empty because it doesn't you know have any nodes going out of it so neighbors in this case means what edges is node zero pointing to there aren't any edges for node one we would have neighbors of you know this graph node so a pointer to this graph node would be in the neighbors of node one and the graph node itself would actually be its own neighbor would graph node three be in its list of neighbors no because in this case we're using neighbors to refer to which nodes is this node pointing at it's not pointing at graph node three graph node three is pointing at it so if we were looking at graph node three it would of course have a value of three that's not so important what would its neighbors be its only neighbor would be node one that's the only node that it's pointing at so would have a single neighbor it would be a pointer to this graph node lastly two would have a value of two let's say its neighbors would be just three so in the list of its neighbors it would have a single pointer to graph node three this is obviously a bit more space sufficient than the adjacency matrix that we looked at because we only contain pointers for nodes that actually exist we're not declaring two pointers for every single graph node or three or five we're just declaring an array and it could be empty or it could have some pointers now what if we had undirected edges like maybe you know the way we've drawn this is wrong let's suppose that this actually doesn't exist for simplicity but let's say we had three edges that look like this right there they don't have arrows on them so they're undirected well that would just mean that for the neighbors of zero it would have one in its neighbors for the neighbors of one it would have zero in its neighbors it would also have three in its neighbors for three it would have one in its neighbors and it would have two in its neighbors and for two it would have three in its neighbors we when we have undirected edges we're basically assuming that there is you know a pointer going both ways something like this so that's the basics of the different ways to represent graphs now let's look at some really common algorithms when it comes to matrices and then later we'll talk about adjacency lists so now let's cover an example problem that you might see for a matrix and surprise surprise the algorithm we're going to use is DFS I told you it's one of the most common algorithms and that's because it's very very frequently applied to graphs so in this example we have pretty much the same matrix we looked at earlier we want to count the unique paths starting from the top left and going to the bottom right in this case of course the path can only move along zeros not on any ones and also for a single path we can't visit the same cell more than once why is that important well take a look at this we can go along these zeros and then we know we go down here and then left here and then we could pretty much be in an infinite loop over here among these four we could basically you know keep going in a circle and however many times we want to and then we could move down and then get to our destination the bottom right so in that case what would be the answer to this question well it would basically be infinity and that's kind of boring so we don't want to for any single path like suppose we go here and then we go down and then we go to the left now we can't move to this cell because we've already visited it and we can't move to this cell because we've already visited so the only option we have here is moving to the left we can't do that it's blocked so we can only go down now here of course we can visit a couple cells that we haven't visited before we can't go to the right it's blocked off but at this point you probably get the idea so when we want to count the paths we want to go through every single possibility so an algorithm like dfs is going to be helpful for us this also might remind you of backtracking which is what we talked earlier and that's because it pretty much is this is an example of backtracking there's a big overlap when it comes to dfs and backtracking they're both recursive and they're both very very similar in nature so this dfs is definitely going to be more complicated than when we looked at binary trees so i'm going to just show you the code immediately and we're going to see how in general the algorithm will run visually and then compare that to what the code would do and by the way yes again this is going to be a recursive algorithm with the recursive case and of course a couple base cases in this case we don't just have one base case we actually have two now the simplest way to think about this is not to immediately look at the code but to think about it visually it's all a matter of choices we start at the top left like that's always where we're going to start so in terms of the parameters that we're given we're going to be given the grid of course that's our two-dimensional matrix here we're going to be given what's our starting position in this case it's going to be zero zero so we can have kind of the dimensions written out so we're starting at the top left and what are our choices we'll remember we can move in all four directions we can move up we can move left we can move down and we can move right and we know that's going to be kind of annoying because we can potentially move out of bounds that's the first thing that we have to worry about so that's what the first base case is going to be first of all here you can see i'm getting the dimensions of the grid this is how you would do it in python so the length of the grid which is going to be this is going to give us the number of rows that we have the length of one of these rows you can see i'm just taking the first row because we know every single row is going to have the same length because this is a rectangle i think it's safe to assume that most of the time and the length of one of those rows is going to be the number of columns in this case we have a simple case because we have a square matrix so it's four by four but that might not necessarily be the case now in my case i'm you know calculating this every time we call the function that's pretty unnecessary to do we could pass in those parameters to the function but i prefer to do it this way because it gets kind of annoying when you have to pass in six parameters into a function but it doesn't change the time complexity so this isn't such a big deal the important thing is we have the dimensions of the matrix now one case is that our row remember this is the row goes out of bounds it's too small or our column goes out of bounds so what we could check is our row less than zero or is our column less than zero or you could simplify that into a single case because the minimum of these if the minimum is less than zero that's all we care about we just care about if one of these is too small so we can just take the minimum of the row in the column and check is it less than zero that means either this is too small or this is too small it doesn't matter because we're out of bounds either way what would we do if that was the case well if we end up going out of bounds that clearly means that we did not find a path at least down this recursive you know chain this path we did not find a path to the destination so in that case we would return true this dfs is supposed to count the number of paths you can see that there's a few more cases where we would return zero i'll get to those in a minute especially as we run through the example but to briefly cover them now another case of course for our row and column instead of being too small they could be too big our row could be equal to the number of rows why are we checking if it's equal to the number of rows instead of greater well remember the number of rows is going to be four not three we have four rows the last index is three but the number of rows is four so if row ever goes out of bounds if it ever equals four then we also return zero or if our column goes out of bounds it reaches four then we also return zero right we did not find a path we went out of bounds why can't we take the max of the row and the column and check if it's greater well because remember the number of rows and columns might not necessarily be equal in this case since they're equal we could take the max of the row in the column but maybe if we had four columns we would not be able to do that we know we go out of bounds this way or this way if we're less than zero because that's always going to be the starting point but the ending point could be different that's another case where we would return zero and another case would be this is the slightly more simple one is if we reach a blocked position like from here right starting at the top left we go down well we reached a blocked position we're not even supposed to be here so we basically stop searching we're not going to continue our recursive case because we're not allowed to even visit this position so we're going to stop immediately and we're also going to return zero basically we're saying by visiting this position there are no valid paths that reach the destination so again we return zero now the other case is if we reach a position that we've already visited before and what is this visit actually going to be well it's going to be a hash set data structure so that's what we're going to end up passing in it's not super clear in python because we don't have static typing but this visit is going to be a hash set and it's going to tell us if we visited a position before along a given path so that would be the example where we go here then we go down then we go left and then maybe we go back up to the same position at this point if we visited the same position twice we would stop we'd say nope if we visit this position twice there are no valid paths that reach the destination we're not allowed to do this so we return zero the other base case is of course we you know end up somehow reaching the bottom right we reach the destination how do we know we reached the destination well it's defined as the last row and the last column so if r is equal to the last row which is row minus one and our column is equal to our columns minus one then we return one that means we found a single path this is that particular path for instance right this is one path that could be counted as part of the solution now let's actually run through this example and see how the code would actually execute so when we actually call this function our dfs we're going to pass in the grid of course we're going to pass in zero as the starting row and zero as the starting column and we're going to pass in some hash set and that hash set is going to be reused throughout this recursive function what that means is we're not creating a new hash set every time we make a recursive call we're passing in a reference to that exact same object every recursive call is going to have access to that exact same object so starting at the top left we're going to you know run through our base cases have we gone out of bounds no we haven't gone out of bounds have we already visited this position nope is this position blocked nope let's assume by the way there's always going to be at least one valid path in this matrix but if you're not sure of that in a real interview it's worth asking that as a clarifying question to your interviewer next let's check maybe we've already reached the destination no we haven't we can't return so at this point what we're going to do is add this coordinate to our visit hash set the reason i'm using a hash set in this case is because it's just easier in terms of code to just add a pair of values to check if we've done this before and we know adding and removing from a hash set is going to be a constant time operation but alternatively you could use a two-dimensional grid like visually what i'm going to do is basically just mark the positions that we've already visited with a blue circle so if we wanted to know if any of these positions is visited we could use a hash set or we could use a two-dimensional grid of the same size as the grid to represent that information if you're allowed to modify the grid you could also as you visit a position mark it as a one to indicate that it's already been visited because then logically we will basically assume that we can't visit that position but it's not always safe to assume that you can modify the input grid so we're going to ignore that for now so now that we've added this to our visit hash set it's time to do the recursive case we're going to set our count equal to zero or basically saying that from this position we want to count how many ways we can reach the result and we're allowed to move in four directions so we can move down that's going to be row plus one we can move up that's going to be row minus one we can move to the right that's going to be column plus one and we can move to the left that's going to be column minus one now when we go up we're going to go out of bounds our row is going to be less than zero so we're going to end up returning zero okay what about when our column goes to the left we're going to end up returning zero what about when we go down well in that case we're going to visit a blocked position so in that case we're going to return zero again because it's blocked so the only valid position we can go to is to the right over here and when we do that we're not out of bounds we haven't already visited this and it's not blocked it's also not the destination so we can't return one but we are going to add it to our visit hash set so so far we visited these two positions now that we've gotten an idea of how the base cases work i'm going to start running through them a little bit quicker so from this position now this second position that we're at we're going to have another count variable we're counting how many ways from this position can we reach the destination and when we find that result we're going to return that to the previous position that we were at which was the starting position and then we're going to have our answer basically these two are going to have the same count now from here we're allowed to go in four directions we can go up can't do that we can go to the left that is valid but it's already been visited we know that because it's blue here but we know in code we would add it to our visit hash set so it's already been visited we can't do that so we can go down well we can't do that either it's already blocked so we can't visit this position so we can only move to the right and then from here this is valid neither of the base cases are going to execute now from here we're also going to have a cost which is initially going to be zero but when we calculate it we're going to end up returning that cost to the previous node which is going to end up returning its cost to the previous position but from here we can go in four directions we can go up it's out of bounds we can go to the left it's a position we've already visited but we have two valid positions now that we can go to we can go to the right or we can go down now since this is a dfs depth first search it's recursive we're not going to go along these two paths simultaneously we're only going to do one at a time we're going to go as deep as we can in one of them and then we're going to go backwards we're going to backtrack that's why this is a backtracking algorithm and then we're going to go back to where we were and then we're going to go along the other path so in terms of code which one of these would execute first while it looks like row plus one which is this one would be first so let's just go along that so but this is going to be added to the visit hash set and then from here neither of the base case is going to execute this is going to be added to visit and now we have four choices we can go up can't do that's already been visited can't go left it's blocked we can go to the right here and we can go down here which one of them is going to execute first well as we saw before down is going to execute first but just to actually quickly run through the other case what would happen if we went here well then we don't have many choices we can't go to the left we can't go to the right we can't go down we can go up here right and then when we go up here we'd be stuck we can't go to the left we can't go up we can't go down we can't go below because it's already been visited so this path essentially what i'm saying is would not lead us to a solution so let's keep that in mind but going down here it's also not a base case we have some choices can't go up can't go to the right but we can go left and we can go down what's going to happen by the way if we went left well here we wouldn't have many choices we could only go to the left one more time and here we can only go down and here we have zero choices we haven't reached the destination and we can't move anywhere else we can't visit the same positions we've already visited so we'd be trapped and along this path we would end up returning the base case zero okay so the question remains from here can we even reach the result at all can't go to the right well we can go down so from here the only valid choice as you can see is moving to the right recursively and at this point we would finally execute the base case where we have reached the destination and then we would return one so from here this cell we would have a cost of zero we would execute four dfs's in all four directions three of them would return zero this one would return zero this one would return zero and this one would return zero but the one here the one where the column is incremented by one would return one and at this point we would end up returning one to the previous node but before we return one to the previous node you can see we're backtracking first we marked this position as visited and now we're going to mark it as unvisited you're going to see why we're doing that in just a second so from here now we're going to backtrack we're going to mark this as unvisited and go to this node from here we know that that there was only one path here that led us to the solution so from here the count would also be one and we would return one to the previous node and before we do that we'd mark this as unvisited so then we're going to go back to this node we know from here only one of the paths reached the destination so from here we would return one to this node now this node if you recall had two choices we could either go down which we just talked about right now or we could go to the right now from here we're going to go to the right we're going to execute the second valid case but now as you can see all of these are marked as unvisited why is that allowed i thought we could only visit the same position once well that's only true along a single path what i'm getting at here is we could from here have two paths we could you know do something like this that reaches the destination but we could also have a path like this that reaches the destination these are two different paths so they are allowed to visit the same position right both of the paths visit this position as you can see and this position and this position and even the result i mean of course they have to both reach the result we said only a single path can't visit the same position twice but multiple paths can reach the same position in fact they have to if they want to both reach the result so i hope that makes sense it can be a point of confusion but as you can see from here uh you know we don't have many choices we can go down and then we can go to the left and then we can go down and then from here how we're going to end up trying this path it's not going to reach the result and we're also going to try this path where we go down and then to the right and again we are going to reach the result but this is a slightly different path this is a slightly longer path but it's still valid so what we would realize then is backtracking all the way back is from here we can reach the result in one way from here we can also reach the result in one way so what that means is from here we can reach the result in two ways and what about from here well from here we're going to end up returning the count back to this so we're going to say that from here we can also reach the result in two ways and we're going to return that to the previous, which is here, and we're going to say we can reach the result from the starting position, we can reach the destination in two ways. And that's going to be the final value that we return. So when we call our DFS with these parameters and then print the result to is going to be the value that we print, you can try it in any of the code languages that we provide. So now finally, when it comes to analyzing the time complexity of a solution like this, it can get pretty complicated. So I like to think about it in a simple way, but it's not super precise.  We know from the starting position, let's suppose that the worst case is where there's all zeros. We don't have any blocked paths. So in that case, the length of a path could be the size of the matrix, right? Any given path could be the size of the matrix. So thinking about it in terms of a decision tree, we have from any position, we have four choices. And for each of those positions, we have four more choices. And by four choices, I mean we can go left, right, up or down. Now, of course, we know some of them are going to execute the base case where we either go out of bounds or maybe we visit the same position twice or we visit a blocked position. But like I said, this is an imprecise way, but it still gives us an idea of the upper bound for every node. We're going to have four choices and the height of this tree is going to be the size of the matrix because we know the longest path, which is what this tree represents. This tree represents a given path. Like if you follow a path in this tree, it represents a path in the matrix. So the height of the tree is going to be the number of rows times the number of columns. Now, if you recall from our binary tree analysis, this is going to be basically the number of branches, which in this case is four raised to the power of the height of the tree, which is R times C.  So you could say that the time complexity of this is going to be four to the power of N times M. That's the big O time complexity. So this is not very efficient, but that's expected when it comes to brute force DFS backtracking. Now, the memory complexity would essentially be the recursive call stack. That means when we started this position, then we make a recursive call here, then a recursive call here, here, and you know, do that for pretty much the entire size of the matrix. At most there could be that many recursive calls outstanding at the same time. So we say that the memory complexity is going to be N times M. We could also say this is the memory complexity from our visit hash set, because that is also going to be the size of the grid. Or instead of having a hash set, you could just create a grid itself to keep track of visited positions. So that's the idea here. I know it's pretty complicated. It's not the type of thing you'll completely understand the first time you see it. It can take a while to wrap your head around a lot of the concepts that we talked about here. But DFS, especially on a matrix comes up quite often. Check out the practice section for graphs if you want to find some practice problems that you can try out. So next let's talk about the BFS algorithm run on a matrix. And as you can see, I'm going to be jumping into the code relatively quickly because we actually have even more code than when we were talking about DFS. But the good thing is, at least in my opinion, that this is more simple to understand visually than DFS. If you recall BFS, at least when we ran it on a tree was, you know, something like this where instead of, you know, starting out the root and then going as deep as we can and then going as deep as we can on the other side. What we did is we went layer by layer, we went through the first layer, then we went through the second layer, and then we went through the third layer, etc, etc. And that's the same idea here. We're going to go through the first layer and then the second layer, and then the third layer, and then the fourth layer, and then the fifth layer, etc, etc. Now what type of question would this algorithm apply to? well, by far the most common is the shortest path algorithm. Suppose we want to find the length of the shortest path from the top left to the bottom right and then return that the best way to do that. The most efficient way is the BFS algorithm. We could also use DFS if we really wanted to the algorithm that we just talked about. We could use DFS. We could go. We could basically check every single possible path that can reach the destination and then find the length of the shortest one of those, but that's a brute force approach. BFS is actually more efficient. The time complexity of this is actually just going to be the size of the grid. Let's say that's n times M where, you know, this is the number of rows. This is the number of columns. This is what the time complexity is going to be. Whereas DFS was much, much less efficient was four to the power of n times M. So let's see how we can run this algorithm in terms of code and why it's so efficient. So the setup is going to be taking the dimensions of the grid. In this case, we're just past a grid. Let's say we already know that the starting point is the top left and we're going to the bottom right. We're going to have a visit hash set just like with DFS. So there are some similarities. We're going to have a queue just like for BFS when we ran it on a tree. The queue is basically going to tell us the current level that we're at. So initially the queue is just going to be initialized with the first node. That's our starting point. And we're also going to add it to the visit hash set. It's already visited. And now from here, we want to see this is basically all the nodes we can reach with a length of zero. So this is, you know, our starting point, essentially, then we're essentially going to loop while the queue is non empty. And we're going to take a snapshot of the length of the queue. Initially, it's just going to be one, just a single element. And we're going to pop all one elements just like with a tree. But when we pop, we know we're not getting a node. We're actually adding the coordinates of the position. And when we pop, we're getting the coordinates of the position. Now we might have found the result. What if we were at the destination? In that case, we would return the length of the path. Initially, like I said, our length is zero. But in this case, we know we haven't reached the result. So one way to code this up. And basically this is going to look complicated. It's a lot of boilerplate. But once you get used to it, it's pretty easy. It's just a pain to type out in my opinion, because we have a lot of conditionals. We know we can move in four directions, just like we did in the DFS approach. And we know there's a bunch of edge cases, we could go out of bounds, we could reach a position that's blocked, we could reach a position we've already visited before. Those are a few edge cases, and we're handling them the exact same way we did with DFS, where if the minimum of the row and the column is less than zero, we're out of bounds. If the row is equal to the number of rows, we're out of bounds that way. If the column is equal to the number of columns, we're out of bounds that way. We've might have already visited before, or it could be the value one. That means it's blocked. What we would do in that ca