Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Break down a hard problem into reliable checkpoints, edge-case handling, and complexity trade-offs.
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.
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 without eliminating any obstacle is 10. The shortest path with one obstacle elimination at position (3,2) is 6. Such path is (0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2) -> (3,2) -> (4,2).
Example 2:
Input: grid = [[0,1,1],[1,1,1],[1,0,0]], k = 1 Output: -1 Explanation: We need to eliminate at least two obstacles to find such a walk.
Constraints:
m == grid.lengthn == grid[i].length1 <= m, n <= 401 <= k <= m * ngrid[i][j] is either 0 or 1.grid[0][0] == grid[m - 1][n - 1] == 0Problem summary: 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.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Array
[[0,0,0],[1,1,0],[0,0,0],[0,1,1],[0,0,0]] 1
[[0,1,1],[1,1,1],[1,0,0]] 1
shortest-path-to-get-food)minimum-obstacle-removal-to-reach-corner)find-a-safe-walk-through-a-grid)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #1293: Shortest Path in a Grid with Obstacles Elimination
class Solution {
public int shortestPath(int[][] grid, int k) {
int m = grid.length;
int n = grid[0].length;
if (k >= m + n - 3) {
return m + n - 2;
}
Deque<int[]> q = new ArrayDeque<>();
q.offer(new int[] {0, 0, k});
boolean[][][] vis = new boolean[m][n][k + 1];
vis[0][0][k] = true;
int ans = 0;
int[] dirs = {-1, 0, 1, 0, -1};
while (!q.isEmpty()) {
++ans;
for (int i = q.size(); i > 0; --i) {
int[] p = q.poll();
k = p[2];
for (int j = 0; j < 4; ++j) {
int x = p[0] + dirs[j];
int y = p[1] + dirs[j + 1];
if (x >= 0 && x < m && y >= 0 && y < n) {
if (x == m - 1 && y == n - 1) {
return ans;
}
if (grid[x][y] == 0 && !vis[x][y][k]) {
q.offer(new int[] {x, y, k});
vis[x][y][k] = true;
} else if (grid[x][y] == 1 && k > 0 && !vis[x][y][k - 1]) {
q.offer(new int[] {x, y, k - 1});
vis[x][y][k - 1] = true;
}
}
}
}
}
return -1;
}
}
// Accepted solution for LeetCode #1293: Shortest Path in a Grid with Obstacles Elimination
func shortestPath(grid [][]int, k int) int {
m, n := len(grid), len(grid[0])
if k >= m+n-3 {
return m + n - 2
}
q := [][]int{[]int{0, 0, k}}
vis := make([][][]bool, m)
for i := range vis {
vis[i] = make([][]bool, n)
for j := range vis[i] {
vis[i][j] = make([]bool, k+1)
}
}
vis[0][0][k] = true
dirs := []int{-1, 0, 1, 0, -1}
ans := 0
for len(q) > 0 {
ans++
for i := len(q); i > 0; i-- {
p := q[0]
q = q[1:]
k = p[2]
for j := 0; j < 4; j++ {
x, y := p[0]+dirs[j], p[1]+dirs[j+1]
if x >= 0 && x < m && y >= 0 && y < n {
if x == m-1 && y == n-1 {
return ans
}
if grid[x][y] == 0 && !vis[x][y][k] {
q = append(q, []int{x, y, k})
vis[x][y][k] = true
} else if grid[x][y] == 1 && k > 0 && !vis[x][y][k-1] {
q = append(q, []int{x, y, k - 1})
vis[x][y][k-1] = true
}
}
}
}
}
return -1
}
# Accepted solution for LeetCode #1293: Shortest Path in a Grid with Obstacles Elimination
class Solution:
def shortestPath(self, grid: List[List[int]], k: int) -> int:
m, n = len(grid), len(grid[0])
if k >= m + n - 3:
return m + n - 2
q = deque([(0, 0, k)])
vis = {(0, 0, k)}
ans = 0
while q:
ans += 1
for _ in range(len(q)):
i, j, k = q.popleft()
for a, b in [[0, -1], [0, 1], [1, 0], [-1, 0]]:
x, y = i + a, j + b
if 0 <= x < m and 0 <= y < n:
if x == m - 1 and y == n - 1:
return ans
if grid[x][y] == 0 and (x, y, k) not in vis:
q.append((x, y, k))
vis.add((x, y, k))
if grid[x][y] == 1 and k > 0 and (x, y, k - 1) not in vis:
q.append((x, y, k - 1))
vis.add((x, y, k - 1))
return -1
// Accepted solution for LeetCode #1293: Shortest Path in a Grid with Obstacles Elimination
struct Solution;
use std::collections::HashSet;
use std::collections::VecDeque;
impl Solution {
fn shortest_path(grid: Vec<Vec<i32>>, k: i32) -> i32 {
let n = grid.len();
let m = grid[0].len();
let mut queue: VecDeque<(usize, usize, i32, i32)> = VecDeque::new();
let mut visited: HashSet<(usize, usize, i32)> = HashSet::new();
queue.push_back((0, 0, k, 0));
visited.insert((0, 0, k));
while let Some((i, j, left, step)) = queue.pop_front() {
if i == n - 1 && j == m - 1 {
return step;
}
let nstep = step + 1;
for &(di, dj) in &[(-1, 0), (1, 0), (0, -1), (0, 1)] {
let ni = i as i32 + di;
let nj = j as i32 + dj;
if 0 <= ni && ni < n as i32 && 0 <= nj && nj < m as i32 {
let ni = ni as usize;
let nj = nj as usize;
let nleft = left - grid[ni][nj];
if nleft >= 0 && visited.insert((ni, nj, nleft)) {
queue.push_back((ni, nj, nleft, nstep));
}
}
}
}
-1
}
}
#[test]
fn test() {
let grid = vec_vec_i32![[0, 0, 0], [1, 1, 0], [0, 0, 0], [0, 1, 1], [0, 0, 0]];
let k = 1;
let res = 6;
assert_eq!(Solution::shortest_path(grid, k), res);
let grid = vec_vec_i32![[0, 1, 1], [1, 1, 1], [1, 0, 0]];
let k = 1;
let res = -1;
assert_eq!(Solution::shortest_path(grid, k), res);
}
// Accepted solution for LeetCode #1293: Shortest Path in a Grid with Obstacles Elimination
function shortestPath(grid: number[][], k: number): number {
const m = grid.length;
const n = grid[0].length;
if (k >= m + n - 3) {
return m + n - 2;
}
let q: Point[] = [[0, 0, k]];
const vis = Array.from({ length: m }, () =>
Array.from({ length: n }, () => Array.from({ length: k + 1 }, () => false)),
);
vis[0][0][k] = true;
const dirs = [0, 1, 0, -1, 0];
let ans = 0;
while (q.length) {
const nextQ: Point[] = [];
++ans;
for (const [i, j, k] of q) {
for (let d = 0; d < 4; ++d) {
const [x, y] = [i + dirs[d], j + dirs[d + 1]];
if (x === m - 1 && y === n - 1) {
return ans;
}
const v = grid[x]?.[y];
if (v === 0 && !vis[x][y][k]) {
nextQ.push([x, y, k]);
vis[x][y][k] = true;
} else if (v === 1 && k > 0 && !vis[x][y][k - 1]) {
nextQ.push([x, y, k - 1]);
vis[x][y][k - 1] = true;
}
}
}
q = nextQ;
}
return -1;
}
type Point = [number, number, number];
Use this to step through a reusable interview workflow for this problem.
Two nested loops check every pair or subarray. The outer loop fixes a starting point, the inner loop extends or searches. For n elements this gives up to n²/2 operations. No extra space, but the quadratic time is prohibitive for large inputs.
Most array problems have an O(n²) brute force (nested loops) and an O(n) optimal (single pass with clever state tracking). The key is identifying what information to maintain as you scan: a running max, a prefix sum, a hash map of seen values, or two pointers.
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.