Katkat
Back

Minimum Path Length Through a Grid With One Allowed Cell Conversion

AmazonSoftware Engineer · Online Assessment
MediumSoftware EngineerOnline AssessmentCoding & Algorithms

Last updated

This problem tests your ability to adapt BFS to a state-space graph where an additional dimension represents the remaining capacity to modify the grid, requiring efficient state tracking to find the shortest path.

Minimum Path Length With One Conversion

You are given an m x n binary grid where 0 represents an empty path and 1 represents an obstacle. You start at the top-left corner (0, 0) and want to reach the bottom-right corner (m-1, n-1). You can move up, down, left, or right to any adjacent cell that contains a 0.

You are allowed to convert at most one obstacle (1) into an empty path (0) to make the traversal possible. Return the length of the shortest path from the start to the end. If it is impossible to reach the target, return -1.

Function Signature

def shortest_path(grid: List[List[int]]) -> int:

Constraints

  • m, n are between 1 and 100.
  • grid[i][j] is either 0 or 1.
  • grid[0][0] and grid[m-1][n-1] are always 0.

Examples

Example 1: Input: grid = [[0, 1], [1, 0]] Output: 3 Explanation: Converting one 1 allows a path of length 3 (e.g., (0,0) -> (0,1) -> (1,1)).

Example 2: Input: grid = [[0, 0, 0], [1, 1, 0], [0, 0, 0]] Output: 5 Explanation: No conversion needed; the path follows the existing zeros.

Edge Cases

  • Grids where m=1 or n=1.
  • Paths where no conversion is necessary vs. paths that strictly require one conversion.

Hints

Hint 1

Represent your state in BFS as a tuple containing `(row, col, has_converted)`, where `has_converted` is a boolean indicating if you have already removed an obstacle.

Hint 2

When traversing, if you encounter a `1` and `has_converted` is `False`, you can move into that cell and update the state to `has_converted = True`.

Hint 3

Use a 3D array or a set of tuples to keep track of visited states `(row, col, has_converted)` to avoid cycles and redundant computation.

Follow-up questions

  • How would you modify your approach if you were allowed to remove up to 'k' obstacles instead of just one?
  • What is the time and space complexity of your solution in terms of 'm' and 'n'?
  • Could you solve this using Dijkstra's algorithm instead of BFS? When would that be beneficial?