Shortest Path in a Grid with Obstacles Elimination
Hard · Queue & Deque · about 30 minutes
Asked at Google, Amazon, Databricks, Cisco, Meta, Arista Networks, Hugging Face.
Given an m × n grid of 0s (empty) and 1s (obstacles), you start at the top-left and want to reach the bottom-right moving up, down, left or right. You may walk through at most k obstacles (eliminating them). Return the minimum number of steps, or -1 if it's impossible.