Summary

The web content describes a challenging Google coding interview problem involving finding the shortest path in a grid with the ability to eliminate up to 'k' obstacles.

Abstract

The problem presented is known as "Shortest path in a grid with elimination," a frequent question in Google's interview process. The goal is to navigate from the top-left corner to the bottom-right corner of an m x n grid, which contains empty cells and obstacles. Each move can be up, down, left, or right to an adjacent empty cell, and up to 'k' obstacles can be removed to facilitate the shortest path. The solution involves a breadth-first search (BFS) algorithm that tracks the number of steps, current position, and the remaining number of obstacles that can be removed. The BFS requires careful management of the queue and visited states to ensure that each cell is considered along with the different ways it can be reached, taking into account the obstacles that can be removed. The article provides a detailed explanation of the necessary logic for the BFS, including what the queue should store, what constitutes a visited state, and the exit condition for the search. It concludes with a code snippet and a discussion of the algorithm's time and space complexity.

Opinions

The author suggests that a breadth-first search is an appropriate approach for solving this problem due to its nature of finding the shortest path.
It is emphasized that tracking the number of obstacles that can still be removed (num_available) is crucial for the algorithm's logic.
The article highlights the importance of a comprehensive "visited" set that includes not just the position but also the number of remaining obstacles that can be removed, to accurately represent the state of the grid exploration.
The author provides an edge case consideration, mentioning the need to return a valid value when the grid consists of only one cell.
The article concludes with an invitation for readers to follow the author for more content on Medium and to reach out with requests for future articles.

Google Coding Interview Problem (Hard Difficulty!): Shortest Path in Grid with Elimination

This problem is called “Shortest path in a grid with elimination” and is one of the most frequently asked Google interview questions.

The problem is:

You are given an m x n integer matrix grid where each cell is either 0 (empty) or 1 (obstacle). You can move up, down, left, or right from and to an empty cell in one step.

Return the minimum number of steps to walk from the upper left corner (0, 0) to the lower right corner (m — 1, n — 1) given that you can eliminate at most k obstacles. If it is not possible to find such a path return -1.

Let’s walk through an example.

Example 1. From https://leetcode.com/problems/shortest-path-in-a-grid-with-obstacles-elimination/

The input and output are defined as:

Input: grid = [[0,0,0],[1,1,0],[0,0,0],[0,1,1],[0,0,0]], k = 1
Output: 6

So one valid path is to go across the top row, then all the way down, which takes 6 steps.

The one removal we’re allowed we’ll use on the obstacle in the cell right above the bottom rightmost cell. Alternatively, we could go straight down from the initial cell to the bottom leftmost cell, then all the way to the right.

Intuition

At first glance, this problem feels like a typical graph traversal problem. Since we want to find the minimum distance to get from the top left cell to the bottom right cell, a breadth-first search feels appropriate.

In a breadth-first search, we need the following key bits of logic:

What information should our queue store? How do we determine what our addition to the queue should be?
What information should we store in our “visited” set?
What’s our exit condition?

What should our queue store?

So we definitely need to know the number of steps we’re on while traversing the grid, because the number of steps at our “goal” cell is what we’ll return as our answer. We’ll also need to know our current position.

The key distinction here is we need to track the *number of obstacles we can still remove* (let’s call this num_available ).

So our queue will store:

current row
current column
number of obstacles we can still remove (num_available)
number of steps used to get to the current position.

For each position, we can go above, below, left or right. If we encounter a path without an obstacle, we can simply enqueue the new position without changing the number of obstacles we can still remove; we’ll just increment our current path count by one.

However, if we hit an obstacle, we’ll have to see that we still have an available number of obstacles to remove (num_available ). If not, we can’t enqueue that position.

What should our “visited” states be?

The other tricky part about this problem is what we need to store in our visited set. Normally, we’d just store visited positions (pairs of rows and column coordinates). However, note that we can also reach multiple cells in different ways, with different values for num_available ! So, our visited set needs to store both the visited positions and the number available at that position, i.e. (curr_row, curr_col, num_available ).

What’s our exit condition?

Because we’re doing a breadth-first search, we know that once we encounter the exit cell (lower-rightmost cell), we should just return the number of steps to get there.

Code

With that, the rest of the solution looks like a typical grid traversal problem. Note the edge case to return 1 if we only have one cell (we assume it’s a valid value).

Let’s say the number of rows is r and the number of columns is c and the number of obstacles we can remove is k.

Runtime: O(r*c*k). Worst case we need to put every position in the queue k times.

Space complexity: O(r*c*k). Worst case we put every position in the visited set k times.

Let me know if anything’s unclear and thanks for reading!

For more articles like this, follow me on Medium. Not a member yet? Join the community. Want more software engineering interview guides and coding question tips? Check out all of my writing organized by topic in this article.

If you have any requests for what I should write, please let me know!