Katkat
Back

Shortest Path in a Grid with Limited Obstacle Removal

ByteDanceSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to adapt Breadth-First Search (BFS) to a state-space graph where the state includes both spatial coordinates and a remaining resource constraint.

Problem Statement

You are given an m x n grid where each cell is either a 0 (empty) or a 1 (obstacle). You start at the top-left corner (0, 0) and want to reach the bottom-right corner (m-1, n-1).

You are allowed to remove at most k obstacles in total to create a path. Your goal is to find the length of the shortest path from the start to the destination. If it is impossible to reach the destination, return -1.

Function Signature

def shortestPath(grid: List[List[int]], k: int) -> int:

Constraints

  • m, n are in the range [1, 40].
  • k is in the range [0, m * n].
  • grid[i][j] is either 0 or 1.

Examples

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 is (0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2) -> (3,2) -> (4,2). Removing the obstacle at (3,2) costs 1, which is within the limit k=1.

Example 2: Input: grid = [[0,1,1],[1,1,1],[1,0,0]], k = 1 Output: -1

Edge Cases

  • The start or end cell itself might be an obstacle.
  • k might be large enough to clear every obstacle in the grid.
  • Grid size might be 1 x 1.

Hints

Hint 1

Consider the state as a triple (row, col, remaining_k) to track your progress through the grid.

Hint 2

Since we are looking for the shortest path in an unweighted grid, Breadth-First Search (BFS) is the optimal approach.

Hint 3

Use a 3D boolean array `visited[row][col][remaining_k]` to avoid redundant calculations and infinite loops.

Follow-up questions

  • How would the solution change if you had a weight associated with each cell instead of a binary obstacle state?
  • What is the time and space complexity of your solution in terms of m, n, and k?
  • If the grid were extremely large (e.g., 1000x1000) and `k` was small, could you optimize the memory usage?