1293. Shortest Path in a Grid with Obstacles Elimination

You are given an $m \times n$ integer matrix grid where each cell is either $0$ (empty) or $1$ (obstacle). In one step, you can move up, down, left, or right to an empty cell.

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 no such walks exist, return $-1$.

Example 1:

Input: grid = [[0,0,0],[1,1,0],[0,0,0],[0,1,1],[0,0,0]], k = 1
Output: 6
Explanation:
The shortest path without eliminating any obstacle is 10.
The shortest path with one obstacle elimination at position (3,2) is 6. Such path is (0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2) -> (3,2) -> (4,2).

Example 2:

Input: grid = [[0,1,1],[1,1,1],[1,0,0]], k = 1
Output: -1
Explanation: We need to eliminate at least two obstacles to find such a walk.

Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 40
• 1 <= k <= m * n
• grid[i][j] is either 0 or 1.
• grid[0][0] == grid[m - 1][n - 1] == 0

Brute Force

First, we might think to try all possible eliminations of at most $k$ obstacles.

Then, on every possible elimination, we can run a BFS/flood fill algorithm on the new grid to find the length of the shortest path. Our final answer will be the minimum of all of these lengths.

However, this is way too inefficient and complicated.

Full Solution

Instead of thinking of first removing obstacles and then finding the shortest path, we can find the shortest path and remove obstacles along the way when necessary.

To accomplish this, we'll introduce an additional state by adding a counter for the number of obstacles we removed so far in our path. For any path, we can extend that path by moving up, left, down, or right. If the new cell we move into is blocked, we will remove that obstacle and add $1$ to our counter. However, since we can remove no more than $K$ obstacles, we can't let our counter exceed $K$.

Example

Let's look at our destination options if we started in the cell grid[2][1] with the obstacle counter at $0$.

We can also make the observation that each position/state (row, column, obstacle counter) can act as a node in a graph and each destination option can act as a directed edge in a graph.

In this specific example with the node (2,1,0), we have $4$ directed edges with the destinations being (1,1,1), (2,2,0), (3,1,1), and (2,0,0).

Since each edge has length $1$, we can run a BFS/flood fill algorithm on the graph to find the answer. Using BFS to find the shortest path will work in this case as the graph is unweighted. While running the algorithm, we'll look for the first instance we traverse through a node $u$ which is located in the bottom right corner (i.e. row = m - 1 and column = n - 1). Since BFS/flood fill traverses through nodes in non-decreasing order by the distance from the start node (0,0,0), our answer will be the distance from the start node (0,0,0) to node $u$. This is always true no matter what the obstacle counter is for that node (assuming it doesn't exceed $k$). If no such node is traversed, then our answer is $-1$.

Essentially, we'll create a graph with nodes having $3$ states (row, column, obstacle counter) and run a BFS/flood fill on it to find the minimum distance between the start and end nodes.

Time Complexity

Let's think of how different nodes exist in our graph. There are $O(MN)$ cells in total, and in each cell, our current counter of obstacles ranges from $0$ to $K$, inclusive. This gives us $O(K)$ options for our obstacle counter, yielding $O(MNK)$ nodes. From each node, we have a maximum of $4$ other destinations we can visit (i.e. edges), which is equivalent to $O(1)$. From all $O(MNK)$ nodes, we also obtain $O(MNK)$ total edges.

Our graph has $O(MNK)$ nodes and $O(MNK)$ edges. A BFS with $O(MNK)$ nodes and $O(MNK)$ edges will have a final time complexity of $O(MNK)$.

Time Complexity: $O(MNK)$

Space Complexity

Our graph has $O(MNK)$ nodes so a BFS will have a space complexity of $O(MNK)$ as well.

Space Complexity: $O(MNK)$

C++ solution

1class Solution {
2   public:
3    int shortestPath(vector<vector<int>>& grid, int k) {
4        int m = grid.size();
5        int n = grid[0].size();  // dimensions of the grid
6        vector<int> deltaX = {-1, 0, 1, 0};
7        vector<int> deltaY = {0, 1, 0, -1};
8        // nodes are in the form (row, column, obstacles removed so far)
9        int dis[m][n][k + 1];   // keeps track of distance of nodes
10        bool vis[m][n][k + 1];  // keeps track of whether or not we visited a node
11        memset(dis, 0, sizeof(dis));
12        memset(vis, false, sizeof(vis));
13        queue<vector<int>> q;
14        q.push({0, 0, 0});  // starting at upper left corner for BFS/floodfill
15        vis[0][0][0] = true;
16        while (!q.empty()) {
17            vector<int> cur = q.front();
18            q.pop();
19            int curX = cur[0];  // current row
20            int curY = cur[1];  // current column
21            int curK = cur[2];  // current obstacles removed
22            if (curX == m - 1 &&
23                curY == n - 1) {  // check if node is in bottom right corner
24                return dis[curX][curY][curK];
25            }
26            for (int i = 0; i < 4; i++) {
27                int newX = curX + deltaX[i];  // row of destination
28                int newY = curY + deltaY[i];  // column of destination
29                if (newX < 0 || newX >= m || newY < 0 ||
30                    newY >= n) {  // check if it's in boundary
31                    continue;
32                }
33                int newK = curK;  // obstacle count of destination
34                if (grid[newX][newY] == 1) newK++;
35                if (newK > k) {  // surpassed obstacle removal limit
36                    continue;
37                }
38                if (vis[newX][newY][newK]) {  // check if node has been visited before
39                    continue;
40                }
41                dis[newX][newY][newK] = dis[curX][curY][curK] + 1;
42                vis[newX][newY][newK] = true;
43                q.push({newX, newY, newK});
44                // process destination node
45            }
46        }
47        return -1;  // no valid answer found
48    }
49};

Java solution

1class Solution {
2    public int shortestPath(int[][] grid, int k) {
3        int m = grid.length;
4        int n = grid[0].length; // dimensions of the grid
5        int[] deltaX = {-1, 0, 1, 0};
6        int[] deltaY = {0, 1, 0, -1};
7        // nodes are in the form (row, column, obstacles removed so far)
8        int[][][] dis = new int[m][n][k + 1]; // keeps track of distance of nodes
9        boolean[][][] vis =
10            new boolean[m][n][k + 1]; // keeps track of whether or not we visited a node
11        Queue<int[]> q = new LinkedList<int[]>();
12        int[] start = {0, 0, 0};
13        q.add(start); // starting at upper left corner for BFS/floodfill
14        vis[0][0][0] = true;
15        while (!q.isEmpty()) {
16            int[] cur = q.poll();
17            int curX = cur[0]; // current row
18            int curY = cur[1]; // current column
19            int curK = cur[2]; // current obstacles removed
20            if (curX == m - 1
21                && curY == n - 1) { // check if node is in bottom right corner
22                return dis[curX][curY][curK];
23            }
24            for (int i = 0; i < 4; i++) {
25                int newX = curX + deltaX[i]; // row of destination
26                int newY = curY + deltaY[i]; // column of destination
27                if (newX < 0 || newX >= m || newY < 0
28                    || newY >= n) { // check if it's in boundary
29                    continue;
30                }
31                int newK = curK; // obstacle count of destination
32                if (grid[newX][newY] == 1)
33                    newK++;
34                if (newK > k) { // surpassed obstacle removal limit
35                    continue;
36                }
37                if (vis[newX][newY][newK]) { // check if node has been visited before
38                    continue;
39                }
40                dis[newX][newY][newK] = dis[curX][curY][curK] + 1;
41                vis[newX][newY][newK] = true;
42                int[] destination = {newX, newY, newK};
43                q.add(destination);
44                // process destination node
45            }
46        }
47        return -1; // no valid answer found
48    }
49}

Python Solution

