Ep.1: Depth-First Search - LeetCode Problems That Got Me Hired

i'm hoping that this isn't going to be your typical elite code tutorial type video i think that there's already a ton of great resources out there for learning data structures and for understanding the solutions to specific lead code problems i thought about making something along those lines but i wasn't confident that i'd be able to create something unique or better instead i wanted to try to take a step back and see if i could teach people how to see the bigger picture when they're doing leak code problems there is a finite set of data structures and algorithms that coding interviews tend to be about and i wanted to go through each of those categories to highlight a few problems i've done that i think are particularly worth doing because they illustrate a concept very well i want to really emphasize the big takeaway from each of these problems and show how they connect to other problems and how these concepts can appear all over the place i've said before that studying leap code is about exposing yourself to different types of problems and understanding how different solution patterns can reappear i'm hoping that by categorizing and sharing my favorite problems these solution patterns will become a lot more obvious to you to prepare for this i looked through my list of every single lead code question i've ever done and tried to one categorize them by problem type and two pick the ones that seem to be the most useful and applicable this proved to take a lot longer than i expected because rather than just explaining one problem well i had to go through and remind myself what each problem was about solve a bunch of them and then pick the ones that felt the most representative of that problem type if people end up liking this type of video then i'll definitely make a series out of this because i came up with 10 to 15 different categories of problems that i would love to talk about today i'm going to talk about what i think is the most important pattern to learn well because it shows up everywhere that first search on my facebook full-time interview out of the six problems that i had to do i would say that 50 of them essentially boiled down to that first search which sounds absurd but you'll see why in a second if you're watching this video i'm going to assume that you already know what a depth first search is at least in its most basic form maybe you've taken a data structures class so you learned that that first search is a way to search through all the nodes of some graph the bridge version is that a graph has many paths through its nodes and a depth first search searches all the way down one path before coming back to search the other paths you also probably saw a very specific implementation of that first search in your class but today i want to talk about how this pattern can be generalized and applied to so many different problem types right so at the start of each of these videos i'm going to show you a list of all the problems that i'm going to be talking about just in case you want to try them before i spoil them for you i'm not going to go into the full solution of each of them in this video because i want to talk about the key takeaways so if you want to try it out on your own before watching the rest of this video i highly encourage that alternatively you could do them in the order i present one at a time and after you finish one of them come back and watch my commentary on it before trying the next one i won't mind i'll be here go ahead try them out all right i'm just going to start now letter combinations of a phone number is a great problem to start with and i think it showcases one of the big use cases of dfs very well so in this problem we're given a phone number that's represented as a string containing the digits two through nine each of these digits is associated with a set of letters and our job is to take the entire phone number and to write out all the different possible letter combinations that it could represent so in this case 2 could be a b or c and since it's followed by a 3 we can form combinations like a d b d c d a e a f and etc and our job is to return a list containing all these different possible letter combinations if you've never seen this type of problem before you might be thinking how can i use dfs on this if it's not a graph if you're newer to this type of problem then here's the biggest takeaway that i can offer a lot of times the graph that you're doing a search through is not an explicit graph but rather it's the solution space really try to internalize this and you'll see that it pops up everywhere let's draw out a way to solve this problem and you'll see what i mean you'll probably want to start with the first digit and write out all the possible letters that it could represent then for each of those you want to write out all the possible letters that the next digit can represent like so you continue this until you've considered all the digits in your input and you need to remember that each one of these paths is a possible combination that we want in our solution set if we start with an empty string and build them up from there like building a d or a f we find that our solution space kind of looks like a tree so we want whatever search algorithm we write to be able to get to all of these endpoints at the bottom in implementing dfs remember that you can do it both recursively and iteratively i personally prefer doing it recursively most of the time because you don't need to define an explicit stack or data structure instead you can just use the recursion call stack for the purposes of today's examples i'll be showing all of them with recursive implementations if we think about this recursively all we're doing is that each point or node of the graph we want to send little search parties down all the possible paths it can take from there then we just keep doing that and in this way we eventually get to search all the paths and build all the solutions in this solution space so i'm not going to go line by line through the code if you want to do that i've commented my code so you can pause the video and try to understand it instead i want to go over my big takeaways and highlight some key tips the biggest thing you should take away from this problem is the structure of the code and i'll try to generalize it for you because this exact pattern comes up again and again and again at the top you need to create something that will hold your solution as you're working towards it in this case we have an empty list that's going to contain each of the letter combinations we've finished building then you need to initialize your depth first search in our case we'll be starting with an empty string because we haven't seen any of the digits yet and as we build our letter combinations we'll be storing them into string builder your dfs may need to take in a lot of inputs it needs to know exactly where it is which is what this index is for it needs to know how to look up relevant information which is what this map is for and in this case it actually needs to build the solution as it searches and store them in the solution set which is what this result array list is doing in the depth first search function there's two big parts and they both just follow standard recursion rules first you need to know when to stop searching in this case when we've built a string that's as long as the input we know we're done and we can add it to the solution one tip is that you might also need to check for duplicates or wrong answers but those don't exist in this particular problem because we know all paths are valid the other part of the depth first search is to define which path you'll explore from here and this is what's going to vary the most from problem to problem in this case we need to try all the possible letters that are represented by the current digit we need to consider the string a which is what we're doing here and send a search party down that way which is what this recursive call of dfs is doing that way we can find all the combinations that start with a now here's a little tricky bit which you should make note of we actually need to remove a from our string builder so that we can add b to it and search down that path otherwise if we don't remove a we're actually going to be looking for all the strings that start with a b which is wrong this is a pretty common pattern when you're setting up your dfs routes and it's the same idea behind backtracking first you make a change then you recurse down that path and then you undo your change so you can check the other paths this problem is a great example of how to use dfs to build all the possible solutions that exist in a solution space and there's a bunch of other problems that are super similar to this with slight variations i think that the problem generate parentheses is a great example to try it looks cosmetically different but it's actually implemented in almost the exact same way the only difference is that in your solution space you're going to find certain paths that might be invalid so you have to make sure you don't search down those paths other problems like permutations combination sum subsets are all just variations of this exact format so i encourage you to take a look at them and see where the similarities are so the next problem i want to talk about is number of islands which encompasses a pretty large group of dfs problems that involve searching through a matrix if you've ever played the game minesweeper this is sort of the same idea so in this problem you're given a 2d array of ones and zeroes where ones represent land and zero represents water if two ones are next to each other they're part of the same landmass or island and you want to figure out how many such islands exist in this map essentially you want to see which ones are connected to each other the solution is essentially to iterate through the grid and every time we see a one we look at all the ones connected to it sync all of them or flip them to zero and add one to our score because we just found one island so each time we see a one we flip it to zero and check if there's any ones neighboring it and that's an island now this sink method essentially becomes our dfs function the idea is that when we're on a one we flip it to a zero and then we need to send search parties into four directions around it to see if there's any ones there obviously if there's no ones we don't have to do anything but if we find another one we have to go to that spot and send out more search parties from there just to see if there's any ones connected to it so in this way we end up finding all the ones that are connected to one specific one and if we sync all of them that is equal to one island which goes towards our final score by flipping them from ones to zeros we're essentially ensuring that we don't accidentally double count an island and this essentially is dfs in a matrix right so the solution code for this problem looks cluttered but most of it is just setup and matrix logic the big takeaway is that it's the same thing as the previous example but i do want to give some tips that are specific to matrix problems just as before we set up our solution variable which is this integer count but this time instead of storing all the different solution paths we'll just keep count of how many islands we've come across this logic basically says that any time we see a 1 anywhere in our matrix we run our dfs to get rid of all the connected ones or sync them and after we do that we can increment count by one because we've just encountered a single island so a key thing to keep in mind when you implement the depth-first search for a matrix is that you need to make sure you terminate when you run out of bounds in this case you can also terminate when you hit a zero or if the current grid spot is not a one because once you've hit something that's not land you don't need to search that way anymore this is analogous to the previous problem where we stop our search once the string we've built hits a certain length you'll also need to write logic to check the neighbors of a spot which you can do by adding and subtracting one from the i and j coordinates this checks the four neighbors of a current spot this is also analogous to the previous problem where the paths we're searching are the different letters that we could add at any point in time one tip that comes up a lot with this type of problem is that it's crucial you know which spots you've seen already in this case when we've seen a 1 we flip it to 0 and that's that if you don't do that before you extend your search as so then you could run into an infinite loop sometimes you might need to flip a spot you've seen back to its original value after you're done searching and sometimes you might be better off creating a separate matrix of booleans to keep track of what you've seen already in general i would be careful about this especially in matrix dfs problems so there's a handful of problems that follow this general idea in number of enclaves and surrounded regions you're looking for the amount of land from which you cannot walk off the border of the matrix which is a very similar idea to what we did in number of islands word search and smallest rectangle enclosing black pixels are two other examples of problems that involve dfs and a matrix although they have slightly different conditions for when you should stop and start searching i encourage you to check those out and understand them because this type of problem comes up a lot disguised as different applications now really quickly i want to talk about a third problem and queens this is sort of like the daddy of this type of problem but if you really break it down you'll see that a lot of what makes it difficult is just fluff if you understand this problem pattern well then you should have no problem with it given a square chessboard with end by end spots you need to find out all the ways that you can put queens on this board so that they don't attack each other in chess queens can move vertically diagonally or horizontally this would be a valid example as none of the queens are in each other's way but if this queen was say here then these two queens would be in conflict with each other and this would not be a valid board it seems overwhelming but the best place to start is to draw an example you'll probably have to go row by row to place one queen at a time so in the first row we could consider four different cases where we put the queen in any one of four spots then from each of those cases we branch out into other possibilities for the second row so if we consider this branch where in the first row we've put the queen in the first position in the second row we have limited options we could either put it in the third or the fourth position then we keep branching out from those examples in some cases we might encounter a branch where we've hit a point where the queen can't go anywhere it can't go in either of these spots so in that case we can't search down that branch anymore and we have to go back up and try a different path eventually if we find a branch where we've managed to fill up all the rows like so then we found a valid example and we can add that to our solution set so i'm going to highlight a few things in the solution code namely what parts of this problem are fluff and what the core bits of logic are you'll see that once you cut past the fluff the underlying code is no different than the previous two examples and for today's purposes i'm going to use this solution i found in leeco discuss by pirate utopia because i think they wrote it just as well if not better than i could have so just as before we need to set up something to hold our eventual solutions in the format of a chessboard in this scenario is a little odd they want the solution board to be outputted as a list of strings where each row is a string it'll be a lot easier for our sake to represent the board as a matrix of characters so we can easily put queens where needed the idea is that later once we've built a valid board we'll have some function to convert it into this list of strings format and store it in our results list this is the exact same as the string builder pattern that we used in letter combinations of a phone number all the construct function does later down here is that when a solution is found we'll convert this character matrix into the list of strings format so it's not really that profound i would consider this problem specific once you've set that up you can start the depth first search in this case we're going to go column by column at the start we haven't put any queens in any column so we need to start with column one this is what's going to help us keep track of where in the depth first search we are now the dfs logic is actually pretty simple in our given column we could put the queen in any row as long as it doesn't get in the way of other queens on the board which is what this logic here is handling we check each of the rows and consider whether that row is a possible spot that we could put the queen in in this specific column what this validate function is doing is that it's just going through the whole board to see if any queens lie on the same diagonal or horizontal as the spot that you're about to put the queen in and if there is a conflict then we don't try to put a queen there again i think this specific helper function is obviously important for this problem but it's a bit like fluff once we decide whether we can put a queen on a spot just like before we add a queen to that spot we dfs down that path to see if it leads to anything and then we get rid of the queen at that spot so we can try what would happen if we put the queen in other rows in that column this is the exact same idea as in letter combinations of a phone number so our terminating condition up here is if we've reached the end of the board this can only happen if all the queens that were placed past validate so if a board reaches the end we know that it's a valid board and we can add it to our solutions list obviously this problem is beefy and thinking through all of this on an actual interview could be tough but i'm convinced that if you know the dfs pattern well and you're able to recognize that the solution space for this problem is no different from that of other bfs problems then you'll have a much easier time understanding how to implement it valid sudoku is another great lead code problem to practice with if you want more practice with this type of weird backtracking dfs problem so now to talk about some of my more general thoughts on this topic i think the beauty of dfs is that it's so versatile and has so many applications we just looked at examples where we built strings using dfs and searched through a matrix i want to talk very briefly about how you'll encounter more dfs applications when you deal with problems that involve trees graphs or even dynamic programming i do plan on making other videos to address these topics specifically in the future since i think there's a bit more to them than just knowing how to search through them so i'll keep it short for today key thing to remember with dfs is that no matter how the problem is represented all you really need is a way to get from one state to the next in letter combinations of a phone number we got from one state to the next by adding a character to the stream that we were building in our matrix problem we got from one state to the next by moving up down left or right from our current location in tree problems we have a physical tree that we're searching through so when we're trying to decide how to figure out the next path to take or how to get from our current state to the next state we don't need to do anything fancy we can simply call the recursive function on the left and right children of the current node the big difference in many tree problems is that in addition to exploring all the paths you'll often have to return results back up your recursion calls and make sense of them that i think is the key insight to keep in mind when you're dealing with trees and i'll talk more about this later graphs are pretty similar but the way to move through your path or your states is to use an adjacency list or a matrix so that you can look up the neighbors of a particular node once you have that figured out you'll realize that the rest is the same thing you just call dfs to search all of the node's neighbors and then you keep calling dfs to search those neighbors neighbors i think that graph problems in general take a bit more setup than other types of problems so they might seem intimidating but i'll really go into detail and break these down for you later so you'll see that there's nothing really to be afraid of and that they're quite straightforward when you understand how the setup works now dynamic programming is the most interesting i think that dp problems are one of the most dreaded problem types but when you really get down to it recursive implementations of dp problems are essentially just depth first search with memoization i find it easiest to treat dp problems as a regular recursive dfs problem first once you figure out how to define the problem recursively then you simply figure out how to add memorization to save time the main idea in dp is that you'll notice you're constantly trying to recalculate the same thing and explore the same paths the dp solution is to simply save what you've seen already so that you don't have to recompute it you can just look up what you already discovered the fibonacci problem is your classic example of this but there's approximately a bajillion videos out there talking about this problem so i'm not going to go over it right now i will make a separate video in the future that talks about key dp problems and what you should take away from each of them anyways if you've made it this far i hope that this video was helpful and that you have an appreciation for the various ways that dfs can disguise itself and how important it is to learn dfs well because it shows up so much as you can see from today's video dfs problems follow a very similar structure and the problems that i talked about today are the ones that i find myself always thinking back to when i'm trying to figure out how to solve new dfs problems i am working full time now but i'm going to try to push the rest of these videos out in a consistent manner without compromising on the quality that i put into them and i have a lot of videos in this series planned so let me know if this is something that you find useful and i'll make sure to keep them coming all i ask is that if you did find this useful think about who else might benefit from watching this and try to help them out as well a lot of times the dash for jobs in cs can feel very cut through but i know that there were a lot of people on my journey who helped me out and i encourage you guys to all help each other out and do the same other than that i'd love to hear what you guys think and make sure to subscribe so you see when the next one comes out so on that note thanks for watching and see you guys soon

Channel: Kenny Talks Code

Views: 58,818

Rating: 4.9846678 out of 5

Keywords: coding, algorithms, data structures, technical interview, coding interview, nick white, algorithm, data structure, programming, software engineering, google interview, software engineer, back to back swe, depth first search, dfs, n-queens, number of islands, letter combinations of a phone number, leetcode problems, leetcode solution, internship interview, best leetcode problems, essential algorithms, cracking the coding interview, how to study for a coding interview, hackerrank

Id: nNGSZdx6F3M

Length: 20min 17sec (1217 seconds)

Published: Fri Sep 11 2020