[Solution]Problem 30: Find Distance to nearest Exit[Google]
Shortest Distance, Graph Traversal, Path Finding
Get hyped my amazing coders,
Let’s get into the solution for a very interesting question. Google questions can be tricky because Google loves asking questions that have an element of misdirection. They seem like they would be doable one way, but the optimal solution is something else. This is especially true for their coding challenges. When I was invited to solve Google’s notorious Foobar challenge, I noticed that all the questions had blobs of text that could make figuring out what to do much harder.
To learn more about my experiences with the challenge, and how I solved it, make sure you tune in for this week’s Storytime Saturday. We’re keeping this Week Google-themed. Now let’s proceed through to the solution.
Problem
This problem was asked by Google.
You are given a m x n 2D grid initialized with these three possible values:
-1 - A wall or an obstacle.
0 - A gate.
INF - Infinity means an empty room.
Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, it should be filled with INF.
For example, given the 2D grid:
INF -1 0 INF
INF INF INF -1
INF -1 INF -1
0 -1 INF INF
After running your function, the 2D grid should be:
3 -1 0 1
2 2 1 -1
1 -1 2 -1
0 -1 3 4
[FREE SUBS]To buy the solution for this problem, use any of the following links. The price is 3 USD. Once you send the payment, message me on IG, LinkedIn, Twitter, or Email:
Venmo: https://account.venmo.com/u/FNU-Devansh
Paypal: paypal.me/ISeeThings
Step 1: Birds Eye View
One of the standard openers on this newsletter, we start this question by taking a step back. Let’s look at what we’ve been given and figure out some simple details. The first detail that we can hash out is the concept of distance. How are we defining it? Since we have been given a grid, it might be tempting to take the Euclidean Distance between these points. This temptation will be even stronger if, like me, you work in AI/Machine Learning and calculate distance in the context Vector Spaces.
Luckily for us, they give us a sample input. Let’s bring it back here so we won’t have to scroll up.
INF -1 0 INF
INF INF INF -1
INF -1 INF -1
0 -1 INF INF
with the required output:
3 -1 0 1
2 2 1 -1
1 -1 2 -1
0 -1 3 4
Notice there is a gate at [0][2]. The location at [1][1] is said to be 2 units away. This does not align with the Euclidean Distance. Instead, the distance calculation we are using here is closer to the Manhattan Distance.
Let’s take a look at what we have been given. We have a grid, and we want to calculate the distance of every point on that grid to the closest gate (assuming it is reachable). In other words, this distance is the primary relationship between two points (location and the gate). Now is there a relational data structure that we can use to encode such relations?
Enter the Graph
Most resources online tend to focus on what Graphs are. They typically tell you that Graphs are defined by a set of vertices and a set of edges connecting the vertices. This is true, but not very useful if you want to use it. Here is a better way to think about Graphs: Graphs are data structures that represent relationships between objects.
Let’s take a look at an example, specific to this question. Here we have different locations (of walls, gates, and rooms). And we want the distance between these various locations. Here the location (given by index on the grid) becomes our node, and the manhattan distance between locations becomes our edges. Since we only care about distances from rooms to nearest gates, we will only create those edges. Take a second to pause, and make sure our rationale for using a graph and method for building one makes sense.
I have no doubt that my more advanced subs (especially those that are currently working with me), had identified this as a graph problem. And I could have directly said use a graph here, which is what coding blogs/tutorials/videos and even premium services do. However, that would not be useful to anybody. Graphs are a beautiful and elegant data structure, and I want you to be able to use them to their full extent. There is a reason companies like Spotify, Netflix, and YouTube all use Graphs heavily (I will cover it soon. To not miss it, make sure you are following me on LinkedIn and Medium). They are unfortunately not taught properly, so people miss out on their complete awesomeness. I will make sure that this doesn’t happen to the readers of my content.
Let’s get back to the question on hand. We have now identified that this problem can be solved with graphs, and how we should set up our graphs. Now the next step is how do we traverse this graph to calculate the distances. There is always DFS (Depth-First Search) and BFS (Breadth-First Search). We could get fancy with A*, Djikstra, or Bellman-Ford. How can we pick the best traversal algorithm for our question?
If this is something that confuses you, make sure you check in for Math Mondays. Next Monday, I will cover the important path-finding algorithms in detail. For now, I will just use the spark notes version.
Step 2: Picking the best graph traversal algorithm
It can be a little overwhelming to find the best algorithm in graph traversal. There are very subtle nuances b/w them which make choosing hard. Let’s go over it here.
The first thing that we can notice is that this graph is not weighted. The distance between points (0,0) and (1,0) will always be equal to the distance between (2,3) and (2,4). This goes back to the Manhattan distance. This means that we can use a simple algorithm like BFS over the more complex path-finding algorithms (which shine in graphs with unequal weights). To understand take a simple example.
Imagine you were developing a running path creator. If you were running on identical terrain throughout, you would only care about the distance b/w two points. 1KM traveled on any path would take identical amounts of energy. However, now imagine your terrains could change (swamps, mud, water, slopes etc). Running 1KM on a plain would be very different than 1KM through a swamp.
For the first kind of AI, a BFS would be great. For the second, more comprehensive planner, we want to use a better and more comprehensive pathfinding algorithm, that can account for differing weights. That should make it clear why we are using a BFS for this particular problem.
You might be wondering I haven’t mentioned DFS yet. If you look online, lots of people try to solve this problem with a DFS. However, DFS is not a good pathfinding algorithm. This is because with DFS if the algorithm goes down the wrong path, it will waste a lot of time before returning. And if it does go down a path that is non-optimal, it will simply return that path. So trying DFS in a path-finding context is not a smart idea. Unlike BFS, DFS is not guaranteed to return the optimal path (and in some cases, might never terminate). This is Djikstras, A*, and other pathfinders are based on BFS. This is why we will use BFS to solve this problem.
However, there is a twist. And that twist is why this problem is so brilliant (and the reason I selected it for this week). Using this simple twist, we will be able to solve this question in a really neat and efficient way. Let’s discuss what it is.
Keep reading with a 7-day free trial
Subscribe to Technology Made Simple to keep reading this post and get 7 days of free access to the full post archives.