1class Solution(object):
2    def shortestPath(self, grid, k):
3        """
4        :type grid: List[List[int]]
5        :type k: int
6        :rtype: int
7        """
8        m = len(grid)
9        n = len(grid[0])
10        # dimensions of the grid
11        deltaX = [-1, 0, 1, 0]
12        deltaY = [0, 1, 0, -1]
13        # nodes are in the form (row, column, obstacles removed so far)
14        dis = [
15            [[0 for x in range(k + 1)] for y in range(n)] for z in range(m)
16        ]  # keeps track of distance of nodes
17        vis = [
18            [[False for col in range(k + 1)] for col in range(n)] for row in range(m)
19        ]  # keeps track of whether or not we visited a node
20        q = []
21        q.append((0, 0, 0))  # starting at upper left corner for BFS/floodfill
22        vis[0][0][0] = True
23        while q:
24            (curX, curY, curK) = q.pop(0)
25            # curX refers to current row
26            # curY refers to current column
27            # curK refers to current obstacles removed
28            if (
29                curX == m - 1 and curY == n - 1
30            ):  # check if node is in bottom right corner
31                return dis[curX][curY][curK]
32            for i in range(4):
33                newX = curX + deltaX[i]  # row of destination
34                newY = curY + deltaY[i]  # column of destination
35                if (
36                    newX < 0 or newX >= m or newY < 0 or newY >= n
37                ):  # check if it's in boundary
38                    continue
39                newK = curK  # obstacle count of destination
40                if grid[newX][newY] == 1:
41                    newK += 1
42                if newK > k:  # surpassed obstacle removal limit
43                    continue
44                if vis[newX][newY][newK]:  # check if node has been visited before
45                    continue
46                dis[newX][newY][newK] = dis[curX][curY][curK] + 1
47                vis[newX][newY][newK] = True
48                q.append((newX, newY, newK))
49                # process destination node
50        return -1  # no valid answer found
51

Javascript Solution

1/**
2 * @param {number[][]} grid
3 * @param {number} k
4 * @return {number}
5 */
6var shortestPath = function (grid, k) {
7  const m = grid.length;
8  const n = grid[0].length; // dimensions of the grid
9  let deltaX = [-1, 0, 1, 0];
10  let deltaY = [0, 1, 0, -1];
11  // nodes are in the form (row, column, obstacles removed so far)
12  let dis = new Array(m)
13    .fill()
14    .map((_) => new Array(n).fill().map((_) => new Array(k).fill(0)));
15  // keeps track of distance of nodes
16  let vis = new Array(m)
17    .fill()
18    .map((_) => new Array(n).fill().map((_) => new Array(k).fill(false)));
19  // keeps track of whether or not we visited a node
20  let q = [[0, 0, 0]]; // starting at upper left corner for BFS/floodfill
21  vis[0][0][0] = true;
22  while (q.length > 0) {
23    let [curX, curY, curK] = q.shift();
24    // curX refers to current row
25    // curY refers to current column
26    // curK refers to current obstacles removed
27    if (curX == m - 1 && curY == n - 1) {
28      // check if node is in bottom right corner
29      return dis[curX][curY][curK];
30    }
31    for (let i = 0; i < 4; i++) {
32      let newX = curX + deltaX[i]; // row of destination
33      let newY = curY + deltaY[i]; // column of destination
34      if (newX < 0 || newX >= m || newY < 0 || newY >= n) {
35        // check if it's in boundary
36        continue;
37      }
38      let newK = curK; // obstacle count of destination
39      if (grid[newX][newY] === 1) {
40        newK++;
41      }
42      if (newK > k) {
43        // surpassed obstacle removal limit
44        continue;
45      }
46      if (vis[newX][newY][newK]) {
47        // check if node has been visited before
48        continue;
49      }
50      dis[newX][newY][newK] = dis[curX][curY][curK] + 1;
51      vis[newX][newY][newK] = true;
52      q.push([newX, newY, newK]);
53      // process destination node
54    }
55  }
56  return -1; // no valid answer found
57};

Solution Implementation