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 collections.deque in Python and ArrayDeque in Java.

How to solve Even Number of Knight Moves in O(1)?

Compute the parity of both positions using (row + col) % 2 . 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.

Description Hints 6 Solution Video 4:52

3996. Even Number of Knight Moves

Easy75.1% acceptance

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

Topics

Array Math

Hints open one at a time

Hint 1

1a (Chessboard Coloring). Color the chessboard like a standard chessboard using the parity of x + y.

Hint 2

1b (Chessboard Coloring). Every knight move changes the color of the current cell. Therefore, after an even number of moves, the knight must be on a cell of the same color as the starting cell.

Hint 3

1c (Chessboard Coloring). Since every cell is reachable from every other cell on an 8 x 8 chessboard, return whether (start[0] + start[1]) % 2 == (target[0] + target[1]) % 2.

Hint 4

2a (BFS). Treat each of the 64 cells as a node and connect two cells if a knight can move between them.

Hint 5

2b (BFS). Run BFS while tracking both the current cell and the parity of the number of moves used.

Hint 6

2c (BFS). Return true if target is reachable with even parity.

4:52

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def canReach(self, start: list[int], target: list[int]) -> bool:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

[1,1]
[2,2]

Input

[4,5]
[6,6]

Your code is saved on this device.Solution