Skip to main content
Talentd

Even Number of Knight Moves - Solution & Explanation

EasyArrayMath7 min read
Practice this problem

Problem Statement

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 == 2
  • 0 <= start[i], target[i] <= 7

Approach Overview

Problem 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.

Solution

Each knight move has an offset of (\pm 1, \pm 2) or (\pm 2, \pm 1), so the change in the coordinate sum x + y is always odd. In other words, every move flips the color of the square (black/white distinguished by (x + y) bmod 2).

Therefore:

  • After an even number of moves, the start and target have the same color;
  • After an odd number of moves, the start and target have different colors.

On an 8 times 8 chessboard, a knight can reach any square, and any path to a same-color square must have even length. Hence, it suffices to check whether (x + y) bmod 2 is equal for the start and the target.

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
BFS SimulationO(n)O(n)When shortest path exploration is required on bounded boards
Parity ObservationO(1)O(1)Best general solution for checking even or odd move count
Recursive BacktrackingO(8^k)O(k)Useful for learning traversal logic or constrained search depth

Video Solution

3996. Even Number of Knight Moves (Leetcode Easy) ā€¢ Programming Live with Larry ā€¢ 339 views views

Watch 2 more video solutions ā†’

Frequently Asked Questions

Is Even Number of Knight Moves easy or hard?
Even Number of Knight Moves is generally considered an Easy problem because the optimal solution depends on a simple parity observation. Candidates who recognize the chessboard color pattern can solve it in constant time without graph traversal.
Even Number of Knight Moves Python/Java solution
Python and Java implementations are usually very short for the parity approach because they only compare square colors. BFS implementations in both languages use standard queue structures such as <code>collections.deque</code> in Python and <code>ArrayDeque</code> in Java.
How to solve Even Number of Knight Moves in O(1)?
Compute the parity of both positions using <code>(row + col) % 2</code>. A knight changes parity every move, so equal parity means the target is reachable in an even number of moves, while different parity means the move count must be odd.
What is the best approach for Even Number of Knight Moves?
The parity-based approach is the best solution because it runs in O(1) time and O(1) space. A knight alternates square color after every move, so checking whether the start and target squares share the same parity immediately determines whether the move count is even.
Is Even Number of Knight Moves asked at Google/Amazon/Meta?
Knight movement and chessboard parity problems appear frequently in coding interviews because they test graph traversal and mathematical observation skills. Variants of knight shortest path and parity reasoning have shown up in interviews at large tech companies including Google and Amazon.
What data structure is used in Even Number of Knight Moves?
The BFS solution typically uses a queue and a visited set or matrix to track explored positions. The optimized parity solution does not require any additional data structure beyond a few integer variables.
What is the time complexity of Even Number of Knight Moves?
The optimal parity solution runs in O(1) time because it only compares coordinate parity values. A BFS implementation takes O(n) time and space since it explores reachable board positions level by level.

Ready to solve this problem?

Practice Even Number of Knight Moves with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays