Knight Walk — Solution in Python, Java & C++
Knight Walk solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Knight Walk is a medium coding problem on matrix and breadth-first search, asked in Amazon, Microsoft and Samsung interviews.
- Difficulty: Medium
- Topics: Matrix, Breadth-First Search
- Asked at: Amazon, Microsoft, Samsung
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A knight stands on an n x n chessboard whose rows and columns are numbered 1 to n. It starts at knightPos = [row, col] and wants to reach targetPos = [row, col].
In one move a knight goes two squares in one direction and one square in a perpendicular direction — up to eight possible squares — and it may never leave the board.
Return the minimum number of moves the knight needs to reach the target, or -1 if it can never get there.
Example 1
Input: knightPos = [4,5], targetPos = [1,1], n = 6
Output: 3
Explanation: One shortest route is (4,5) → (5,3) → (3,2) → (1,1).
Example 2
Input: knightPos = [2,2], targetPos = [1,1], n = 3
Output: -1
Explanation: On a 3 x 3 board the centre square has no legal move at all.
Example 3
Input: knightPos = [1,1], targetPos = [1,1], n = 1
Output: 0
Constraints
1 <= n <= 1000knightPos.length == targetPos.length == 21 <= knightPos[i], targetPos[i] <= n
Hints for Knight Walk
Hint 1
Every move costs the same, so the fewest moves is a shortest path in an unweighted graph whose vertices are the squares.
Hint 2
Breadth-first search from the knight's square visits squares in order of their distance.
Hint 3
Mark a square when it is first enqueued so no square enters the queue twice, and stop as soon as the target is reached.
How to solve Knight Walk
The board is an unweighted graph: each square is a vertex joined to the up-to-eight squares a knight can jump to. Breadth-first search from the start finds the shortest number of jumps to every square.
Approach
- If the start equals the target, return
0. - Keep a distance array over the
n * nsquares, all-1, and set the start to0. Push the start into a queue. - Pop a square; for each of the eight jumps that stays on the board and lands on an unvisited square, set its distance to the current one plus one and push it. If that square is the target, return its distance.
- If the queue empties first, the target is unreachable: return
-1.
Why it works
BFS processes squares in non-decreasing distance order, so the first time a square is discovered it is discovered by a shortest route. The target therefore gets its true minimum on discovery.
Complexity
- Time —
O(n^2) - Space —
O(n^2)
Pitfalls
- Positions are 1-indexed; convert them (or bound-check against
1..n) consistently. - On boards of side 1, 2 or 3 some squares are unreachable — the
-1case is real. - Mark squares visited when they are pushed, not when popped, or the queue can hold many copies of a square.
Reference solution
Python
from collections import deque
from typing import List
def minStepToReachTarget(knightPos: List[int], targetPos: List[int], n: int) -> int:
sr, sc = knightPos[0] - 1, knightPos[1] - 1
tr, tc = targetPos[0] - 1, targetPos[1] - 1
if sr == tr and sc == tc:
return 0
dist = [-1] * (n * n)
dist[sr * n + sc] = 0
q = deque([(sr, sc)])
moves = ((1, 2), (2, 1), (2, -1), (1, -2), (-1, -2), (-2, -1), (-2, 1), (-1, 2))
while q:
r, c = q.popleft()
d = dist[r * n + c]
for dr, dc in moves:
nr, nc = r + dr, c + dc
if 0 <= nr < n and 0 <= nc < n and dist[nr * n + nc] == -1:
if nr == tr and nc == tc:
return d + 1
dist[nr * n + nc] = d + 1
q.append((nr, nc))
return -1Java
public static int minStepToReachTarget(int[] knightPos, int[] targetPos, int n) {
int sr = knightPos[0] - 1, sc = knightPos[1] - 1, tr = targetPos[0] - 1, tc = targetPos[1] - 1;
if (sr == tr && sc == tc) return 0;
int[] dr = {1, 2, 2, 1, -1, -2, -2, -1}, dc = {2, 1, -1, -2, -2, -1, 1, 2};
int[] dist = new int[n * n];
Arrays.fill(dist, -1);
int[] q = new int[n * n];
int head = 0, tail = 0;
dist[sr * n + sc] = 0;
q[tail++] = sr * n + sc;
while (head < tail) {
int cur = q[head++], r = cur / n, c = cur % n;
for (int k = 0; k < 8; k++) {
int nr = r + dr[k], nc = c + dc[k];
if (nr < 0 || nc < 0 || nr >= n || nc >= n || dist[nr * n + nc] != -1) continue;
if (nr == tr && nc == tc) return dist[cur] + 1;
dist[nr * n + nc] = dist[cur] + 1;
q[tail++] = nr * n + nc;
}
}
return -1;
}C++
int minStepToReachTarget(vector<int>& knightPos, vector<int>& targetPos, int n) {
int sr = knightPos[0] - 1, sc = knightPos[1] - 1, tr = targetPos[0] - 1, tc = targetPos[1] - 1;
if (sr == tr && sc == tc) return 0;
int dr[8] = {1, 2, 2, 1, -1, -2, -2, -1}, dc[8] = {2, 1, -1, -2, -2, -1, 1, 2};
vector<int> dist(n * n, -1);
queue<int> q;
dist[sr * n + sc] = 0;
q.push(sr * n + sc);
while (!q.empty()) {
int cur = q.front(); q.pop();
int r = cur / n, c = cur % n;
for (int k = 0; k < 8; k++) {
int nr = r + dr[k], nc = c + dc[k];
if (nr < 0 || nc < 0 || nr >= n || nc >= n || dist[nr * n + nc] != -1) continue;
if (nr == tr && nc == tc) return dist[cur] + 1;
dist[nr * n + nc] = dist[cur] + 1;
q.push(nr * n + nc);
}
}
return -1;
}JavaScript
var minStepToReachTarget = function(knightPos, targetPos, n) {
var sr = knightPos[0] - 1, sc = knightPos[1] - 1, tr = targetPos[0] - 1, tc = targetPos[1] - 1;
if (sr === tr && sc === tc) return 0;
var dr = [1, 2, 2, 1, -1, -2, -2, -1], dc = [2, 1, -1, -2, -2, -1, 1, 2];
var dist = new Array(n * n);
for (var i = 0; i < n * n; i++) dist[i] = -1;
dist[sr * n + sc] = 0;
var q = [sr * n + sc];
for (var h = 0; h < q.length; h++) {
var r = Math.floor(q[h] / n), c = q[h] % n, d = dist[q[h]];
for (var k = 0; k < 8; k++) {
var nr = r + dr[k], nc = c + dc[k];
if (nr < 0 || nc < 0 || nr >= n || nc >= n || dist[nr * n + nc] !== -1) continue;
if (nr === tr && nc === tc) return d + 1;
dist[nr * n + nc] = d + 1;
q.push(nr * n + nc);
}
}
return -1;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 184 matrix problems · the whole catalogue
Learn the technique: Matrix and Grid Traversal · Breadth-First Search (BFS)