Watch 3 video solutions for Even Number of Knight Moves, a easy level problem. This walkthrough by Programming Live with Larry has 339 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given two integer arrays start and target, where each array is of the form [x, y] representing a cell on a standard 8 x 8 chessboard.
Return true if a knight can move from start to target in an even number of moves. Otherwise, return false.
Note: A valid knight move consists of moving two squares in one direction and one square perpendicular to it. The figure below illustrates all eight possible moves from a cell.
Example 1:
Input: start = [1,1], target = [2,2]
Output: true
Explanation:
One possible sequence of moves is (1, 1) -> (3, 2) -> (2, 4) -> (4, 3) -> (2, 2).
The knight reaches the target in 4 moves, which is even. Thus, the answer is true.
Example 2:
Input: start = [4,5], target = [6,6]
Output: false
Explanation:
It is impossible to reach target = [6, 6] from start = [4, 5] in an even number of moves. Thus, the answer is false.
Constraints:
start.length == target.length == 20 <= start[i], target[i] <= 7Problem Overview: You need to determine whether a knight on a chessboard can reach a target position using an even number of moves. The core observation is that knight movement alternates square color parity on every move, which makes this problem more about mathematical properties than full path simulation.
Approach 1: Breadth-First Search (BFS) Simulation (Time: O(n), Space: O(n))
The direct solution is to run a BFS from the starting cell and explore all 8 knight moves level by level. Each BFS layer represents one move count, so when you first reach the target, you can check whether the depth is even. This approach works well for bounded boards or when the board dimensions are small enough to explore safely. Use a queue and a visited set to avoid revisiting positions. Problems involving shortest movement paths often use Breadth-First Search because BFS guarantees the minimum move count.
Approach 2: Chessboard Parity Observation (Time: O(1), Space: O(1))
The optimal approach relies on parity. A knight always changes square color after every move because its movement changes coordinates by an odd total amount. If the start and target squares have the same color parity, the knight needs an even number of moves. If the colors differ, the move count must be odd. Instead of exploring the board, compute (row + col) % 2 for both positions and compare them. This converts the problem into a simple arithmetic check using Math and board parity properties.
Approach 3: Recursive Backtracking (Time: O(8^k), Space: O(k))
A recursive solution tries all possible knight moves until reaching the target or exceeding a move limit. While this demonstrates the movement rules clearly, it becomes exponentially expensive because each position branches into up to eight new states. This approach is mainly useful for understanding traversal logic or for interview discussion before optimizing into BFS or parity analysis. Recursive traversal problems often overlap with Graph exploration patterns.
Recommended for interviews: Start with BFS to show you understand shortest-path traversal on grids and unweighted graphs. Then optimize using the parity observation. Interviewers usually expect the O(1) parity solution because it demonstrates pattern recognition and mathematical reasoning rather than brute-force exploration.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| BFS Simulation | O(n) | O(n) | When shortest path exploration is required on bounded boards |
| Parity Observation | O(1) | O(1) | Best general solution for checking even or odd move count |
| Recursive Backtracking | O(8^k) | O(k) | Useful for learning traversal logic or constrained search depth |