Facebook Pixel

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 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 3-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

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

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
Discover Your Strengths and Weaknesses: Take Our 3-Minute Quiz to Tailor Your Study Plan:

What are the most two important steps in writing a depth first search function? (Select 2)

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