#1197 Minimum Knight Moves
the problem
In plain words
A chess knight stands on square (0, 0) of a board that never ends in any direction. One knight move goes 2 squares in one direction (along x or y) and 1 square at a right angle — 8 possible moves. Given a target (x, y), return the fewest moves to land on it. It is always reachable.
in x = 2, y = 1
out 1
(0, 0) → (2, 1).
in x = 5, y = 5
out 4
(0, 0) → (2, 1) → (4, 2) → (3, 4) → (5, 5).
- −300 ≤ x, y ≤ 300
- 0 ≤ |x| + |y| ≤ 300
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code right here. Stuck for 20 minutes? Open one hint at a time.
This one is LeetCode Premium. You don't need a subscription: solve it right here. The free alternative linked above is the closest free practice; its label says how close it is.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternBFS shortest path (unweighted)
Each move costs 1, so it's BFS on an implicit graph — the squares are generated on the fly. Two facts tame the infinite board: the answer is symmetric (|x|, |y| give the same count), and a shortest path never wanders far outside the box around the target.
solutions
From brute force to optimal
BFS from (0, 0) with the 8 knight moves, but only inside a box a little bigger than the target. Store visited in a boolean[][] with an offset instead of a HashSet<String>.
- limit = max(|x|, |y|) + 3; seen is (2·limit + 1)² with (a, b) stored at [a + limit][b + limit].
- BFS level by level from (0, 0).
- Return the level at which (x, y) is polled.
The box has about (2·max(|x|, |y|))² squares, each polled at most once with 8 moves.
The seen grid plus the queue.
class Solution { private static final int[][] MOVES = {{1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}, {-2, -1}, {-2, 1}, {-1, 2}}; /** Plain BFS from (0, 0). The board is infinite, but a box a little bigger than the target is enough. */ public int minKnightMoves(int x, int y) { int limit = Math.max(Math.abs(x), Math.abs(y)) + 3; // a shortest path never needs to go further out int size = 2 * limit + 1; boolean[][] seen = new boolean[size][size]; // (a, b) is stored at [a + limit][b + limit] Deque<int[]> queue = new ArrayDeque<>(); queue.offer(new int[] {0, 0}); seen[limit][limit] = true; for (int moves = 0; !queue.isEmpty(); moves++) { for (int count = queue.size(); count > 0; count--) { // one BFS level = one more move int[] cur = queue.poll(); if (cur[0] == x && cur[1] == y) return moves; for (int[] m : MOVES) { int a = cur[0] + m[0], b = cur[1] + m[1]; if (Math.abs(a) > limit || Math.abs(b) > limit || seen[a + limit][b + limit]) continue; seen[a + limit][b + limit] = true; queue.offer(new int[] {a, b}); } } } return -1; // never happens: a knight can reach every square }}Fold the target into the first quadrant. The last move into (x, y) came from (|x−1|, |y−2|) or (|x−2|, |y−1|) — the two squares pointing back towards the origin. Recurse with a memo.
- x = |x|, y = |y|.
- Base cases: x + y == 0 → 0; x + y == 2 → 2 (the squares (1,1), (2,0), (0,2)).
- Otherwise: 1 + min(f(|x−1|, |y−2|), f(|x−2|, |y−1|)), stored in a memo.
Every state stays inside 0..|x|+2 by 0..|y|+2 and is solved once in O(1).
The memo; the recursion is only about (|x| + |y|) / 3 deep.
class Solution { private final Map<Integer, Integer> memo = new HashMap<>(); /** The board is symmetric, so fold everything into the first quadrant and step back towards (0, 0). */ public int minKnightMoves(int x, int y) { return moves(Math.abs(x), Math.abs(y)); } private int moves(int x, int y) { if (x + y == 0) return 0; // already there if (x + y == 2) return 2; // (1,1), (2,0), (0,2): two moves, the base cases that break the pattern int key = x * 1000 + y; Integer known = memo.get(key); if (known != null) return known; // The last move reached (x, y) from one of the two squares that point back towards the origin. int best = 1 + Math.min(moves(Math.abs(x - 1), Math.abs(y - 2)), moves(Math.abs(x - 2), Math.abs(y - 1))); memo.put(key, best); return best; }}in the room
How to say it in the interview
talk track
- Start with BFS: "fewest moves, equal cost → BFS; the board is infinite, so I generate neighbours on the fly."
- Then shrink it: symmetry lets me use |x|, |y|, and I bound the search to a small box.
- If asked for faster, present the memo recursion and explain the two special base cases.
traps
- BFS with a
HashSet<String>of "a,b" keys — it works, but string building and hashing on every move is slow. Use an offsetboolean[][]or an int key. - Restricting BFS to x ≥ 0, y ≥ 0 exactly: some shortest paths step slightly negative. Allow a margin of 2 (or use the box).
- Missing the base case (1, 1) → 2 in the memo version — the general rule would give a wrong answer near the origin.
what they ask next
Follow-ups
Is there an O(1) answer?
Yes, a closed-form formula exists (based on max(⌈x/2⌉, ⌈(x+y)/3⌉) plus parity fixes), but it's easy to get wrong in an interview. Know that it exists; code the BFS or memo.
Some squares are forbidden?
Symmetry and the formula break. Go back to BFS and skip forbidden squares (that's the LintCode twin).
Speed up the BFS?
Bidirectional BFS: grow from (0, 0) and from (x, y) together, always expanding the smaller frontier, until they meet.
before you submit
Edge cases to test
- Target (0, 0) → 0.
- (1, 1) → 2 and (1, 0) → 3: tiny targets are the trickiest.
- Negative coordinates give the same answer as their absolute values.
- Far along an axis, e.g. (300, 0) → 150.
practise next
Similar problems
- #1091Shortest Path in Binary MatrixMediumin Graphs
- #909Snakes and LaddersMediumin Graphs
- #127Word LadderHardin Graphs