Minimum Queen Moves to Reach Target solution and explanation
The problem
There is an 8 x 8 empty chessboard with 1-indexed rows and columns.
You are given an array source = [sr, sc] representing the starting position of a queen, and an array target = [tr, tc] representing the target position.
In one move, the queen travels one or more squares along a single row, column, or diagonal, staying within the board.
Return the minimum number of moves for the queen to land exactly on target.
Example 1:
Input: source = [8,1], target = [1,8]
Output: 1
Explanation:
A single diagonal move takes the queen straight from (8, 1) to (1, 8).
Example 2:
Input: source = [4,2], target = [1,3]
Output: 2
Explanation:
The queen moves from (4, 2) to (4, 3), then from (4, 3) to (1, 3), reaching the target in 2 moves.
Example 3:
Input: source = [1,1], target = [1,1]
Output: 0
Explanation:
The queen is already at the target position, so no moves are needed.
Constraints:
source == [sr, sc]target == [tr, tc]1 <= sr, sc, tr, tc <= 8
Approach overview
Problem Overview: A queen starts at (0,0) on an unbounded board. Given a target cell (x, y), return the minimum number of moves needed to reach it. A queen moves any number of squares along a row, column, or diagonal in one move.
Approach 1: Breadth-First Search on a Bounded Grid (O(N^2) time, O(N^2) space)
Model each cell as a node and each legal queen move as an edge. Run BFS from (0,0) and stop when you reach the target. For each popped cell, expand in all 8 directions and push every reachable cell that you have not visited. This is correct, and it is the approach you reach for first if you want to avoid geometry. The cost is that you must bound the grid, and every cell in that bound becomes a node. For a board of side N, that is N^2 nodes and up to N^2 visited entries, which gets slow fast.
Approach 2: Case Analysis (O(1) time, O(1) space)
Look at the target's position relative to the origin. Only three things matter. If the target is (0,0), the answer is 0. If the target lies on the same row (y = 0), same column (x = 0), or same diagonal (|x| = |y|), a single queen move reaches it, so the answer is 1. Every other cell needs exactly 2 moves. You can always go to an intermediate cell that shares a line with both the origin and the target, so 2 is the upper bound, and the single-move cases are the only way to get below it. This runs in constant time because you do three comparisons and return.
Recommended for interviews: Start by describing the BFS approach so the interviewer sees you understand the move model. Then switch to case analysis and justify why the answer is never larger than 2. The BFS shows you can model the problem. The case analysis shows you can reduce it to the structure that matters, and that is what interviewers score for. Both topics appear under array and math problems on this platform, and this problem is a good example of why math-based reasoning often beats simulation.
Solution
Thinking
The board is only
8times 8, so a BFS from the source also finds the shortest path. One queen move reaches any square on the same row, column, or diagonal, and the distance can only be0,1, or2.When the two squares differ, move along the row to
(s_r, t_c)and then along the column to(t_r, t_c). Two moves always arrive, and the board is empty.If that intermediate square coincides with either end, the source and the target already share a row or a column, so one move is enough. It remains only to test equality, a shared row or column, and a shared diagonal.
The answer is 0 when (s_r, s_c) and (t_r, t_c) are the same square.
A queen moves any number of squares along one row, one column, or one diagonal. The answer is 1 when s_r=t_r, s_c=t_c, or |s_r-t_r|=|s_c-t_c|.
Every remaining pair takes two moves. Go from (s_r, s_c) to (s_r, t_c), then from (s_r, t_c) to (t_r, t_c). The squares share neither a row nor a column, so the intermediate square differs from both ends. The board is empty, and both moves are legal. The answer is 2.
The time complexity is O(1) and the space complexity is O(1).
class Solution:
def minQueenMoves(self, source: list[int], target: list[int]) -> int:
sr, sc = source
tr, tc = target
if sr == tr and sc == tc:
return 0
if sr == tr or sc == tc or abs(sr - tr) == abs(sc - tc):
return 1
return 2class Solution {
public int minQueenMoves(int[] source, int[] target) {
int sr = source[0], sc = source[1];
int tr = target[0], tc = target[1];
if (sr == tr && sc == tc) {
return 0;
}
if (sr == tr || sc == tc || Math.abs(sr - tr) == Math.abs(sc - tc)) {
return 1;
}
return 2;
}
}class Solution {
public:
int minQueenMoves(vector<int>& source, vector<int>& target) {
int sr = source[0], sc = source[1];
int tr = target[0], tc = target[1];
if (sr == tr && sc == tc) {
return 0;
}
if (sr == tr || sc == tc || abs(sr - tr) == abs(sc - tc)) {
return 1;
}
return 2;
}
};function minQueenMoves(source: number[], target: number[]): number {
const [sr, sc] = source;
const [tr, tc] = target;
if (sr === tr && sc === tc) {
return 0;
}
if (sr === tr || sc === tc || Math.abs(sr - tr) === Math.abs(sc - tc)) {
return 1;
}
return 2;
}func minQueenMoves(source []int, target []int) int {
sr, sc := source[0], source[1]
tr, tc := target[0], target[1]
if sr == tr && sc == tc {
return 0
}
if sr == tr || sc == tc || abs(sr-tr) == abs(sc-tc) {
return 1
}
return 2
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| BFS on bounded grid | O(N^2) | O(N^2) | Useful for verifying the move model or when obstacles are added |
| Case Analysis | O(1) | O(1) | Always for the standard unobstructed board |
Frequently asked questions
Is Minimum Queen Moves to Reach Target easy or hard?
It is an easy problem. The core insight is recognizing that any target is reachable in at most two queen moves, and that only lines through the origin give a single move. Once you see that, the code is three conditionals.
Minimum Queen Moves to Reach Target Python solution?
In Python, read the target coordinates, return 0 if both are zero, and return 1 if x == 0 or y == 0 or abs(x) == abs(y). Otherwise return 2. The function runs in O(1) time and O(1) space.
How to solve Minimum Queen Moves to Reach Target in O(1)?
Check the target's position against the origin. Return 0 if it is (0,0). Return 1 if x equals 0, y equals 0, or the absolute value of x equals the absolute value of y. Return 2 for all other cells, since one intermediate cell on a shared line always connects the two points.
What is the best approach for Minimum Queen Moves to Reach Target?
Case analysis is the best approach. Check whether the target is the origin (0 moves), lies on the same row, column, or diagonal as the origin (1 move), or otherwise (2 moves). It runs in O(1) time and O(1) space.
What data structure is used in Minimum Queen Moves to Reach Target?
The optimal solution uses no data structure beyond a few integer variables. The problem is solved with arithmetic checks on the coordinates. The BFS alternative uses a queue and a visited set, but it is not needed for the standard board.
What is the time complexity of Minimum Queen Moves to Reach Target?
The optimal solution runs in O(1) time because it performs a fixed number of comparisons regardless of the target's coordinates. A BFS over a bounded grid would take O(N^2) time, where N is the board side length.
Is Minimum Queen Moves to Reach Target asked at Google, Amazon, or Meta?
This problem is tagged Array and Math and is rated Easy with a 56.7% acceptance rate on LeetCode. It is a warm-up style question, so you are more likely to see it in early screening rounds than in final onsite loops. Check company-specific question lists for current frequency.