← DSA Atlas
Dedicated problem page · #1197

Minimum Knight Moves

MediumGraph DFS and BFSUnweighted shortest path via BFS with symmetry foldingBFS on an implicit infinite grid
Solve on LeetCode ↗
1197
MediumGraph DFS and BFSBFS on an implicit infinite gridUnweighted shortest path via BFS with symmetry folding

Minimum Knight Moves

A knight starts at square [0, 0] on an infinite chessboard. A knight moves in an L-shape: two squares in one axis and one in the perpendicular axis, giving 8 possible moves. Return the minimum number of moves needed to reach the target square [x, y]. A solution is always guaranteed to exist.

Open official problem prompt ↗
In plain English

Find the smallest number of L-shaped knight jumps that move a piece from the origin to a given target square on an unbounded board.

Picture it like this

Think of dropping a stone at the origin in a pond: ripples spread out one ring at a time. Each ring is one more knight move away. The ring that first washes over the target tells you the minimum number of moves.

Example
Input
x = 2, y = 1
Output
1
Why
A single knight move from [0, 0] lands directly on [2, 1].
Constraints
-300 <= x, y <= 3000 <= |x| + |y| <= 300
Pattern lesson

See the pattern, then code

Unweighted shortest path via BFS with symmetry folding
Recognition clue

You are asked for the FEWEST moves on a grid where every move costs the same. Equal-cost steps plus 'minimum number of moves' is the classic signal for breadth-first search rather than Dijkstra or DFS.

↗
Graph DFS and BFS

Connected components, grids, reachability, or unweighted shortest paths.. BFS expands outward in rings of increasing distance, so the first time it touches the target the current level count is the shortest move count. The board is infinite, but by the 8-fold symmetry of knight moves the answer for (x, y) equals the answer for (|x|, |y|), so fold the target into the first quadrant and bound the search to a small negative margin.

New words, made simpleKnow these before the algorithm
BFS (breadth-first search)
Explore all cells reachable in k moves before any cell reachable in k+1 moves, so distances come out in nondecreasing order.
Implicit graph
The grid cells are graph nodes and knight moves are edges; you never build the graph explicitly, you generate neighbors on the fly.
Symmetry folding
Because knight moves are symmetric across both axes, the answer depends only on |x| and |y|, letting you solve just the first quadrant.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Plain BFS over the whole infinite board

Without pruning, the frontier fans out symmetrically in every direction and never terminates efficiently; you revisit an ever-growing shell of useless negative-coordinate cells.

BFS from the origin generating all 8 moves with no coordinate bounds.

Time UnboundedSpace Unbounded
Best choiceBFS with symmetry folding and a negative-coordinate cutoff

Bounds the explored region to roughly a square around the path while still allowing the small backward wiggles a knight sometimes needs, so BFS terminates fast and stays correct.

Fold the target to (|x|, |y|), then BFS but discard any cell with a coordinate below -2, which keeps the search near the origin-to-target corridor.

Time O(max(|x|, |y|)^2)Space O(max(|x|, |y|)^2)
The rule we keep true

Invariant

Every cell is enqueued exactly once, with the step count equal to its true shortest distance from the origin, because BFS dequeues cells in nondecreasing distance order.

Why this is correct

Reasoning

BFS visits nodes in layers of increasing distance, so the first time the target is dequeued its recorded step count is minimal. Folding to the first quadrant is valid because reflecting a shortest move sequence across an axis yields an equally short sequence, and the -2 margin preserves the few moves where a shortest path briefly steps to a negative coordinate.

The algorithm in three movesSay these aloud before coding
1Replace the target with (abs(x), abs(y)) using the board's symmetry

target folded to (2, 1)

2Run BFS from (0, 0), tracking the move count per node

level 0: {(0,0)}

3For each dequeued cell, generate all 8 knight moves

level 1 enqueues (2,1) -> return 1

4Skip visited cells and cells far in the negative region (coord < -2) to keep the frontier finite

5Return the step count the moment the target is dequeued

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
(0,0)0
(1,2)1
(2,1)2
(2,-1)3
(-1,2)4
(-2,1)5
1 · Readx=2, y=1
2 · AskWhat is the folded target and starting state?
3 · Update statetarget=(2,1), queue=[(0,0,0)], seen={(0,0)}
4 · ResultOrigin enqueued at distance 0.
Key takeaway

From the origin the knight's 8 reachable cells include (2,1), which is the target, so the answer is 1.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 5Fold to first quadrant

    Take absolute values so symmetric targets collapse into one canonical case, shrinking the search.

  2. 2
    Lines 6-7The 8 knight offsets

    Each pair is an L-shaped jump; iterating them generates every neighbor of a cell.

  3. 3
    Lines 8-9Queue and seen set

    The queue holds (col, row, steps); seen prevents re-enqueueing a cell, which both ensures correctness and bounds the work.

  4. 4
    Lines 11-13Goal test on dequeue

    Checking at dequeue time guarantees the returned distance is the minimum, since BFS pops cells in distance order.

  5. 5
    Lines 14-18Bounded expansion

    The nx >= -2 and ny >= -2 guard drops far-negative cells that no shortest path uses, keeping the frontier finite.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • Target is the origin (x=0, y=0): the origin is dequeued immediately and the answer is 0.
  • Negative coordinates like (-3, -3): folding to (3, 3) gives the same answer, so signs never matter.
  • Targets near the origin that need a backward step (e.g. (1,1) needs 2 moves) rely on the small -2 margin being allowed.
!

Common beginner mistakes

  • Forgetting to fold with abs and then letting BFS explode symmetrically in all four directions, causing timeouts.
  • Cutting off all negative coordinates at 0 instead of -2, which breaks short targets like (1,1) that require a temporary backward move.
  • Testing for the goal when generating neighbors instead of when dequeuing, which can be fine here but in general risks returning a non-minimal count if combined with other bugs.
  • Trying plain DFS: it explores one long chain first and does not yield shortest paths on an unweighted graph.
Check your understanding

Why is it safe to replace the target (x, y) with (|x|, |y|) before running BFS?

More in Graph DFS and BFS

#200Number of IslandsGrid flood fill#133Clone GraphGraph traversal with clone map#994Rotting OrangesMulti-source BFS (level-by-level)#127Word LadderShortest transformation via BFS#130Surrounded RegionsBorder-guarded flood fill#286Walls and GatesMulti-source BFS distance fill