Using Breadth-First Search for LeetCode ProblemsAlgorithms in SwiftSteven CurtisBlockedUnblockFollowFollowingJun 16BFS for this is 10 5 20 3 15Before We StartWhy?Breadth-first search for trees may seem easy, but they can be expanded for use in simple matrices which is often used for LeetCode challenges rated as medium or above.
PrerequisitesTo follow along with this piece, you should be able to create a binary tree using insertions (although a simple implementation is shown below).
Keywords and TerminologyTree: A data structure with a root value and left and right subtreesMatrix: A grid to store dataCell: One of the elements of a matrixThe Tree VersionTraversing the tree above involves passing through the three levels in turn.
The order of the nodes within the level does not matter and the nodes are presented left-to-right, although any order would be acceptable.
Level 0: 10Level 1: 5, 20Level 2: 3,15A sample implementation (and test) is in the Gist here:The implementation here revolves around creating a queue that is appended to if there is a left or a right subtree.
It is trivial to convert this into path length.
The Matrix VersionLeetCode 1091.
Finding the shortest path in Binary Matrix requires us to work out the shortest path (from the top right-hand corner to the lower right-hand corner) of a matrix (represented by [[Int]] in Swift).
Cells in the grid can either be available (0) or blocked (1).
We could conceivably choose a depth-first search, but that would involve going through all of the possibilities first and picking the shortest one.
The added complexity from the matrix version includes the following:There are eight directions that can be traveled in the matrix, and we need to make sure that we do not cross over the bounds of the gridWe need to confirm if each cell is possible to visit (has been blocked (1), or marked as visited (also 1)We will know if we have reached the goal (the bottom-right cell) by comparing the cell with the size of the grid (headCoordinate.
0 == grd.
count — 1 && headCoordinate.
1 == grd.
count — 1)Since each cell can have up to eight paths from it, we need to make sure that for each iteration we pull up each path from the current cell — and perhaps this is the most complicated part of the full implementationSimplifying the CodeBy separating out the possible directions from the rest of the code we can split this out into a variable:let dir:[[Int]] = [[0,1],[0,-1],[1,0],[-1,0],[1,-1],[-1,1],[-1,-1],[1,1]]So we can calculate the candidate next coordinate by adding these to the current coordinate.
One way of doing this is:let nextCoordinate = (currentCoordinate.
0 + direction[0], currentCoordinate.
1 + direction[1])The AlgorithmSo the basic idea goes like this:We set the initial cell as the start (top-left hand corner; 0,0)Set the path count to be 1.
We take the elements in the queue, and for each current cell:Check if we can traverse to the cell (check it is 0), if not move to the next elementCheck we are at the destination.
If we are, return the path countMark the current cell as 1Then for each possible direction, calculate the nextCoordinate.
If it is within the bounds add to the queueThe current iteration is complete, increment the path count4.
After we have completed all of the possible cells, there is no solution so we return -1ConclusionI hope you enjoyed this tutorial.
You can find the code and repo below.
Thanks for reading!The code snippet:The repo:stevencurtis/BFSForLeetCodeAccompanies Medium post Swift: Using BFS for LeetCode problems – stevencurtis/BFSForLeetCodegithub.
comWant to get in contact?.Get in touch on Twitter:Steven Curtis (@stevenpcurtis) | TwitterThe latest Tweets from Steven Curtis (@stevenpcurtis).
Studying for a Masters in Computing while developing iOS Apps…twitter.
com.