LeetCode Biweekly Contest 190 š„ | 3 Problems Solved | Q1āQ3 | 4034, 4035, 4036
Minimum Bishop Moves to Reach Target - Video Solution
Watch 2 video solutions for Minimum Bishop Moves to Reach Target, a medium level problem. This walkthrough by EdgeCaseOffByOne has 320 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 == 21 <= sr, sc, tr, tc <= 8source != 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
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Mathematical | O(1) | O(1) | Always preferred for this problem |
| BFS | O(1) (constant board) | O(1) | When board size is variable or for learning graph traversal |