Shortest path with wall removal
You are given an m x n grid where each cell is 0 (open) or 1 (wall). Starting at the top-left (0,0) and moving 4-directionally to the bottom-right (m-1,n-1), you may remove at most k walls along your path. Return the minimum number of steps to reach the bottom-right, or -1 if it cannot be reached even after removing up to k walls. You cannot leave the grid. If the start cell is a wall it counts against your budget too.
Implement
min_steps_with_removals(grid: list[list[int]], k: int) → intExamples
in
[[[0,1,0],[0,1,0],[0,0,0]],1]out4What a strong answer looks like
State your approach and its time/space complexity out loud before you optimize. Handle the edge cases (empty input, duplicates, overflow), and say why you chose this over the brute force. Green tests are the floor, not the grade.
0:00 of about 40 min
solution.py
InputExpectedGot
[[[0,1,0],[0,1,0],[0,0,0]],1]4not run yetsample