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.
A storekeeper is a game in which the player pushes boxes around in a warehouse trying to get them to target locations.
The game is represented by an m x n grid of characters grid where each element is a wall, floor, or box.
Your task is to move the box 'B' to the target position 'T' under the following rules:
'S' represents the player. The player can move up, down, left, right in grid if it is a floor (empty cell).'.' represents the floor which means a free cell to walk.'#' represents the wall which means an obstacle (impossible to walk there).'B' and one target cell 'T' in the grid.Return the minimum number of pushes to move the box to the target. If there is no way to reach the target, return -1.
Example 1:
Input: grid = [["#","#","#","#","#","#"],
["#","T","#","#","#","#"],
["#",".",".","B",".","#"],
["#",".","#","#",".","#"],
["#",".",".",".","S","#"],
["#","#","#","#","#","#"]]
Output: 3
Explanation: We return only the number of times the box is pushed.
Example 2:
Input: grid = [["#","#","#","#","#","#"],
["#","T","#","#","#","#"],
["#",".",".","B",".","#"],
["#","#","#","#",".","#"],
["#",".",".",".","S","#"],
["#","#","#","#","#","#"]]
Output: -1
Example 3:
Input: grid = [["#","#","#","#","#","#"],
["#","T",".",".","#","#"],
["#",".","#","B",".","#"],
["#",".",".",".",".","#"],
["#",".",".",".","S","#"],
["#","#","#","#","#","#"]]
Output: 5
Explanation: push the box down, left, left, up and up.
Constraints:
m == grid.lengthn == grid[i].length1 <= m, n <= 20grid contains only characters '.', '#', 'S', 'T', or 'B'.'S', 'B', and 'T' in the grid.Problem summary: A storekeeper is a game in which the player pushes boxes around in a warehouse trying to get them to target locations. The game is represented by an m x n grid of characters grid where each element is a wall, floor, or box. Your task is to move the box 'B' to the target position 'T' under the following rules: The character 'S' represents the player. The player can move up, down, left, right in grid if it is a floor (empty cell). The character '.' represents the floor which means a free cell to walk. The character '#' represents the wall which means an obstacle (impossible to walk there). There is only one box 'B' and one target cell 'T' in the grid. The box can be moved to an adjacent free cell by standing next to the box and then moving in the direction of the box. This is a push. The player cannot walk through the box. Return the minimum number of pushes to move the box to the target.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Array
[["#","#","#","#","#","#"],["#","T","#","#","#","#"],["#",".",".","B",".","#"],["#",".","#","#",".","#"],["#",".",".",".","S","#"],["#","#","#","#","#","#"]]
[["#","#","#","#","#","#"],["#","T","#","#","#","#"],["#",".",".","B",".","#"],["#","#","#","#",".","#"],["#",".",".",".","S","#"],["#","#","#","#","#","#"]]
[["#","#","#","#","#","#"],["#","T",".",".","#","#"],["#",".","#","B",".","#"],["#",".",".",".",".","#"],["#",".",".",".","S","#"],["#","#","#","#","#","#"]]
Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #1263: Minimum Moves to Move a Box to Their Target Location
class Solution {
private int m;
private int n;
private char[][] grid;
public int minPushBox(char[][] grid) {
m = grid.length;
n = grid[0].length;
this.grid = grid;
int si = 0, sj = 0, bi = 0, bj = 0;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == 'S') {
si = i;
sj = j;
} else if (grid[i][j] == 'B') {
bi = i;
bj = j;
}
}
}
int[] dirs = {-1, 0, 1, 0, -1};
Deque<int[]> q = new ArrayDeque<>();
boolean[][] vis = new boolean[m * n][m * n];
q.offer(new int[] {f(si, sj), f(bi, bj), 0});
vis[f(si, sj)][f(bi, bj)] = true;
while (!q.isEmpty()) {
var p = q.poll();
int d = p[2];
bi = p[1] / n;
bj = p[1] % n;
if (grid[bi][bj] == 'T') {
return d;
}
si = p[0] / n;
sj = p[0] % n;
for (int k = 0; k < 4; ++k) {
int sx = si + dirs[k], sy = sj + dirs[k + 1];
if (!check(sx, sy)) {
continue;
}
if (sx == bi && sy == bj) {
int bx = bi + dirs[k], by = bj + dirs[k + 1];
if (!check(bx, by) || vis[f(sx, sy)][f(bx, by)]) {
continue;
}
vis[f(sx, sy)][f(bx, by)] = true;
q.offer(new int[] {f(sx, sy), f(bx, by), d + 1});
} else if (!vis[f(sx, sy)][f(bi, bj)]) {
vis[f(sx, sy)][f(bi, bj)] = true;
q.offerFirst(new int[] {f(sx, sy), f(bi, bj), d});
}
}
}
return -1;
}
private int f(int i, int j) {
return i * n + j;
}
private boolean check(int i, int j) {
return i >= 0 && i < m && j >= 0 && j < n && grid[i][j] != '#';
}
}
// Accepted solution for LeetCode #1263: Minimum Moves to Move a Box to Their Target Location
func minPushBox(grid [][]byte) int {
m, n := len(grid), len(grid[0])
var si, sj, bi, bj int
for i, row := range grid {
for j, c := range row {
if c == 'S' {
si, sj = i, j
} else if c == 'B' {
bi, bj = i, j
}
}
}
f := func(i, j int) int {
return i*n + j
}
check := func(i, j int) bool {
return i >= 0 && i < m && j >= 0 && j < n && grid[i][j] != '#'
}
q := [][]int{[]int{f(si, sj), f(bi, bj), 0}}
vis := make([][]bool, m*n)
for i := range vis {
vis[i] = make([]bool, m*n)
}
vis[f(si, sj)][f(bi, bj)] = true
dirs := [5]int{-1, 0, 1, 0, -1}
for len(q) > 0 {
p := q[0]
q = q[1:]
si, sj, bi, bj = p[0]/n, p[0]%n, p[1]/n, p[1]%n
d := p[2]
if grid[bi][bj] == 'T' {
return d
}
for k := 0; k < 4; k++ {
sx, sy := si+dirs[k], sj+dirs[k+1]
if !check(sx, sy) {
continue
}
if sx == bi && sy == bj {
bx, by := bi+dirs[k], bj+dirs[k+1]
if !check(bx, by) || vis[f(sx, sy)][f(bx, by)] {
continue
}
vis[f(sx, sy)][f(bx, by)] = true
q = append(q, []int{f(sx, sy), f(bx, by), d + 1})
} else if !vis[f(sx, sy)][f(bi, bj)] {
vis[f(sx, sy)][f(bi, bj)] = true
q = append([][]int{[]int{f(sx, sy), f(bi, bj), d}}, q...)
}
}
}
return -1
}
# Accepted solution for LeetCode #1263: Minimum Moves to Move a Box to Their Target Location
class Solution:
def minPushBox(self, grid: List[List[str]]) -> int:
def f(i: int, j: int) -> int:
return i * n + j
def check(i: int, j: int) -> bool:
return 0 <= i < m and 0 <= j < n and grid[i][j] != "#"
for i, row in enumerate(grid):
for j, c in enumerate(row):
if c == "S":
si, sj = i, j
elif c == "B":
bi, bj = i, j
m, n = len(grid), len(grid[0])
dirs = (-1, 0, 1, 0, -1)
q = deque([(f(si, sj), f(bi, bj), 0)])
vis = [[False] * (m * n) for _ in range(m * n)]
vis[f(si, sj)][f(bi, bj)] = True
while q:
s, b, d = q.popleft()
bi, bj = b // n, b % n
if grid[bi][bj] == "T":
return d
si, sj = s // n, s % n
for a, b in pairwise(dirs):
sx, sy = si + a, sj + b
if not check(sx, sy):
continue
if sx == bi and sy == bj:
bx, by = bi + a, bj + b
if not check(bx, by) or vis[f(sx, sy)][f(bx, by)]:
continue
vis[f(sx, sy)][f(bx, by)] = True
q.append((f(sx, sy), f(bx, by), d + 1))
elif not vis[f(sx, sy)][f(bi, bj)]:
vis[f(sx, sy)][f(bi, bj)] = True
q.appendleft((f(sx, sy), f(bi, bj), d))
return -1
// Accepted solution for LeetCode #1263: Minimum Moves to Move a Box to Their Target Location
struct Solution;
use std::cmp::Reverse;
use std::collections::BinaryHeap;
use std::collections::HashSet;
type State = (i32, i32, i32, i32);
impl Solution {
fn min_push_box(grid: Vec<Vec<char>>) -> i32 {
let n = grid.len();
let m = grid[0].len();
let mut floors: HashSet<(i32, i32)> = HashSet::new();
let mut state = (0, 0, 0, 0);
let mut t = (0, 0);
for i in 0..n {
for j in 0..m {
match grid[i][j] {
'S' => {
state.0 = i as i32;
state.1 = j as i32;
floors.insert((state.0, state.1));
}
'B' => {
state.2 = i as i32;
state.3 = j as i32;
floors.insert((state.2, state.3));
}
'T' => {
t = (i as i32, j as i32);
floors.insert(t);
}
'.' => {
floors.insert((i as i32, j as i32));
}
_ => {}
}
}
}
let mut queue: BinaryHeap<(Reverse<i32>, State)> = BinaryHeap::new();
queue.push((Reverse(0), state));
let mut visited: HashSet<State> = HashSet::new();
visited.insert(state);
let dirs = vec![(1, 0), (0, 1), (-1, 0), (0, -1)];
while let Some((Reverse(step), state)) = queue.pop() {
if (state.2, state.3) == t {
return step;
}
for (di, dj) in &dirs {
let pi = state.0 + di;
let pj = state.1 + dj;
let bi = state.2;
let bj = state.3;
if (state.2, state.3) == (pi, pj) {
let next_state = (pi, pj, bi + di, bj + dj);
if floors.contains(&(bi, bj)) && visited.insert(next_state) {
queue.push((Reverse(step + 1), next_state));
}
} else {
let next_state = (pi, pj, bi, bj);
if floors.contains(&(pi, pj)) && visited.insert(next_state) {
queue.push((Reverse(step), next_state));
}
}
}
}
-1
}
}
#[test]
fn test() {
let grid = vec_vec_char![
['#', '#', '#', '#', '#', '#'],
['#', 'T', '#', '#', '#', '#'],
['#', '.', '.', 'B', '.', '#'],
['#', '.', '#', '#', '.', '#'],
['#', '.', '.', '.', 'S', '#'],
['#', '#', '#', '#', '#', '#']
];
let res = 3;
assert_eq!(Solution::min_push_box(grid), res);
let grid = vec_vec_char![
['#', '#', '#', '#', '#', '#'],
['#', 'T', '#', '#', '#', '#'],
['#', '.', '.', 'B', '.', '#'],
['#', '#', '#', '#', '.', '#'],
['#', '.', '.', '.', 'S', '#'],
['#', '#', '#', '#', '#', '#']
];
let res = -1;
assert_eq!(Solution::min_push_box(grid), res);
let grid = vec_vec_char![
['#', '#', '#', '#', '#', '#'],
['#', 'T', '.', '.', '#', '#'],
['#', '.', '#', 'B', '.', '#'],
['#', '.', '.', '.', '.', '#'],
['#', '.', '.', '.', 'S', '#'],
['#', '#', '#', '#', '#', '#']
];
let res = 5;
assert_eq!(Solution::min_push_box(grid), res);
let grid = vec_vec_char![
['#', '#', '#', '#', '#', '#', '#'],
['#', 'S', '#', '.', 'B', 'T', '#'],
['#', '#', '#', '#', '#', '#', '#']
];
let res = -1;
assert_eq!(Solution::min_push_box(grid), res);
let grid = vec_vec_char![
['.', '.', '#', '.', '.', '.', '.', '.', '.', '.'],
['.', '#', '.', '#', 'B', '#', '.', '#', '.', '.'],
['.', '#', '.', '.', '.', '.', '.', '.', 'T', '.'],
['#', '.', '.', '.', '.', '.', '.', '.', '.', '.'],
['.', '.', '.', '.', '.', '.', '.', '.', '.', '#'],
['.', '.', '.', '.', '.', '.', '.', '.', '#', '.'],
['.', '.', '.', '#', '.', '.', '#', '#', '.', '.'],
['.', '.', '.', '.', '#', '.', '.', '#', '.', '.'],
['.', '#', '.', 'S', '.', '.', '.', '.', '.', '.'],
['#', '.', '.', '#', '.', '.', '.', '.', '.', '#']
];
let res = 5;
assert_eq!(Solution::min_push_box(grid), res);
}
// Accepted solution for LeetCode #1263: Minimum Moves to Move a Box to Their Target Location
function minPushBox(grid: string[][]): number {
const [m, n] = [grid.length, grid[0].length];
let [si, sj, bi, bj] = [0, 0, 0, 0];
for (let i = 0; i < m; ++i) {
for (let j = 0; j < n; ++j) {
if (grid[i][j] === 'S') {
[si, sj] = [i, j];
} else if (grid[i][j] === 'B') {
[bi, bj] = [i, j];
}
}
}
const f = (i: number, j: number): number => i * n + j;
const check = (i: number, j: number): boolean =>
i >= 0 && i < m && j >= 0 && j < n && grid[i][j] !== '#';
const q: Deque<[number, number, number]> = new Deque();
const vis: boolean[][] = new Array(m * n).fill(0).map(() => new Array(m * n).fill(false));
q.push([f(si, sj), f(bi, bj), 0]);
vis[f(si, sj)][f(bi, bj)] = true;
const dirs: number[] = [-1, 0, 1, 0, -1];
while (q.size() > 0) {
const [s, b, d] = q.shift()!;
const [si, sj] = [Math.floor(s / n), s % n];
const [bi, bj] = [Math.floor(b / n), b % n];
if (grid[bi][bj] === 'T') {
return d;
}
for (let k = 0; k < 4; ++k) {
const [sx, sy] = [si + dirs[k], sj + dirs[k + 1]];
if (!check(sx, sy)) {
continue;
}
if (sx === bi && sy === bj) {
const [bx, by] = [bi + dirs[k], bj + dirs[k + 1]];
if (!check(bx, by) || vis[f(sx, sy)][f(bx, by)]) {
continue;
}
vis[f(sx, sy)][f(bx, by)] = true;
q.push([f(sx, sy), f(bx, by), d + 1]);
} else if (!vis[f(sx, sy)][f(bi, bj)]) {
vis[f(sx, sy)][f(bi, bj)] = true;
q.unshift([f(sx, sy), f(bi, bj), d]);
}
}
}
return -1;
}
/* 以下是双向列队模板类 */
class CircularDeque<T> {
prev: CircularDeque<T> | null;
next: CircularDeque<T> | null;
begin: number;
end: number;
empty: boolean;
data: T[];
constructor(N: number) {
this.prev = this.next = null;
this.begin = this.end = 0;
this.empty = true;
this.data = Array(N);
}
isFull(): boolean {
return this.end === this.begin && !this.empty;
}
isEmpty(): boolean {
return this.empty;
}
push(val: T): boolean {
if (this.isFull()) return false;
this.empty = false;
this.data[this.end] = val;
this.end = (this.end + 1) % this.data.length;
return true;
}
front(): T | undefined {
return this.isEmpty() ? undefined : this.data[this.begin];
}
back(): T | undefined {
return this.isEmpty() ? undefined : this.data[this.end - 1];
}
pop(): T | undefined {
if (this.isEmpty()) return undefined;
const value = this.data[this.end - 1];
this.end = (this.end - 1) % this.data.length;
if (this.end < 0) this.end += this.data.length;
if (this.end === this.begin) this.empty = true;
return value;
}
unshift(val: T): boolean {
if (this.isFull()) return false;
this.empty = false;
this.begin = (this.begin - 1) % this.data.length;
if (this.begin < 0) this.begin += this.data.length;
this.data[this.begin] = val;
return true;
}
shift(): T | undefined {
if (this.isEmpty()) return undefined;
const value = this.data[this.begin];
this.begin = (this.begin + 1) % this.data.length;
if (this.end === this.begin) this.empty = true;
return value;
}
*values(): Generator<T, void, undefined> {
if (this.isEmpty()) return undefined;
let i = this.begin;
do {
yield this.data[i];
i = (i + 1) % this.data.length;
} while (i !== this.end);
}
}
class Deque<T> {
head: CircularDeque<T>;
tail: CircularDeque<T>;
_size: number;
constructor(collection: T[] = []) {
this.head = new CircularDeque<T>(128);
this.tail = new CircularDeque<T>(128);
this.tail.empty = this.head.empty = false;
this.tail.prev = this.head;
this.head.next = this.tail;
this._size = 0;
for (const item of collection) this.push(item);
}
size(): number {
return this._size;
}
push(val: T): void {
let last = this.tail.prev!;
if (last.isFull()) {
const inserted = new CircularDeque<T>(128);
this.tail.prev = inserted;
inserted.next = this.tail;
last.next = inserted;
inserted.prev = last;
last = inserted;
}
last.push(val);
this._size++;
}
back(): T | undefined {
if (this._size === 0) return;
return this.tail.prev!.back();
}
pop(): T | undefined {
if (this.head.next === this.tail) return undefined;
const last = this.tail.prev!;
const value = last.pop();
if (last.isEmpty()) {
this.tail.prev = last.prev;
last.prev!.next = this.tail;
}
this._size--;
return value;
}
unshift(val: T): void {
let first = this.head.next!;
if (first.isFull()) {
const inserted = new CircularDeque<T>(128);
this.head.next = inserted;
inserted.prev = this.head;
inserted.next = first;
first.prev = inserted;
first = inserted;
}
first.unshift(val);
this._size++;
}
shift(): T | undefined {
if (this.head.next === this.tail) return undefined;
const first = this.head.next!;
const value = first.shift();
if (first.isEmpty()) {
this.head.next = first.next;
first.next!.prev = this.head;
}
this._size--;
return value;
}
front(): T | undefined {
if (this._size === 0) return undefined;
return this.head.next!.front();
}
*values(): Generator<T, void, undefined> {
let node = this.head.next!;
while (node !== this.tail) {
for (const value of node.values()) yield value;
node = node.next!;
}
}
}
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.