What is the brute force approach and complexity for Minimum Steps to Reach Target by a Knight?

Try all move sequences of length 0, 1, 2, … until one lands on the target with time complexity O(8^K) and space complexity O(K).

What is the optimal approach and complexity for Minimum Steps to Reach Target by a Knight?

Visit squares in rings from the start; the first time the target is popped gives the answer with optimal time complexity O(N²) and space complexity O(N²).

How do you identify the pattern for Minimum Steps to Reach Target by a Knight?

Look for key signals in the prompt: "fewest moves" indicates Every move costs 1, so a question about the fewest moves is a shortest-path question. With equal costs, BFS gives the answer.; "knight on a board" indicates Each square is a state, and each legal jump is an edge. The graph is never built in full; the 8 jumps are worked out from the current square.; "reach the target" indicates There is only one target, so the search can stop as soon as the target leaves the queue..

Minimum Steps to Reach Target by a Knight

Medium·GeeksforGeeksBasic Anchor

GeeksforGeeks

Jump:

30-Second Mental ModelGraph BFS, Implicit graph / state BFS

Complexity:O(8^K)→O(N²)

Key Insight

Treat each square as a node and each legal knight move as an edge. Run BFS from the start square. Give a square its distance the moment it is pushed, so it enters the queue only once. The first distance written for a square is its shortest distance.

Core Validity Invariant

A square's distance is set the first time it is pushed, and it is never changed after that. Every square is pushed once, so the queue never holds the same square twice.

Problem

You have an N × N chessboard. A knight stands on one square, and you want to move it to a target square. Rows and columns are numbered from 1 to N, so the top-left square is (1, 1).

A knight moves in an L shape: two squares in one direction, then one square sideways. From a square it has up to 8 moves. A move must stay on the board.

Return the fewest moves the knight needs to reach the target. If the knight already stands on the target, the answer is 0. If the target can never be reached, return -1.

Input

Three values: N, the size of the board; knightPos = [row, column], where the knight starts; targetPos = [row, column], where it must go. Both positions use 1-indexed numbers.

Output

One number: the minimum number of knight moves, or -1 if the target cannot be reached.

Example 1

Input: N = 8, knightPos = [1, 1], targetPos = [8, 8]

Output: 6

Going from one corner of an 8 × 8 board to the opposite corner takes 6 knight moves.

Example 2

Input: N = 6, knightPos = [1, 1], targetPos = [6, 5]

Output: 3

One route is (1,1) → (2,3) → (4,4) → (6,5). Each step is a legal L-shaped jump, and no route with 2 moves exists.

Example 3

Input: N = 4, knightPos = [2, 2], targetPos = [2, 2]

Output: 0

The knight is already on the target, so no moves are needed.

Example 4

Input: N = 3, knightPos = [1, 1], targetPos = [2, 2]

Output: -1

The centre of a 3 × 3 board has no legal knight move, and no knight move lands on it, so it can never be reached.

Constraints

• The board is N × N, and both positions are inside it: 1 ≤ row, column ≤ N.
• Positions are 1-indexed. Convert them to array indexes before you use them.
• On a board of 4 × 4 or bigger every square can be reached. Only very small boards (3 × 3 or less) can leave a square unreachable.

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
A knight move changes the square in one fixed way. How many squares can the knight reach in one move from the middle of the board?
2.
If I try every sequence of moves, how fast does the number of sequences grow with each extra move?
3.
Is the shortest route always the one that gets closer to the target at every move?
4.
If the knight has already reached a square, does a shortest route ever need to come back to it?
5.
If I explore from the start in rings, first every square one move away, then two moves away, what changes when I reach the target?

Brute force approach

Idea

Pick a limit, starting at 0. Try every sequence of at most that many knight moves and check whether one ends on the target. If none does, raise the limit by 1 and search again. The first limit that works is the answer.

Thinking process

1
A route is a list of knight moves. The question asks for the shortest route, so I need the smallest number of moves that can reach the target.
2
Limit 0: the knight is on (1,1) and the target is (3,3), so no. Limit 1: on a 5 × 5 board, (1,1) has only two legal moves, to (2,3) and (3,2). Neither is (3,3), so no.
3
Limits 2 and 3 also fail. Limit 4 works: (1,1) → (3,2) → (5,3) → (4,5) → (3,3) is one of the 4-move routes.
4
Every limit starts the search again from the beginning. Each extra move can multiply the number of sequences by up to 8, so this only works on tiny boards.

Visual

Blue = squares the search touched (each call counts, even repeats). Each new limit starts again from the start square, so the earlier work is repeated. Each extra move can multiply the calls by up to 8.

Brute force: try every move sequenceN = 5, knightPos = [1,1], targetPos = [3,3]step 1/10

board

Limit

max moves: 0
calls made: 1
squares touched: 1
reached target: no

Limit 0: no sequence of 0 or fewer moves reaches T

With at most 0 moves, the search tries every sequence (1 calls) and none ends on T. Each extra move can multiply the work by up to 8.

Code & Implementation

brute.cpp

class Solution {
    // Can the knight get from (r, c) to (tr, tc) in at most `left` moves?
    // It tries every sequence of moves, so it is only practical on tiny boards.
    bool canReach(int r, int c, int tr, int tc, int n, int left) {
        if (r == tr && c == tc) return true;
        if (left == 0) return false;
        const int dr[] = {2, 2, -2, -2, 1, 1, -1, -1};
        const int dc[] = {1, -1, 1, -1, 2, -2, 2, -2};
        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) continue;   // the move leaves the board
            if (canReach(nr, nc, tr, tc, n, left - 1)) return true;
        }
        return false;
    }

public:
    int minStepToReachTarget(vector<int>& knightPos, vector<int>& targetPos, int n) {
        // The statement is 1-indexed. Convert to 0-indexed board positions.
        int r = knightPos[0] - 1, c = knightPos[1] - 1;
        int tr = targetPos[0] - 1, tc = targetPos[1] - 1;

        // Try limits 0, 1, 2, ... The first limit that works is the fewest moves.
        // A shortest route never visits the same square twice, so n * n moves is always enough.
        for (int moves = 0; moves <= n * n; moves++) {
            if (canReach(r, c, tr, tc, n, moves)) return moves;
        }
        return -1;   // no route at all (possible only on a 3 x 3 board or smaller)
    }
};

import java.util.*;

class Solution {
    // Can the knight get from (r, c) to (tr, tc) in at most `left` moves?
    // It tries every sequence of moves, so it is only practical on tiny boards.
    private boolean canReach(int r, int c, int tr, int tc, int n, int left) {
        if (r == tr && c == tc) return true;
        if (left == 0) return false;
        int[] dr = {2, 2, -2, -2, 1, 1, -1, -1};
        int[] dc = {1, -1, 1, -1, 2, -2, 2, -2};
        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) continue; // the move leaves the board
            if (canReach(nr, nc, tr, tc, n, left - 1)) return true;
        }
        return false;
    }

    public int minStepToReachTarget(int[] knightPos, int[] targetPos, int n) {
        // The statement is 1-indexed. Convert to 0-indexed board positions.
        int r = knightPos[0] - 1, c = knightPos[1] - 1;
        int tr = targetPos[0] - 1, tc = targetPos[1] - 1;

        // Try limits 0, 1, 2, ... The first limit that works is the fewest moves.
        // A shortest route never visits the same square twice, so n * n moves is always enough.
        for (int moves = 0; moves <= n * n; moves++) {
            if (canReach(r, c, tr, tc, n, moves)) return moves;
        }
        return -1; // no route at all (possible only on a 3 x 3 board or smaller)
    }
}

from typing import List

