Skip to main content

1293. Shortest Path in a Grid with Obstacles Elimination

hardAsked at Uber

Given a 0/1 grid where 1s are obstacles and you can eliminate up to k of them, return the shortest path from top-left to bottom-right. Uber asks this to test BFS with a 3D state (row, col, remaining eliminations).

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Uber loops.

  • Glassdoor (2026-Q1)— Uber L5 onsite reports include this as a recurring BFS hard.
  • Blind (2025-11)— Mentioned in Uber dispatch / map team interviews.

Problem

You are given an m x n integer matrix grid where each cell is either 0 (empty) or 1 (obstacle). You can move up, down, left, or right from and to an empty cell in one step. 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 it is not possible to find such walk return -1.

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

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: Shortest path goes around obstacles; only one elimination saves steps.

Example 2

Input
grid = [[0,1,1],[1,1,1],[1,0,0]], k = 1
Output
-1

Explanation: With only 1 elimination, no path is feasible.

Approaches

1. BFS with (row, col) state — wrong without k dimension

Standard BFS, ignoring k. Fails because you might reach a cell with too few eliminations left, blocking the shortest path through obstacles.

Time
O(m * n)
Space
O(m * n)
// This is intentionally wrong — kept as a teaching foil.
function shortestPathWrong(grid, k) {
  // BFS without tracking remaining eliminations doesn't work.
  // Two paths may reach the same cell but with different leftover eliminations,
  // and the one with fewer eliminations might be the only one that can finish.
  return -1;
}

Tradeoff: Conceptual: visiting a cell isn't enough — the (cell, eliminations) state is what's unique. Use this to articulate why the next solution adds the third dimension.

2. BFS with (row, col, k_remaining) state (optimal)

Each state is (r, c, remaining eliminations). BFS gives the shortest path because all edges cost 1. Track visited by (r, c, k).

Time
O(m * n * k)
Space
O(m * n * k)
function shortestPath(grid, k) {
  const m = grid.length, n = grid[0].length;
  if (m === 1 && n === 1) return 0;
  k = Math.min(k, m + n - 3);
  if (k >= m + n - 2) return m + n - 2;
  const visited = Array.from({ length: m }, () => Array.from({ length: n }, () => -1));
  visited[0][0] = k;
  let queue = [[0, 0, k]];
  let steps = 0;
  const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
  while (queue.length) {
    steps++;
    const next = [];
    for (const [r, c, rem] of queue) {
      for (const [dr, dc] of dirs) {
        const nr = r + dr, nc = c + dc;
        if (nr < 0 || nc < 0 || nr >= m || nc >= n) continue;
        const nrem = rem - grid[nr][nc];
        if (nrem < 0) continue;
        if (nr === m - 1 && nc === n - 1) return steps;
        if (visited[nr][nc] >= nrem) continue;
        visited[nr][nc] = nrem;
        next.push([nr, nc, nrem]);
      }
    }
    queue = next;
  }
  return -1;
}

Tradeoff: The 3D state space is what enables correctness. BFS layer-by-layer gives shortest. The 'visited[nr][nc] >= nrem' check is the key pruning — re-visiting with fewer eliminations is never useful.

Uber-specific tips

Uber's bar here is realizing the state needs to include k. Say: 'Two paths can reach the same cell with different remaining eliminations. The one with more eliminations dominates strictly — never revisit a cell with fewer-or-equal eliminations than a previous visit.' That insight is what's being graded.

Common mistakes

  • Tracking visited by (row, col) only — misses the case where a different elimination count enables a shorter finish.
  • Forgetting the 'k >= m + n - 2' early return that handles unlimited eliminations.
  • Counting the start cell as a step (it isn't).

Follow-up questions

An interviewer at Uber may pivot to one of these next:

  • What if movement cost varied? (Dijkstra with the same 3D state.)
  • What if you could only eliminate obstacles within a budget of mana points? (Same idea, k = remaining mana.)
  • Shortest path in binary matrix (LC 1091) — same template without the elimination dimension.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why is BFS layer-by-layer correct here?

All edges cost 1, so BFS expands cells in order of distance. The first time you reach the destination, you've found the shortest path.

Why prune with visited[nr][nc] >= nrem?

If we've already reached (nr, nc) with as many or more eliminations remaining, the new path is strictly weaker — same distance from start, fewer eliminations. No reason to enqueue.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

Drill Shortest Path in a Grid with Obstacles Elimination and other Uber interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →