Minimum Moves to Move a Box to Their Target Location - Video Solutions
Hard Leetcode problem Move A Box To Target Location (with implementation)
Minimum Moves to Move a Box to Their Target Location - Video Solution
Watch 8 video solutions for Minimum Moves to Move a Box to Their Target Location, a hard level problem involving Array, Breadth-First Search, Heap (Priority Queue). This walkthrough by Errichto Algorithms has 38,576 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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 ingridif 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 thegrid. - 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. 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 <= 20gridcontains only characters'.','#','S','T', or'B'.- There is only one character
'S','B', and'T'in thegrid.
Approach Overview
Problem Overview: You are given a grid with walls, a player, a box, and a target. The player can move freely but can only push (not pull) the box. The task is to compute the minimum number of pushes required to move the box to the target cell.
Approach 1: Breadth-First Search with State Tracking (O((mn)^2) time, O((mn)^2) space)
Model the puzzle as a state search where each state contains both the box position and the player position. The BFS queue prioritizes states by the number of pushes, not simple movements. When the player moves behind the box and pushes it, a new state is created with the updated box location. Before each push, run a reachability check to confirm the player can walk to the required pushing position without crossing the box or walls. A visited set like (boxRow, boxCol, playerRow, playerCol) prevents revisiting states. This approach relies heavily on Breadth-First Search across a matrix grid to guarantee the minimum pushes.
Approach 2: A* Search for Optimal Pushes (O((mn)^2 log(mn)) time, O((mn)^2) space)
A* improves the search by guiding exploration toward the target using a heuristic. Each state still contains the box and player coordinates, but states are stored in a priority queue ordered by f = pushes + heuristic. A common heuristic is the Manhattan distance from the box to the target. This does not overestimate the required pushes, so the search remains optimal. Instead of expanding states purely level by level like BFS, A* prioritizes promising states and typically explores fewer configurations. The implementation uses a priority queue to efficiently select the next state with the smallest estimated cost.
Recommended for interviews: BFS with state tracking is the most common expected solution. It clearly models the puzzle as a graph search and guarantees the minimum number of pushes. Interviewers usually want to see correct state representation and reachability checks. Mentioning A* as an optimization shows deeper search algorithm knowledge and strong problem-solving maturity.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| BFS with State Tracking | O((mn)^2) | O((mn)^2) | Standard solution for interviews. Guarantees minimum pushes and easier to reason about. |
| A* Search with Priority Queue | O((mn)^2 log(mn)) | O((mn)^2) | When optimizing search exploration. Heuristic reduces explored states in large grids. |