Minimum Knight Moves - Practice Coding Problems

Minimum Knight Moves - Problem

Breadth-First Search Medium

In an infinite chess board with coordinates from -infinity to +infinity, you have a knight at square [0, 0].

A knight has 8 possible moves it can make, as illustrated below. Each move is two squares in a cardinal direction, then one square in an orthogonal direction.

Return the minimum number of steps needed to move the knight to the square [x, y]. It is guaranteed the answer exists.

The 8 possible knight moves are: [+2,+1], [+2,-1], [-2,+1], [-2,-1], [+1,+2], [+1,-2], [-1,+2], [-1,-2].

Input & Output

Example 1 — Basic Case

$ Input: x = 2, y = 1

› Output: 1

💡 Note: Knight can reach (2,1) from (0,0) in 1 move: (0,0) → (2,1)

Example 2 — Multiple Steps

$ Input: x = 5, y = 5

› Output: 4

💡 Note: One optimal path: (0,0) → (2,1) → (4,2) → (5,4) → (5,5) in 4 moves

Example 3 — Negative Coordinates

$ Input: x = -3, y = -3

› Output: 2

💡 Note: Using symmetry, same as reaching (3,3): (0,0) → (2,1) → (3,3) in 2 moves

Constraints

|x| + |y| ≤ 300

Visualization

Tap to expand

Understanding the Visualization

Input

Knight at (0,0), target at (2,1)

Process

Find shortest path using knight moves

Output

Minimum steps = 1

Key Takeaway

🎯 Key Insight: BFS guarantees the shortest path in unweighted graphs like chess knight moves

Asked in

a Amazon 35 G Google 28 M Microsoft 22 f Facebook 18

The key insight is that this is a shortest path problem on an unweighted graph, making BFS the optimal approach. The best approach uses BFS with symmetry optimization to reduce search space. Time: O(max(|x|,|y|)²), Space: O(max(|x|,|y|)²)

Common Approaches

Approach	Time	Space	Notes
✓ Breadth-First Search	O(max(\|x\|,\|y\|)²)	O(max(\|x\|,\|y\|)²)	Use BFS to find shortest path level by level
Brute Force DFS	O(8^n)	O(n)	Try all possible knight moves recursively until reaching target
Optimized BFS with Symmetry	O(max(\|x\|,\|y\|)²)	O(max(\|x\|,\|y\|)²)	Use BFS with symmetry to reduce search space by half

Breadth-First Search — Algorithm Steps

Start BFS from (0,0) with queue
For each position, try all 8 knight moves
Track visited positions to avoid cycles
Return steps when target is reached

Visualization

Tap to expand

Step-by-Step Walkthrough

Level 0

Start at (0,0)

Level 1

Explore all 8 knight moves from start

Found

First time reaching target gives minimum steps

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_QUEUE 100000
#define MAX_VISITED 100000

typedef struct {
    int x, y, steps;
} Position;

typedef struct {
    char key[20];
} VisitedEntry;

int moves[8][2] = {{2,1}, {2,-1}, {-2,1}, {-2,-1}, {1,2}, {1,-2}, {-1,2}, {-1,-2}};
Position queue[MAX_QUEUE];
VisitedEntry visited[MAX_VISITED];
int front = 0, rear = 0, visitedCount = 0;

int isVisited(int x, int y) {
    char key[20];
    sprintf(key, "%d,%d", x, y);
    for (int i = 0; i < visitedCount; i++) {
        if (strcmp(visited[i].key, key) == 0) {
            return 1;
        }
    }
    return 0;
}

void addVisited(int x, int y) {
    sprintf(visited[visitedCount].key, "%d,%d", x, y);
    visitedCount++;
}

int solution(int x, int y) {
    if (x == 0 && y == 0) {
        return 0;
    }
    
    front = rear = visitedCount = 0;
    queue[rear++] = (Position){0, 0, 0};
    addVisited(0, 0);
    
    while (front < rear) {
        Position curr = queue[front++];
        
        for (int i = 0; i < 8; i++) {
            int newX = curr.x + moves[i][0];
            int newY = curr.y + moves[i][1];
            
            if (newX == x && newY == y) {
                return curr.steps + 1;
            }
            
            if (!isVisited(newX, newY)) {
                addVisited(newX, newY);
                queue[rear++] = (Position){newX, newY, curr.steps + 1};
            }
        }
    }
    
    return -1; // Should never reach here
}

int main() {
    int x, y;
    scanf("%d", &x);
    scanf("%d", &y);
    printf("%d\n", solution(x, y));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(max(|x|,|y|)²)

BFS explores positions in roughly circular pattern, area grows quadratically

✓ Linear Growth

Space Complexity

O(max(|x|,|y|)²)

Queue and visited set store positions in search area

✓ Linear Space

28.5K Views

Medium Frequency

~25 min Avg. Time

842 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Breadth-First Search — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler