Coding

Minimum Knight Moves

Asked at

Walmart

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

Given a chessboard where the knight can move in an "L" shape (two squares in one direction and then one square perpendicular), you are given a starting position (0,0) and a target position (x, y). Find the minimum number of moves required for the knight to reach (x, y).

Input: x = 2, y = 1 Output: 1 Explanation: [0, 0] → [2, 1]

Input: x = 5, y = 5 Output: 4 Explanation: [0, 0] → [2, 1] → [4, 2] → [3, 4] → [5, 5]

Input: x = 3, y = 3

-300 ≤ x, y ≤ 300
0 ≤ |x| + |y| ≤ 300

cpp

class Solution {
public:
    int minKnightMoves(int x, int y) {
        //Your Code Goes Here
    }
};

java

class Solution {
    public int minKnightMoves(int x, int y) {
        // Your Code Goes Here
    }
}

python

class Solution(object):
    def minKnightMoves(self, x, y):
        """
        :type x: int
        :type y: int
        :rtype: int
        """
        #Your Code Goes Here

javascript

/**
 * @param {number} x
 * @param {number} y
 * @return {number}
 */

class Solution{
    minKnightMoves(x, y){
        //your code goes here
    }
}

csharp

public class Solution
{
    public int MinKnightMoves(int x, int y)
    {
        //Your Code Goes Here
    }
}

func minKnightMoves(x, y int) int {
	// Your Code Goes Here
}

Stuck? Show a way to structure it+

01Reflect the target into the first quadrant.
02Run BFS from the origin using knight moves.
03Bound exploration slightly below zero.
04Track visited coordinates.
05Return the first distance reaching target.

Reference answer

Knight moves form an unweighted graph, so BFS gives the minimum move count. Use symmetry first: replace target coordinates with abs(x) and abs(y), since reflecting a path preserves its length. BFS from (0,0) with the eight knight deltas, storing visited coordinate pairs and levels. Although the board is infinite, for a first-quadrant target it is safe to explore only a small margin below zero, commonly -2, because a shortest knight path never needs to wander arbitrarily far away; this keeps the visited region finite. Return when the target is dequeued or first discovered. The practical work is proportional to the explored box, O(B^2), with matching visited space. Explain the bound rather than silently hard-coding one.

Then expect these follow-ups

Can bidirectional BFS improve this?
Tests: search optimization
Why is a negative margin necessary?
Tests: geometry

Hiring now

Software engineer roles are open right now

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Senior Software Engineer -.NET
Tyler Technologies · Annapolis, Maryland
Software Development Engineer II
SaaS Labs · Bengaluru, Karnataka, India
Advanced Software Engineer - Product Architect (Legal, Safety, and Risk)
Metropolitan Transportation Authority · New York, NY

Or practice this question first

Next question