Skip to main content
Talentd

Minimum Bishop Moves to Reach Target - Solution & Explanation

MediumArrayMath8 min read
Practice this problem

Problem Statement

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 bishop, and an array target = [tr, tc]. In one move, the bishop travels any number of squares along a single diagonal direction, staying within the board.

Return the minimum number of moves for the bishop to land exactly on target. If it can never reach target, return -1.

 

Example 1:

Input: source = [8,1], target = [1,8]

Output: 1

Explanation:

ā€‹ā€‹ā€‹ā€‹ā€‹ā€‹ā€‹

A single diagonal move takes the bishop straight from (8, 1) to (1, 8).

Example 2:

Input: source = [4,2], target = [1,3]

Output: 2

Explanation:

The bishop moves from (4, 2) to (3, 1), then from (3, 1) to (1, 3), reaching the target in 2 moves.

Example 3:

Input: source = [1,1], target = [3,4]

Output: -1

Explanation:

No matter how many diagonal moves it makes, the bishop starting at (1, 1) can never land on (3, 4). Thus, the answer is -1.

 

Constraints:ā€‹ā€‹ā€‹ā€‹ā€‹ā€‹ā€‹

  • source.length == target.length == 2
  • 1 <= sr, sc, tr, tc <= 8
  • source != target

Approach Overview

Problem Overview: Given start and target positions on a standard 8x8 chessboard, find the minimum number of moves a bishop needs to reach the target. A bishop moves diagonally any number of squares.

Approach 1: Mathematical (O(1) time, O(1) space)

Check if the squares are the same color. If not, return -1. If same square, return 0. If they are on the same diagonal (absolute difference of rows equals absolute difference of columns), return 1. Otherwise, return 2. This works because any two same-colored squares can be connected via a single intermediate square that lies on both diagonals.

Approach 2: BFS (O(1) time, O(1) space)

Since the board is 8x8, BFS from start to target exploring all diagonal moves also works. The board is small, so BFS runs in constant time. However, the mathematical approach is simpler and more efficient in practice. BFS is more general for arbitrary board sizes but is overkill here.

Recommended for interviews: Use the mathematical approach for an O(1) solution. It is the expected answer in interviews. BFS shows understanding of graph traversal, but the problem is designed to test math reasoning. The brute force BFS demonstrates basic skills, but the optimal math solution shows insight.

Related topics: Math, BFS, Chessboard

Solution

A bishop only moves along diagonals, and each move changes the row and the column by the same amount, so (r + c) bmod 2 never changes. In other words, the bishop can only stand on squares of the same color as its starting square. If (sr + sc) and (tr + tc) have different parities, the bishop can never reach the target, so we return -1.

Otherwise, if the source and the target lie on the same diagonal, i.e., |sr - tr| = |sc - tc|, a single move is enough, so we return 1.

In all remaining cases, the two squares share the same color but are not on a common diagonal. Since source neq target is guaranteed and any two same-colored squares on an 8 times 8 board can be joined through some intermediate square, the answer is 2.

The time complexity is O(1), and the space complexity is O(1).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor ā†’

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
MathematicalO(1)O(1)Always preferred for this problem
BFSO(1) (constant board)O(1)When board size is variable or for learning graph traversal

Video Solutions (2)

LeetCode Biweekly Contest 190 šŸ”„ | 3 Problems Solved | Q1ā€“Q3 | 4034, 4035, 4036

EdgeCaseOffByOne14:49320 views
Video 1 of 2

Frequently Asked Questions

Is Minimum Bishop Moves to Reach Target easy or hard?
This problem is rated Medium, but it is on the easier side of Medium. The core insight is that a bishop can reach any same-colored square in at most two moves. Once you realize that, the solution becomes trivial. It is a good test of mathematical thinking rather than complex coding.
Minimum Bishop Moves to Reach Target Python/Java solution
In Python, you can compute the answer with a few if statements. In Java, the logic is identical. Both solutions are O(1) time and space. Example: if (r1+c1)%2 != (r2+c2)%2 return -1; if (r1==r2 && c1==c2) return 0; if (abs(r1-r2)==abs(c1-c2)) return 1; else return 2.
How to solve Minimum Bishop Moves to Reach Target in O(n)?
The problem is solved in O(1) time, not O(n), because the board size is constant. You only need a few arithmetic checks: color parity, diagonal alignment, and same square. No iteration over board cells is required.
What is the best approach for Minimum Bishop Moves to Reach Target?
The best approach is a direct mathematical solution. Check if the start and target squares are the same color; if not, return -1. If they are the same square, return 0. If they lie on the same diagonal, return 1; otherwise, return 2. This runs in O(1) time and O(1) space.
Is Minimum Bishop Moves to Reach Target asked at Google/Amazon/Meta?
This problem is not a common interview question at top tech companies, but it tests fundamental math reasoning and problem-solving. It might appear in phone screens or as a warm-up. Companies like Google, Amazon, and Meta focus more on data structures and algorithms, but this type of puzzle can still be asked.
What data structure is used in Minimum Bishop Moves to Reach Target?
No data structure is required for the optimal solution. The problem is purely mathematical. If you use BFS, you would use a queue and a visited set, but that is unnecessary for the standard 8x8 board.
What is the time complexity of Minimum Bishop Moves to Reach Target?
The optimal mathematical solution runs in O(1) time and O(1) space. A BFS approach also runs in O(1) time because the board is fixed at 8x8, but the math solution is simpler and faster.

Ready to solve this problem?

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

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays