1263. Minimum Moves to Move a Box to Their Target Location

HardBreadth-First SearchArrayMatrixHeap (Priority Queue)
Leetcode Link

Problem Description

This problem is about a Sokoban-style puzzle game where you control a player who needs to push a box to a target location on a grid.

The game is played on an m x n grid where each cell contains one of the following characters:

  • 'S' - The starting position of the player
  • 'B' - The position of the box that needs to be moved
  • 'T' - The target position where the box should be pushed to
  • '.' - An empty floor cell where the player can walk
  • '#' - A wall that blocks movement

The rules of the game are:

  1. The player can move up, down, left, or right to any adjacent floor cell (empty cell), but cannot walk through walls or the box
  2. To move the box, the player must be adjacent to it and then move in the direction of the box - this pushes the box one cell in that direction
  3. The box can only be pushed to an empty floor cell (not through walls)
  4. There is exactly one box and one target position in the grid

The goal is to find the minimum number of pushes needed to move the box from its starting position to the target position. If it's impossible to push the box to the target, return -1.

For example, if the player is to the left of the box and moves right, the box will be pushed one cell to the right (assuming there's an empty cell there). The player ends up where the box was, and the box moves to the next cell in that direction.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

  • Yes: This problem can be modeled as a graph where each state (player position + box position) is a node, and edges represent valid moves between states.

Is it a tree?

  • No: The state space is not a tree structure. Multiple paths can lead to the same state (same player and box positions can be reached through different sequences of moves).

Is the problem related to directed acyclic graphs?

  • No: The state graph can have cycles (the player can move back and forth, returning to previous states).

Is the problem related to shortest paths?

  • Yes: We need to find the minimum number of pushes to move the box to the target, which is essentially finding the shortest path in terms of push operations.

Is the graph Weighted?

  • No: Each push operation has the same cost (1 push). The edges in our state graph are unweighted - we're counting the number of pushes, not calculating weighted distances.

BFS

  • Yes: Since we have an unweighted shortest path problem, BFS is the appropriate algorithm.

Conclusion: The flowchart suggests using BFS (Breadth-First Search) for finding the minimum number of pushes. The key insight is that this is a shortest path problem in an unweighted graph where states are (player_position, box_position) pairs, and we want to minimize the number of box pushes (not total moves).

Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

Intuition

The key insight is to recognize that this isn't just about finding a path for the player - it's about tracking two entities simultaneously: the player and the box. Each state in our search space needs to capture both positions: (player_position, box_position).

Why BFS? We want the minimum number of pushes. BFS naturally finds the shortest path in terms of the number of operations. But there's a subtle twist here - not all moves are equal. When the player moves without pushing the box, we haven't made progress toward our goal (no push occurred). When the player pushes the box, that's when we've made one unit of progress.

This leads to a critical optimization: we can use a double-ended queue (deque) to implement a "0-1 BFS". When the player moves without pushing (cost = 0), we add this state to the front of the queue. When the player pushes the box (cost = 1), we add it to the back. This ensures we explore all free moves before considering additional pushes, effectively grouping states by their push count.

The state representation is clever too. Instead of using 4D coordinates (player_i, player_j, box_i, box_j), we can flatten each 2D position into a single number using f(i, j) = i * n + j. This makes it easier to track visited states in a 2D array vis[player_state][box_state].

The search process works as follows:

  1. Try to move the player in all four directions
  2. If the player moves into the box's position, the box gets pushed in that same direction (if valid)
  3. If the player moves to an empty cell, it's just a repositioning move (no push)
  4. Keep track of visited states to avoid cycles
  5. Continue until the box reaches the target position

The beauty of this approach is that BFS guarantees we find the minimum number of pushes, while the deque optimization ensures we efficiently explore the state space by prioritizing free moves over pushes.

Learn more about Breadth-First Search and Heap (Priority Queue) patterns.

Solution Implementation

1class Solution: 2 def minPushBox(self, grid: List[List[str]]) -> int: 3 """ 4 Find minimum number of pushes to move box 'B' to target 'T' with person 'S'. 5 Uses BFS with state (person_position, box_position). 6 """ 7 8 def encode_position(row: int, col: int) -> int: 9 """Encode 2D grid position to 1D integer for efficient storage.""" 10 return row * cols + col 11 12 def is_valid_cell(row: int, col: int) -> bool: 13 """Check if a cell is within bounds and not a wall.""" 14 return 0 <= row < rows and 0 <= col < cols and grid[row][col] != "#" 15 16 # Find initial positions of person (S) and box (B) 17 person_row, person_col = 0, 0 18 box_row, box_col = 0, 0 19 20 for i, row in enumerate(grid): 21 for j, cell in enumerate(row): 22 if cell == "S": 23 person_row, person_col = i, j 24 elif cell == "B": 25 box_row, box_col = i, j 26 27 rows, cols = len(grid), len(grid[0]) 28 29 # Direction vectors: up, right, down, left 30 directions = (-1, 0, 1, 0, -1) 31 32 # BFS queue: (person_position, box_position, push_count) 33 queue = deque([(encode_position(person_row, person_col), 34 encode_position(box_row, box_col), 0)]) 35 36 # Visited states: visited[person_pos][box_pos] = True if visited 37 visited = [[False] * (rows * cols) for _ in range(rows * cols)] 38 visited[encode_position(person_row, person_col)][encode_position(box_row, box_col)] = True 39 40 while queue: 41 person_pos, box_pos, pushes = queue.popleft() 42 43 # Decode box position 44 current_box_row, current_box_col = box_pos // cols, box_pos % cols 45 46 # Check if box reached target 47 if grid[current_box_row][current_box_col] == "T": 48 return pushes 49 50 # Decode person position 51 current_person_row, current_person_col = person_pos // cols, person_pos % cols 52 53 # Try moving person in all four directions 54 for i in range(4): 55 next_person_row = current_person_row + directions[i] 56 next_person_col = current_person_col + directions[i + 1] 57 58 # Skip if next position is invalid 59 if not is_valid_cell(next_person_row, next_person_col): 60 continue 61 62 # Check if person would move to box position (push the box) 63 if next_person_row == current_box_row and next_person_col == current_box_col: 64 # Calculate new box position after push 65 next_box_row = current_box_row + directions[i] 66 next_box_col = current_box_col + directions[i + 1] 67 68 # Skip if box can't be pushed there or state already visited 69 if not is_valid_cell(next_box_row, next_box_col): 70 continue 71 if visited[encode_position(next_person_row, next_person_col)][encode_position(next_box_row, next_box_col)]: 72 continue 73 74 # Mark as visited and add to queue (push action increases count) 75 visited[encode_position(next_person_row, next_person_col)][encode_position(next_box_row, next_box_col)] = True 76 queue.append((encode_position(next_person_row, next_person_col), 77 encode_position(next_box_row, next_box_col), 78 pushes + 1)) 79 else: 80 # Person moves without pushing box 81 if not visited[encode_position(next_person_row, next_person_col)][encode_position(current_box_row, current_box_col)]: 82 # Mark as visited and add to front of queue (no push, same distance) 83 visited[encode_position(next_person_row, next_person_col)][encode_position(current_box_row, current_box_col)] = True 84 queue.appendleft((encode_position(next_person_row, next_person_col), 85 encode_position(current_box_row, current_box_col), 86 pushes)) 87 88 # No solution found 89 return -1 90
1class Solution { 2 private int rows; 3 private int cols; 4 private char[][] grid; 5 6 public int minPushBox(char[][] grid) { 7 // Initialize grid dimensions and store reference 8 rows = grid.length; 9 cols = grid[0].length; 10 this.grid = grid; 11 12 // Find initial positions of player (S) and box (B) 13 int playerRow = 0, playerCol = 0, boxRow = 0, boxCol = 0; 14 for (int i = 0; i < rows; ++i) { 15 for (int j = 0; j < cols; ++j) { 16 if (grid[i][j] == 'S') { 17 playerRow = i; 18 playerCol = j; 19 } else if (grid[i][j] == 'B') { 20 boxRow = i; 21 boxCol = j; 22 } 23 } 24 } 25 26 // Direction vectors for moving up, right, down, left 27 int[] directions = {-1, 0, 1, 0, -1}; 28 29 // BFS queue: stores [player position, box position, push count] 30 Deque<int[]> queue = new ArrayDeque<>(); 31 32 // Visited states: [player position][box position] 33 boolean[][] visited = new boolean[rows * cols][rows * cols]; 34 35 // Add initial state to queue 36 queue.offer(new int[] {encodePosition(playerRow, playerCol), 37 encodePosition(boxRow, boxCol), 0}); 38 visited[encodePosition(playerRow, playerCol)][encodePosition(boxRow, boxCol)] = true; 39 40 // BFS to find minimum pushes 41 while (!queue.isEmpty()) { 42 int[] current = queue.poll(); 43 int pushCount = current[2]; 44 45 // Decode box position 46 boxRow = current[1] / cols; 47 boxCol = current[1] % cols; 48 49 // Check if box reached target 50 if (grid[boxRow][boxCol] == 'T') { 51 return pushCount; 52 } 53 54 // Decode player position 55 playerRow = current[0] / cols; 56 playerCol = current[0] % cols; 57 58 // Try moving player in all four directions 59 for (int k = 0; k < 4; ++k) { 60 int newPlayerRow = playerRow + directions[k]; 61 int newPlayerCol = playerCol + directions[k + 1]; 62 63 // Check if new player position is valid 64 if (!isValidPosition(newPlayerRow, newPlayerCol)) { 65 continue; 66 } 67 68 // Check if player moves into box position (push the box) 69 if (newPlayerRow == boxRow && newPlayerCol == boxCol) { 70 // Calculate new box position after push 71 int newBoxRow = boxRow + directions[k]; 72 int newBoxCol = boxCol + directions[k + 1]; 73 74 // Check if box can be pushed to new position 75 if (!isValidPosition(newBoxRow, newBoxCol) || 76 visited[encodePosition(newPlayerRow, newPlayerCol)] 77 [encodePosition(newBoxRow, newBoxCol)]) { 78 continue; 79 } 80 81 // Mark new state as visited and add to queue (push occurred) 82 visited[encodePosition(newPlayerRow, newPlayerCol)] 83 [encodePosition(newBoxRow, newBoxCol)] = true; 84 queue.offer(new int[] {encodePosition(newPlayerRow, newPlayerCol), 85 encodePosition(newBoxRow, newBoxCol), 86 pushCount + 1}); 87 } 88 // Player moves without pushing box 89 else if (!visited[encodePosition(newPlayerRow, newPlayerCol)] 90 [encodePosition(boxRow, boxCol)]) { 91 // Mark state as visited and add to front of queue (no push) 92 visited[encodePosition(newPlayerRow, newPlayerCol)] 93 [encodePosition(boxRow, boxCol)] = true; 94 queue.offerFirst(new int[] {encodePosition(newPlayerRow, newPlayerCol), 95 encodePosition(boxRow, boxCol), 96 pushCount}); 97 } 98 } 99 } 100 101 // No solution found 102 return -1; 103 } 104 105 // Encode 2D position to 1D index 106 private int encodePosition(int row, int col) { 107 return row * cols + col; 108 } 109 110 // Check if position is within bounds and not a wall 111 private boolean isValidPosition(int row, int col) { 112 return row >= 0 && row < rows && col >= 0 && col < cols && grid[row][col] != '#'; 113 } 114} 115
1class Solution { 2public: 3 int minPushBox(vector<vector<char>>& grid) { 4 int rows = grid.size(), cols = grid[0].size(); 5 int playerRow, playerCol, boxRow, boxCol; 6 7 // Find initial positions of player 'S' and box 'B' 8 for (int i = 0; i < rows; ++i) { 9 for (int j = 0; j < cols; ++j) { 10 if (grid[i][j] == 'S') { 11 playerRow = i; 12 playerCol = j; 13 } else if (grid[i][j] == 'B') { 14 boxRow = i; 15 boxCol = j; 16 } 17 } 18 } 19 20 // Convert 2D coordinates to 1D index for state representation 21 auto coordToIndex = [&](int row, int col) { 22 return row * cols + col; 23 }; 24 25 // Check if a position is valid (within bounds and not a wall) 26 auto isValidPosition = [&](int row, int col) { 27 return row >= 0 && row < rows && col >= 0 && col < cols && grid[row][col] != '#'; 28 }; 29 30 // Direction vectors: up, right, down, left 31 int directions[5] = {-1, 0, 1, 0, -1}; 32 33 // BFS queue: stores (player position index, box position index, push count) 34 deque<tuple<int, int, int>> bfsQueue; 35 bfsQueue.emplace_back(coordToIndex(playerRow, playerCol), coordToIndex(boxRow, boxCol), 0); 36 37 // Visited states: [player position][box position] 38 bool visited[rows * cols][rows * cols]; 39 memset(visited, false, sizeof(visited)); 40 visited[coordToIndex(playerRow, playerCol)][coordToIndex(boxRow, boxCol)] = true; 41 42 // BFS with 0-1 BFS optimization (using deque) 43 while (!bfsQueue.empty()) { 44 auto [playerIndex, boxIndex, pushCount] = bfsQueue.front(); 45 bfsQueue.pop_front(); 46 47 // Convert indices back to 2D coordinates 48 playerRow = playerIndex / cols; 49 playerCol = playerIndex % cols; 50 boxRow = boxIndex / cols; 51 boxCol = boxIndex % cols; 52 53 // Check if box reached target 'T' 54 if (grid[boxRow][boxCol] == 'T') { 55 return pushCount; 56 } 57 58 // Try moving player in all four directions 59 for (int dir = 0; dir < 4; ++dir) { 60 int newPlayerRow = playerRow + directions[dir]; 61 int newPlayerCol = playerCol + directions[dir + 1]; 62 63 // Skip if new player position is invalid 64 if (!isValidPosition(newPlayerRow, newPlayerCol)) { 65 continue; 66 } 67 68 // Check if player moves to box position (pushing the box) 69 if (newPlayerRow == boxRow && newPlayerCol == boxCol) { 70 // Calculate new box position after push 71 int newBoxRow = boxRow + directions[dir]; 72 int newBoxCol = boxCol + directions[dir + 1]; 73 74 // Skip if new box position is invalid or state already visited 75 if (!isValidPosition(newBoxRow, newBoxCol) || 76 visited[coordToIndex(newPlayerRow, newPlayerCol)][coordToIndex(newBoxRow, newBoxCol)]) { 77 continue; 78 } 79 80 // Mark state as visited and add to queue (push increases count by 1) 81 visited[coordToIndex(newPlayerRow, newPlayerCol)][coordToIndex(newBoxRow, newBoxCol)] = true; 82 bfsQueue.emplace_back(coordToIndex(newPlayerRow, newPlayerCol), 83 coordToIndex(newBoxRow, newBoxCol), 84 pushCount + 1); 85 } 86 // Player moves without pushing box 87 else if (!visited[coordToIndex(newPlayerRow, newPlayerCol)][coordToIndex(boxRow, boxCol)]) { 88 // Mark state as visited and add to front of queue (no push, same count) 89 visited[coordToIndex(newPlayerRow, newPlayerCol)][coordToIndex(boxRow, boxCol)] = true; 90 bfsQueue.emplace_front(coordToIndex(newPlayerRow, newPlayerCol), 91 coordToIndex(boxRow, boxCol), 92 pushCount); 93 } 94 } 95 } 96 97 // No solution found 98 return -1; 99 } 100}; 101
1/** 2 * Finds the minimum number of pushes required to move a box to the target position 3 * Uses BFS with 0-1 BFS optimization (deque for different weight edges) 4 * 5 * @param grid - 2D grid where: 6 * 'S' = starting position of player 7 * 'B' = starting position of box 8 * 'T' = target position for box 9 * '#' = wall 10 * '.' = empty space 11 * @returns Minimum number of pushes, or -1 if impossible 12 */ 13function minPushBox(grid: string[][]): number { 14 const rows = grid.length; 15 const cols = grid[0].length; 16 17 // Find initial positions of player (S) and box (B) 18 let playerRow = 0, playerCol = 0, boxRow = 0, boxCol = 0; 19 for (let i = 0; i < rows; i++) { 20 for (let j = 0; j < cols; j++) { 21 if (grid[i][j] === 'S') { 22 playerRow = i; 23 playerCol = j; 24 } else if (grid[i][j] === 'B') { 25 boxRow = i; 26 boxCol = j; 27 } 28 } 29 } 30 31 // Convert 2D coordinates to 1D index for efficient storage 32 const coordinateToIndex = (row: number, col: number): number => row * cols + col; 33 34 // Check if a position is valid (within bounds and not a wall) 35 const isValidPosition = (row: number, col: number): boolean => 36 row >= 0 && row < rows && col >= 0 && col < cols && grid[row][col] !== '#'; 37 38 // BFS queue: [playerPosition, boxPosition, pushCount] 39 const queue: Deque<[number, number, number]> = new Deque(); 40 41 // Track visited states: visited[playerPosition][boxPosition] 42 const visited: boolean[][] = Array(rows * cols) 43 .fill(0) 44 .map(() => Array(rows * cols).fill(false)); 45 46 // Initialize BFS 47 queue.push([ 48 coordinateToIndex(playerRow, playerCol), 49 coordinateToIndex(boxRow, boxCol), 50 0 51 ]); 52 visited[coordinateToIndex(playerRow, playerCol)][coordinateToIndex(boxRow, boxCol)] = true; 53 54 // Direction vectors: up, right, down, left 55 const directions: number[] = [-1, 0, 1, 0, -1]; 56 57 // BFS traversal 58 while (queue.size() > 0) { 59 const [playerPos, boxPos, pushCount] = queue.shift()!; 60 61 // Decode positions from indices 62 const currentPlayerRow = Math.floor(playerPos / cols); 63 const currentPlayerCol = playerPos % cols; 64 const currentBoxRow = Math.floor(boxPos / cols); 65 const currentBoxCol = boxPos % cols; 66 67 // Check if box reached target 68 if (grid[currentBoxRow][currentBoxCol] === 'T') { 69 return pushCount; 70 } 71 72 // Try moving player in all four directions 73 for (let dir = 0; dir < 4; dir++) { 74 const nextPlayerRow = currentPlayerRow + directions[dir]; 75 const nextPlayerCol = currentPlayerCol + directions[dir + 1]; 76 77 // Skip invalid positions 78 if (!isValidPosition(nextPlayerRow, nextPlayerCol)) { 79 continue; 80 } 81 82 // Check if player moves to box position (pushing the box) 83 if (nextPlayerRow === currentBoxRow && nextPlayerCol === currentBoxCol) { 84 // Calculate new box position after push 85 const nextBoxRow = currentBoxRow + directions[dir]; 86 const nextBoxCol = currentBoxCol + directions[dir + 1]; 87 88 // Check if box can be pushed to new position 89 if (!isValidPosition(nextBoxRow, nextBoxCol) || 90 visited[coordinateToIndex(nextPlayerRow, nextPlayerCol)][coordinateToIndex(nextBoxRow, nextBoxCol)]) { 91 continue; 92 } 93 94 // Mark state as visited and add to queue (push operation costs 1) 95 visited[coordinateToIndex(nextPlayerRow, nextPlayerCol)][coordinateToIndex(nextBoxRow, nextBoxCol)] = true; 96 queue.push([ 97 coordinateToIndex(nextPlayerRow, nextPlayerCol), 98 coordinateToIndex(nextBoxRow, nextBoxCol), 99 pushCount + 1 100 ]); 101 } else if (!visited[coordinateToIndex(nextPlayerRow, nextPlayerCol)][coordinateToIndex(currentBoxRow, currentBoxCol)]) { 102 // Player moves without pushing box (no cost, add to front of queue) 103 visited[coordinateToIndex(nextPlayerRow, nextPlayerCol)][coordinateToIndex(currentBoxRow, currentBoxCol)] = true; 104 queue.unshift([ 105 coordinateToIndex(nextPlayerRow, nextPlayerCol), 106 coordinateToIndex(currentBoxRow, currentBoxCol), 107 pushCount 108 ]); 109 } 110 } 111 } 112 113 // No solution found 114 return -1; 115} 116 117/* Double-ended queue implementation using circular buffers */ 118 119/** 120 * Circular buffer node for deque implementation 121 */ 122class CircularDeque<T> { 123 prev: CircularDeque<T> | null; 124 next: CircularDeque<T> | null; 125 begin: number; 126 end: number; 127 empty: boolean; 128 data: T[]; 129 130 constructor(capacity: number) { 131 this.prev = this.next = null; 132 this.begin = this.end = 0; 133 this.empty = true; 134 this.data = Array(capacity); 135 } 136 137 isFull(): boolean { 138 return this.end === this.begin && !this.empty; 139 } 140 141 isEmpty(): boolean { 142 return this.empty; 143 } 144 145 push(value: T): boolean { 146 if (this.isFull()) return false; 147 this.empty = false; 148 this.data[this.end] = value; 149 this.end = (this.end + 1) % this.data.length; 150 return true; 151 } 152 153 front(): T | undefined { 154 return this.isEmpty() ? undefined : this.data[this.begin]; 155 } 156 157 back(): T | undefined { 158 return this.isEmpty() ? undefined : this.data[this.end - 1]; 159 } 160 161 pop(): T | undefined { 162 if (this.isEmpty()) return undefined; 163 const value = this.data[this.end - 1]; 164 this.end = (this.end - 1) % this.data.length; 165 if (this.end < 0) this.end += this.data.length; 166 if (this.end === this.begin) this.empty = true; 167 return value; 168 } 169 170 unshift(value: T): boolean { 171 if (this.isFull()) return false; 172 this.empty = false; 173 this.begin = (this.begin - 1) % this.data.length; 174 if (this.begin < 0) this.begin += this.data.length; 175 this.data[this.begin] = value; 176 return true; 177 } 178 179 shift(): T | undefined { 180 if (this.isEmpty()) return undefined; 181 const value = this.data[this.begin]; 182 this.begin = (this.begin + 1) % this.data.length; 183 if (this.end === this.begin) this.empty = true; 184 return value; 185 } 186 187 *values(): Generator<T, void, undefined> { 188 if (this.isEmpty()) return undefined; 189 let index = this.begin; 190 do { 191 yield this.data[index]; 192 index = (index + 1) % this.data.length; 193 } while (index !== this.end); 194 } 195} 196 197/** 198 * Double-ended queue implementation using linked list of circular buffers 199 */ 200class Deque<T> { 201 head: CircularDeque<T>; 202 tail: CircularDeque<T>; 203 _size: number; 204 205 constructor(collection: T[] = []) { 206 this.head = new CircularDeque<T>(128); 207 this.tail = new CircularDeque<T>(128); 208 this.tail.empty = this.head.empty = false; 209 this.tail.prev = this.head; 210 this.head.next = this.tail; 211 this._size = 0; 212 for (const item of collection) this.push(item); 213 } 214 215 size(): number { 216 return this._size; 217 } 218 219 push(value: T): void { 220 let lastNode = this.tail.prev!; 221 if (lastNode.isFull()) { 222 // Create new node when current is full 223 const newNode = new CircularDeque<T>(128); 224 225 this.tail.prev = newNode; 226 newNode.next = this.tail; 227 228 lastNode.next = newNode; 229 newNode.prev = lastNode; 230 231 lastNode = newNode; 232 } 233 lastNode.push(value); 234 this._size++; 235 } 236 237 back(): T | undefined { 238 if (this._size === 0) return; 239 return this.tail.prev!.back(); 240 } 241 242 pop(): T | undefined { 243 if (this.head.next === this.tail) return undefined; 244 const lastNode = this.tail.prev!; 245 const value = lastNode.pop(); 246 if (lastNode.isEmpty()) { 247 // Remove empty node 248 this.tail.prev = lastNode.prev; 249 lastNode.prev!.next = this.tail; 250 } 251 this._size--; 252 return value; 253 } 254 255 unshift(value: T): void { 256 let firstNode = this.head.next!; 257 if (firstNode.isFull()) { 258 // Create new node when current is full 259 const newNode = new CircularDeque<T>(128); 260 261 this.head.next = newNode; 262 newNode.prev = this.head; 263 264 newNode.next = firstNode; 265 firstNode.prev = newNode; 266 267 firstNode = newNode; 268 } 269 firstNode.unshift(value); 270 this._size++; 271 } 272 273 shift(): T | undefined { 274 if (this.head.next === this.tail) return undefined; 275 const firstNode = this.head.next!; 276 const value = firstNode.shift(); 277 if (firstNode.isEmpty()) { 278 // Remove empty node 279 this.head.next = firstNode.next; 280 firstNode.next!.prev = this.head; 281 } 282 this._size--; 283 return value; 284 } 285 286 front(): T | undefined { 287 if (this._size === 0) return undefined; 288 return this.head.next!.front(); 289 } 290 291 *values(): Generator<T, void, undefined> { 292 let currentNode = this.head.next!; 293 while (currentNode !== this.tail) { 294 for (const value of currentNode.values()) yield value; 295 currentNode = currentNode.next!; 296 } 297 } 298} 299

Solution Approach

The implementation uses BFS with a double-ended queue to find the minimum number of pushes. Let's walk through the key components:

State Representation:

  • We define a function f(i, j) = i * n + j to map 2D coordinates to a 1D state number
  • Each state is represented as (f(player_position), f(box_position), push_count)
  • This allows us to use a 2D visited array: vis[player_state][box_state]

Initialization:

  1. First, traverse the grid to find initial positions:
    • Player position: (si, sj) where grid[i][j] = 'S'
    • Box position: (bi, bj) where grid[i][j] = 'B'
  2. Initialize a deque q with the starting state: (f(si, sj), f(bi, bj), 0)
  3. Mark the initial state as visited in vis

BFS Process: For each state (s, b, d) dequeued from q:

  1. Convert state numbers back to coordinates:

    • Box position: bi = b // n, bj = b % n
    • Player position: si = s // n, sj = s % n

  2. Check termination: If grid[bi][bj] = 'T', return d (minimum pushes found)

  3. Try all four directions for player movement:

    • Calculate new player position: (sx, sy) = (si + a, sj + b)
    • Use check() function to verify it's a valid position (within bounds and not a wall)

  4. Handle two cases:

    Case 1: Player moves into box position (sx, sy) == (bi, bj):

    • This means the player pushes the box
    • Calculate new box position: (bx, by) = (bi + a, bj + b)
    • If the new box position is valid and this state hasn't been visited:
      • Mark vis[f(sx, sy)][f(bx, by)] as visited
      • Append (f(sx, sy), f(bx, by), d + 1) to the back of queue (push occurred, cost +1)

    Case 2: Player moves to empty cell:

    • This is just player repositioning (no push)
    • If state vis[f(sx, sy)][f(bi, bj)] hasn't been visited:
      • Mark it as visited
      • Append (f(sx, sy), f(bi, bj), d) to the front of queue (no push, cost +0)

Key Optimization - 0-1 BFS:

  • States with no push (cost 0) are added to the front using appendleft()
  • States with a push (cost 1) are added to the back using append()
  • This ensures we explore all possible player repositioning before considering another push, effectively processing states level by level based on push count

Termination:

  • If the queue becomes empty without finding the target, return -1 (no solution exists)

The algorithm guarantees finding the minimum number of pushes because BFS explores states in order of increasing push count, and the 0-1 BFS optimization ensures efficient exploration of the state space.

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a small example to illustrate the solution approach:

Grid: # # # # # # T . . # # . B . # # . S . # # # # # #

Initial Setup:

  • Player starts at S position: (3, 2)
  • Box starts at B position: (2, 2)
  • Target is at T position: (1, 1)
  • Grid dimensions: m=5, n=5

Using our state encoding function f(i,j) = i*5 + j:

  • Initial player state: f(3,2) = 17
  • Initial box state: f(2,2) = 12

BFS Process:

Step 1: Initialize

  • Queue: [(17, 12, 0)] (player at 17, box at 12, 0 pushes)
  • Mark vis[17][12] = true

Step 2: Process state (17, 12, 0)

  • Player at (3,2), Box at (2,2)
  • Try all 4 directions:
    • Up: Player moves to (2,2) - this is the box position!
      • Box gets pushed to (1,2) ✓ valid empty cell
      • Add (12, 7, 1) to back of queue (push occurred)
    • Down: Player moves to (4,2) - wall #, invalid
    • Left: Player moves to (3,1) - empty cell .
      • Add (16, 12, 0) to front of queue (just repositioning)
    • Right: Player moves to (3,3) - empty cell .
      • Add (18, 12, 0) to front of queue (just repositioning)

Queue now: [(16, 12, 0), (18, 12, 0), (12, 7, 1)]

Step 3: Process state (16, 12, 0)

  • Player at (3,1), Box at (2,2)
  • Try all 4 directions:
    • Up: Player to (2,1) - empty cell, add (11, 12, 0) to front
    • Other moves either hit walls or revisit states

Step 4: Process state (18, 12, 0)

  • Player at (3,3), Box at (2,2)
  • Similar exploration of moves...

Step 5: Process state (11, 12, 0)

  • Player at (2,1), Box at (2,2)
  • Right: Player moves to (2,2) - box position!
    • Box pushed to (2,3) ✓ valid
    • Add (12, 13, 1) to back

Step 6: Eventually process state (12, 7, 1)

  • Player at (2,2), Box at (1,2)
  • Left: Player moves to (2,1) - empty cell
    • Add (11, 7, 1) to front (no push)

Step 7: Process state (11, 7, 1)

  • Player at (2,1), Box at (1,2)
  • Up: Player moves to (1,1) - empty cell (the target!)
    • Add (6, 7, 1) to front
  • Right: Player moves to (2,2) - empty cell
    • Add (12, 7, 1) to front (already visited, skip)

Step 8: Process state (6, 7, 1)

  • Player at (1,1), Box at (1,2)
  • Right: Player moves to (1,2) - box position!
    • Box pushed to (1,3) ✓ valid
    • Add (7, 8, 2) to back

Continue until...

Step N: Process state (7, 6, 2)

  • Player at (1,2), Box at (1,1)
  • Check: Box position (1,1) is the target T!
  • Return 2 (minimum pushes needed)

Key Observations:

  1. The 0-1 BFS ensures we explore all repositioning moves (cost 0) before considering additional pushes
  2. States with the same push count are processed together
  3. The first time the box reaches the target, we've found the minimum number of pushes
  4. The player can take many paths to get into position, but only actual pushes count toward our answer

Time and Space Complexity

Time Complexity: O(m^2 × n^2)

The algorithm uses BFS to explore different states where each state consists of the shopkeeper's position and the box's position. Since both the shopkeeper and the box can be at any valid cell in the grid:

  • Total possible positions for the shopkeeper: m × n
  • Total possible positions for the box: m × n
  • Total possible states: (m × n) × (m × n) = m^2 × n^2

Each state is visited at most once due to the visited array vis[f(si, sj)][f(bi, bj)]. For each state, we explore 4 directions (constant time operations), so the overall time complexity is O(m^2 × n^2).

Space Complexity: O(m^2 × n^2)

The space complexity is dominated by:

  • The visited array vis: A 2D boolean array of size (m × n) × (m × n), which stores whether each combination of shopkeeper position and box position has been visited. This requires O(m^2 × n^2) space.
  • The BFS queue q: In the worst case, it could contain all possible states, which is O(m^2 × n^2).
  • Other variables like the grid itself and auxiliary variables use O(m × n) space, which is negligible compared to the visited array.

Therefore, the overall space complexity is O(m^2 × n^2).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect State Representation - Not Tracking Player Position

Pitfall: A common mistake is to only track the box position in the BFS state, thinking that only the box's location matters for the minimum pushes.

# WRONG: Only tracking box position queue = deque([(box_row, box_col, 0)]) visited = set() visited.add((box_row, box_col))

Why it fails: The player's position is crucial because:

  • To push the box in a certain direction, the player must be on the opposite side
  • The same box position with different player positions represents different game states
  • Without tracking player position, you can't determine which pushes are actually possible

Solution: Always track both player and box positions as a combined state:

# CORRECT: Track both positions queue = deque([(player_pos, box_pos, pushes)]) visited = [[False] * (rows * cols) for _ in range(rows * cols)] visited[player_pos][box_pos] = True

2. Using Regular BFS Instead of 0-1 BFS

Pitfall: Treating all moves equally in the queue, which can lead to suboptimal solutions:

# WRONG: All moves added to back of queue if person_moves_to_box_position:  queue.append((new_player_pos, new_box_pos, pushes + 1)) else:  queue.append((new_player_pos, box_pos, pushes)) # Wrong!

Why it fails:

  • Player repositioning (cost 0) should be explored before additional pushes (cost 1)
  • Regular BFS might find a path with more pushes first

Solution: Use 0-1 BFS pattern - add cost-0 moves to front, cost-1 moves to back:

# CORRECT: 0-1 BFS if person_moves_to_box_position:  queue.append((new_player_pos, new_box_pos, pushes + 1)) # Cost 1: to back else:  queue.appendleft((new_player_pos, box_pos, pushes)) # Cost 0: to front

3. Not Validating Box Push Destination

Pitfall: Forgetting to check if the box can actually be pushed to the new position:

# WRONG: Only checking if player can move if is_valid_cell(next_person_row, next_person_col):  if next_person_row == box_row and next_person_col == box_col:  # Forgot to check if box can move to its new position!  new_box_row = box_row + directions[i]  new_box_col = box_col + directions[i + 1]  queue.append(...)

Solution: Always validate both the player's move AND the box's new position when pushing:

# CORRECT: Check both player and box destinations if is_valid_cell(next_person_row, next_person_col):  if next_person_row == box_row and next_person_col == box_col:  new_box_row = box_row + directions[i]  new_box_col = box_col + directions[i + 1]  if not is_valid_cell(new_box_row, new_box_col):  continue # Can't push box there  # Now safe to add to queue

4. Inefficient State Encoding

Pitfall: Using tuples or strings for state representation in visited set:

# INEFFICIENT: Using tuples in set visited = set() visited.add((person_row, person_col, box_row, box_col))

Why it's problematic:

  • Set operations with tuples can be slower for large grids
  • Memory overhead from storing multiple integers per state

Solution: Use integer encoding and 2D array for O(1) lookups:

# EFFICIENT: Integer encoding with 2D array def encode_position(row, col):  return row * cols + col  visited = [[False] * (rows * cols) for _ in range(rows * cols)] visited[encode_position(person_row, person_col)][encode_position(box_row, box_col)] = True
Loading...
Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?

Recommended Readings

BFS Fundamentals

https assets algo monster cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell Breadth First Search BFS

Heap Fundamentals

https assets algo monster cover_photos heap svg Priority Queue and Heap What is the relationship between priority queue and heap Priority Queue is an Abstract Data Type and Heap is the concrete data structure we use to implement a priority queue Priority Queue A priority queue is a data structure

Coding Interview Patterns: The Smart, Data-Driven Way to Prepare for Tech Interviews

Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More