Skip to main content
Talentd

Minimum Moves to Reach Target with Rotations - Solution & Explanation

HardArrayBreadth-First SearchMatrix29 min readAsked at: Kakao
Practice this problem

Problem Statement

In an n*n grid, there is a snake that spans 2 cells and starts moving from the top left corner at (0, 0) and (0, 1). The grid has empty cells represented by zeros and blocked cells represented by ones. The snake wants to reach the lower right corner at (n-1, n-2) and (n-1, n-1).

In one move the snake can:

  • Move one cell to the right if there are no blocked cells there. This move keeps the horizontal/vertical position of the snake as it is.
  • Move down one cell if there are no blocked cells there. This move keeps the horizontal/vertical position of the snake as it is.
  • Rotate clockwise if it's in a horizontal position and the two cells under it are both empty. In that case the snake moves from (r, c) and (r, c+1) to (r, c) and (r+1, c).
  • Rotate counterclockwise if it's in a vertical position and the two cells to its right are both empty. In that case the snake moves from (r, c) and (r+1, c) to (r, c) and (r, c+1).

Return the minimum number of moves to reach the target.

If there is no way to reach the target, return -1.

 

Example 1:

Input: grid = [[0,0,0,0,0,1],
               [1,1,0,0,1,0],
               [0,0,0,0,1,1],
               [0,0,1,0,1,0],
               [0,1,1,0,0,0],
               [0,1,1,0,0,0]]
Output: 11
Explanation:
One possible solution is [right, right, rotate clockwise, right, down, down, down, down, rotate counterclockwise, right, down].

Example 2:

Input: grid = [[0,0,1,1,1,1],
               [0,0,0,0,1,1],
               [1,1,0,0,0,1],
               [1,1,1,0,0,1],
               [1,1,1,0,0,1],
               [1,1,1,0,0,0]]
Output: 9

 

Constraints:

  • 2 <= n <= 100
  • 0 <= grid[i][j] <= 1
  • It is guaranteed that the snake starts at empty cells.

Approach Overview

Problem Overview: You control a 2‑cell snake inside an n x n grid. The snake can move right, move down, or rotate between horizontal and vertical positions if the surrounding cells are empty. The goal is to reach the bottom‑right target configuration using the minimum number of moves.

Approach 1: State Graph BFS (O(n2) time, O(n2) space)

The grid can be treated as a graph where each node represents the snake's state: the head position and its orientation (horizontal or vertical). From each state, generate valid transitions: move right, move down, or rotate if the required cells are free. Use Breadth-First Search to explore states level by level, since BFS guarantees the first time you reach the target configuration is the minimum number of moves. Maintain a visited set keyed by (row, col, orientation) to avoid revisiting the same configuration. The total number of states is at most 2 * n * n, giving O(n2) time and O(n2) space.

Approach 2: BFS with State Encoding and Transition Pruning (O(n2) time, O(n2) space)

This version keeps the same BFS idea but encodes the snake using the top‑left cell of the segment plus orientation. That representation avoids storing both cells explicitly and simplifies transition checks. When horizontal, you attempt: right shift, down shift, and clockwise rotation. When vertical, you attempt: down shift, right shift, and counter‑clockwise rotation. Each transition checks the required cells in the matrix to ensure they are within bounds and empty. Using a compact visited structure such as a boolean 3D array improves cache locality and keeps the BFS fast even when the grid is large.

The algorithm relies heavily on graph traversal concepts from Breadth-First Search and grid state modeling using arrays. Once the state representation is correct, transitions become straightforward conditional checks.

Recommended for interviews: The BFS state‑graph solution is the expected approach. Interviewers want to see how you model the snake configuration as a graph node and generate valid transitions. A naive exploration without visited tracking quickly explodes in states, while the BFS with state encoding shows strong problem‑modeling and graph traversal skills.

Approach 1: Breadth-First Search

Breadth-First Search (BFS) is a powerful technique for such grid-based traversal problems. The idea is to explore all potential moves that the snake can make from its current position and orientation, tracking the number of moves. Each state of the snake (defined by its head position and orientation) is enqueued with its move count. This ensures that the shortest path to the goal is found first, making BFS ideal for finding the minimum number of moves.

This solution uses BFS. The queue holds tuples representing the head and tail of the snake along with the current number of moves. For each state, potential moves are checked (right, down, and rotations), and new states are added to the queue if they haven't been visited yet.

Code

PythonC++JavaJavaScript

Python

C++

Java

JavaScript

Complexity

Time Complexity: O(n^3), because in the worst case, for each of n^2 possible states on the n*n grid, we process it in multiple directions.
Space Complexity: O(n^3), because of the growth in the queue and visited data structures.