class Solution:
    def minStepToReachTarget(self, knightPos: List[int], targetPos: List[int], n: int) -> int:
        # The statement is 1-indexed. Convert to 0-indexed board positions.
        r, c = knightPos[0] - 1, knightPos[1] - 1
        tr, tc = targetPos[0] - 1, targetPos[1] - 1

        dr = (2, 2, -2, -2, 1, 1, -1, -1)
        dc = (1, -1, 1, -1, 2, -2, 2, -2)

        # Can the knight get from (r, c) to (tr, tc) in at most `left` moves?
        # It tries every sequence of moves, so it is only practical on tiny boards.
        def can_reach(curr_r: int, curr_c: int, left: int) -> bool:
            if curr_r == tr and curr_c == tc:
                return True
            if left == 0:
                return False
            for k in range(8):
                nr, nc = curr_r + dr[k], curr_c + dc[k]
                if nr < 0 or nc < 0 or nr >= n or nc >= n:
                    continue  # the move leaves the board
                if can_reach(nr, nc, left - 1):
                    return True
            return False

        # Try limits 0, 1, 2, ... The first limit that works is the fewest moves.
        # A shortest route never visits the same square twice, so n * n moves is always enough.
        for moves in range(n * n + 1):
            if can_reach(r, c, moves):
                return moves
        return -1  # no route at all (possible only on a 3 x 3 board or smaller)

export function minStepToReachTarget(knightPos: number[], targetPos: number[], n: number): number {
    // The statement is 1-indexed. Convert to 0-indexed board positions.
    const r = knightPos[0] - 1, c = knightPos[1] - 1;
    const tr = targetPos[0] - 1, tc = targetPos[1] - 1;

    const dr = [2, 2, -2, -2, 1, 1, -1, -1];
    const dc = [1, -1, 1, -1, 2, -2, 2, -2];

    // Can the knight get from (r, c) to (tr, tc) in at most `left` moves?
    // It tries every sequence of moves, so it is only practical on tiny boards.
    function canReach(currR: number, currC: number, left: number): boolean {
        if (currR === tr && currC === tc) return true;
        if (left === 0) return false;
        for (let k = 0; k < 8; k++) {
            const nr = currR + dr[k], nc = currC + dc[k];
            if (nr < 0 || nc < 0 || nr >= n || nc >= n) continue; // the move leaves the board
            if (canReach(nr, nc, left - 1)) return true;
        }
        return false;
    }

    // Try limits 0, 1, 2, ... The first limit that works is the fewest moves.
    // A shortest route never visits the same square twice, so n * n moves is always enough.
    for (let moves = 0; moves <= n * n; moves++) {
        if (canReach(r, c, moves)) return moves;
    }
    return -1; // no route at all (possible only on a 3 x 3 board or smaller)
}

Complexity

Time O(8^K)Space O(K)

K is the answer (the number of moves). The limits 0, 1, …, K run one after another, and the last one tries up to 8^K move sequences, so the total is a small constant times 8^K. The recursion goes at most K levels deep, which is the O(K) space.

Optimized approach

Idea

Start from brute force

The brute force tries every move sequence. Many sequences end on the same square, and each one is walked again from the start.

Find the repeated work

On an 8 × 8 board there are only 64 squares, but the number of move sequences of length 6 is about 8⁶ ≈ 262 000. Most of those sequences land on a square that a shorter sequence already reached.

Define the state — what variables do I need?

queue: Squares waiting to be expanded, in the order they were reached.
dist[r][c]: The fewest moves found so far to reach square (r, c). −1 means not reached yet.

Define validity

A square's distance is set the first time it is pushed, and it is never changed after that. Every square is pushed once, so the queue never holds the same square twice.

Define the transitions — when does each pointer move, and why is it safe?

Before the loop

dist[start] = 0; push the start

The knight is 0 moves away from its own square.

Pop a square (r, c)

for each of the 8 moves to (nr, nc) that is on the board and has dist = −1: set dist[nr][nc] = dist[r][c] + 1 and push it

The knight jumps from (r, c) to (nr, nc) in one move. A square with dist already set was reached by a route that is at least as short, so skipping it is safe.

Pop the target

return dist[target]

Squares leave the queue in order of distance, so the first time the target is popped, its distance is the smallest possible.

What does the current window add to the answer?

Each pop adds at most 8 new squares to the queue. Over the whole run, each square is pushed once, so the total work is about the number of squares on the board.

Code & Implementation

optimal.cpp

class Solution {
public:
    int minStepToReachTarget(vector<int>& knightPos, vector<int>& targetPos, int n) {
        // The statement is 1-indexed. Convert to 0-indexed board positions.
        int sr = knightPos[0] - 1, sc = knightPos[1] - 1;
        int tr = targetPos[0] - 1, tc = targetPos[1] - 1;

        // dist[r][c] = fewest moves found so far. -1 means not reached yet.
        vector<vector<int>> dist(n, vector<int>(n, -1));
        queue<pair<int, int>> q;
        dist[sr][sc] = 0;
        q.push({sr, sc});

        const int dr[] = {2, 2, -2, -2, 1, 1, -1, -1};
        const int dc[] = {1, -1, 1, -1, 2, -2, 2, -2};
        while (!q.empty()) {
            auto [r, c] = q.front();
            q.pop();
            if (r == tr && c == tc) return dist[r][c];

            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) continue;   // off the board
                if (dist[nr][nc] != -1) continue;   // already reached by a route at least this short
                // Set the distance when the square is pushed, so it enters the queue only once.
                dist[nr][nc] = dist[r][c] + 1;
                q.push({nr, nc});
            }
        }
        return -1;   // the queue ran out before the target: unreachable
    }
};

import java.util.*;

class Solution {
    public int minStepToReachTarget(int[] knightPos, int[] targetPos, int n) {
        // The statement is 1-indexed. Convert to 0-indexed board positions.
        int sr = knightPos[0] - 1, sc = knightPos[1] - 1;
        int tr = targetPos[0] - 1, tc = targetPos[1] - 1;

        // dist[r][c] = fewest moves found so far. -1 means not reached yet.
        int[][] dist = new int[n][n];
        for (int[] row : dist) {
            Arrays.fill(row, -1);
        }
        Queue<int[]> q = new LinkedList<>();
        dist[sr][sc] = 0;
        q.offer(new int[]{sr, sc});

        int[] dr = {2, 2, -2, -2, 1, 1, -1, -1};
        int[] dc = {1, -1, 1, -1, 2, -2, 2, -2};
        while (!q.isEmpty()) {
            int[] curr = q.poll();
            int r = curr[0], c = curr[1];
            if (r == tr && c == tc) return dist[r][c];

            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) continue; // off the board
                if (dist[nr][nc] != -1) continue; // already reached by a route at least this short
                // Set the distance when the square is pushed, so it enters the queue only once.
                dist[nr][nc] = dist[r][c] + 1;
                q.offer(new int[]{nr, nc});
            }
        }
        return -1; // the queue ran out before the target: unreachable
    }
}

from typing import List
from collections import deque

class Solution:
    def minStepToReachTarget(self, knightPos: List[int], targetPos: List[int], n: int) -> int:
        # The statement is 1-indexed. Convert to 0-indexed board positions.
        sr, sc = knightPos[0] - 1, knightPos[1] - 1
        tr, tc = targetPos[0] - 1, targetPos[1] - 1

        # dist[r][c] = fewest moves found so far. -1 means not reached yet.
        dist = [[-1] * n for _ in range(n)]
        q = deque([(sr, sc)])
        dist[sr][sc] = 0

        dr = (2, 2, -2, -2, 1, 1, -1, -1)
        dc = (1, -1, 1, -1, 2, -2, 2, -2)
        while q:
            r, c = q.popleft()
            if r == tr and c == tc:
                return dist[r][c]

            for k in range(8):
                nr, nc = r + dr[k], c + dc[k]
                if nr < 0 or nc < 0 or nr >= n or nc >= n:
                    continue  # off the board
                if dist[nr][nc] != -1:
                    continue  # already reached by a route at least this short
                # Set the distance when the square is pushed, so it enters the queue only once.
                dist[nr][nc] = dist[r][c] + 1
                q.append((nr, nc))

        return -1  # the queue ran out before the target: unreachable

export function minStepToReachTarget(knightPos: number[], targetPos: number[], n: number): number {
    // The statement is 1-indexed. Convert to 0-indexed board positions.
    const sr = knightPos[0] - 1, sc = knightPos[1] - 1;
    const tr = targetPos[0] - 1, tc = targetPos[1] - 1;

    // dist[r][c] = fewest moves found so far. -1 means not reached yet.
    const dist: number[][] = Array.from({ length: n }, () => Array(n).fill(-1));
    const q: [number, number][] = [[sr, sc]];
    dist[sr][sc] = 0;

    const dr = [2, 2, -2, -2, 1, 1, -1, -1];
    const dc = [1, -1, 1, -1, 2, -2, 2, -2];
    let head = 0;

    while (head < q.length) {
        const [r, c] = q[head++];
        if (r === tr && c === tc) return dist[r][c];

        for (let k = 0; k < 8; k++) {
            const nr = r + dr[k], nc = c + dc[k];
            if (nr < 0 || nc < 0 || nr >= n || nc >= n) continue; // off the board
            if (dist[nr][nc] !== -1) continue; // already reached by a route at least this short
            // Set the distance when the square is pushed, so it enters the queue only once.
            dist[nr][nc] = dist[r][c] + 1;
            q.push([nr, nc]);
        }
    }
    return -1; // the queue ran out before the target: unreachable
}

Complexity

Time O(N²)Space O(N²)

N is the side of the board, so the board has N² squares. Each square is pushed once and popped once, and each pop checks 8 moves. The dist table takes N² cells.

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	Try all move sequences of length 0, 1, 2, … until one lands on the target	O(8^K)	O(K)
Optimal	Visit squares in rings from the start; the first time the target is popped gives the answer	O(N²)	O(N²)

Why does this belong to this pattern?

Clues in the problem statement

“fewest moves”Every move costs 1, so a question about the fewest moves is a shortest-path question. With equal costs, BFS gives the answer.
“knight on a board”Each square is a state, and each legal jump is an edge. The graph is never built in full; the 8 jumps are worked out from the current square.
“reach the target”There is only one target, so the search can stop as soon as the target leaves the queue.

Implicit graph (squares are nodes)+every edge costs 1+fewest edges → BFS→Graph BFS, Implicit graph / state BFS

This is the anchor of the sub-pattern. The state is a square on a fixed board, and the moves never change, so the neighbours come from 8 fixed offsets. The next problems keep the same BFS but change what a state is: a four-digit lock code, a word, or a square with snakes and ladders.

Don't make this mistake

Greedy: always step to the square closest to the target

✗ choose the move that minimises |row − targetRow| + |col − targetCol|, then repeat

✓ try all 8 moves from every square with BFS

Closest on the board is not the same as fewest moves. On an 8 × 8 board, from (1,1) toward (2,2): the knight can jump to (3,2), which is one step away by distance. From (3,2) the closest moves are (1,1), (1,3) and (2,4), all two steps away. From (1,3) the closest moves are (3,2) and (2,1). If ties go to the first move in the code's move list, the walk goes (1,1) → (3,2) → (1,3) → (3,2) → … and never reaches (2,2). The real answer is 4.

Using DFS, which finds a route but not the shortest one

✗ use a stack and return the depth the first time the target is popped

✓ use a queue, so squares are reached in order of distance

DFS goes deep down one route before it tries the others, so the first route it finds can be long. On this 5 × 5 board from (1,1) to (3,3), a DFS with a visited set (trying moves in the order used in this walkthrough) finds (1,1) → (3,2) → (5,3) → (3,4) → (5,5) → (4,3) → (2,4) → (4,5) → (3,3) first. That is 8 moves, while BFS finds one with 4.

Forgetting the statement is 1-indexed

✗ int r = knightPos[0], c = knightPos[1];

✓ int r = knightPos[0] - 1, c = knightPos[1] - 1;

The top-left square is (1, 1), but C++ arrays start at index 0. Without the −1, a knight on (8, 8) on an 8 × 8 board would use index 8, one past the last row, and the dist table would be read or written outside its bounds.

Want to implement this?

Write it yourself on GeeksforGeeks, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Graph BFS / DFS translate into production architectures and low-level memory mechanics.

LLD Real-World Story

Food Delivery System (Zomato / DoorDash)

Geospatial indexing and shortest dispatch routing for delivery partners.

Explore Track

C++ Internals

Virtual Method Table (vtable) & Dynamic Dispatch

Polymorphic graph nodes and state machine execution overhead.

Explore Track

Open the Lock