Try this approach in the editor →

Approach 2: BFS

The problem asks for the minimum number of moves for the snake to reach the target position from the starting position. We consider using Breadth-First Search (BFS) to solve it.

We define the following data structures or variables:

  • Queue q: Stores the current position of the snake. Each position is a tuple (a, b), where a represents the tail position of the snake, and b represents the head position of the snake. Initially, we add the position (0, 1) to the queue q. If we flatten the 2D maze into a 1D array, then the position (0, 1) represents the two cells with indices 0 and 1 in the 1D array.
  • Target position target: The value is fixed at (n^2 - 2, n^2 - 1), which is the last two cells of the last row of the 2D maze.
  • Array or set vis: Stores whether the current position state of the snake has been visited. Each state is a tuple (a, status), where a represents the tail position of the snake, and status represents the current state of the snake, with values of 0 or 1, representing the horizontal and vertical states of the snake, respectively. Initially, add the state of the starting position (0, 1) to the set vis.
  • Answer variable ans: Stores the number of moves for the snake to reach the target position from the starting position. Initially, it is 0.

We use BFS to solve it. Each time we take a position from the queue q, we check whether the position is the target position target. If it is, we directly return the answer variable ans. If not, we add the next possible position of this position to the queue q and add this position to vis. Note that the next position could be the horizontal or vertical state of the snake, and we need to judge them separately (see the following code comments). At the end of each round of search, the answer variable ans increments by 1.

Finally, if the queue q is empty, it means that it is impossible to reach the target position from the starting position, so return -1.

The time complexity is O(n^2), and the space complexity is O(n^2). Here, n is the number of rows or columns of the 2D maze.

Code

PythonJavaC++GoTypeScriptJavaScript

Python

Java

C++

Go

TypeScript

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Breadth-First Search

Time Complexity: O(n^3), because in the worst case, for each of n^2 possible states on the n*n grid, we process it in multiple directions.
Space Complexity: O(n^3), because of the growth in the queue and visited data structures.

BFS—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Naive BFS without state pruningExponentialHighConceptual understanding of transitions; not practical for large grids
BFS with (row, col, orientation) stateO(n^2)O(n^2)General optimal solution for finding minimum moves in the grid
BFS with compact state encodingO(n^2)O(n^2)Production or interview code where efficient state checks and clean transitions matter

Video Solution

Leetcode 1210 Minimum Moves to Reach Target with Rotations • Coder on A Farm • 167 views views

Watch 4 more video solutions →

Frequently Asked Questions

Is Minimum Moves to Reach Target with Rotations easy or hard?
Minimum Moves to Reach Target with Rotations is classified as a Hard problem on LeetCode. The challenge comes from correctly modeling the snake state, handling rotation constraints, and generating valid BFS transitions without missing edge cases.
Minimum Moves to Reach Target with Rotations Python/Java solution
Implement BFS using a queue where each entry contains the snake position and orientation. For Python, use collections.deque and a set or boolean visited array. Java implementations typically use a Queue with a boolean[][][] visited structure for fast lookups.
How to solve Minimum Moves to Reach Target with Rotations in O(n^2)?
Model each snake configuration as a graph node defined by (row, column, orientation). Use Breadth-First Search to explore valid transitions such as moving right, moving down, or rotating when adjacent cells are empty. Track visited states to prevent revisiting configurations.
What is the best approach for Minimum Moves to Reach Target with Rotations?
The best approach is Breadth-First Search (BFS) over snake states. Each state stores the snake's position and orientation (horizontal or vertical). BFS explores all valid moves level by level, guaranteeing the first time the target configuration is reached is the minimum number of moves.
Is Minimum Moves to Reach Target with Rotations asked at Google/Amazon/Meta?
Grid BFS and state‑transition problems similar to this appear in interviews at companies like Google, Amazon, and Meta. The problem tests graph modeling, BFS traversal, and careful handling of state transitions in matrix problems.
What data structure is used in Minimum Moves to Reach Target with Rotations?
The core data structure is a queue used in Breadth-First Search. A visited set or 3D boolean array tracks explored states defined by grid position and snake orientation, preventing repeated exploration of the same configuration.
What is the time complexity of Minimum Moves to Reach Target with Rotations?
The optimal BFS solution runs in O(n^2) time and O(n^2) space for an n x n grid. There are at most 2 * n * n possible snake states because each cell can be the head of either a horizontal or vertical configuration.

Ready to solve this problem?

Practice Minimum Moves to Reach Target with Rotations with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays