LeetCode 1197: Minimum Knight Moves Solution

Master LeetCode problem 1197 (Minimum Knight Moves), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1197. Minimum Knight Moves

Medium

Breadth-First Search

Problem Explanation

Explanation:

The problem "Minimum Knight Moves" asks us to find the minimum number of moves a knight can take to reach a specified destination on an infinite chessboard. The knight moves in an L-shape pattern, which means it moves two steps in one direction and one step in a perpendicular direction.

To solve this problem, we can use the Breadth-First Search (BFS) algorithm. We start from the source position (0, 0) and explore all possible moves of the knight until we reach the target position. We keep track of the visited positions and the number of steps taken to reach each position. Once we reach the target position, we return the minimum number of steps taken. :

Solution Code

import java.util.*;

class Solution {
    public int minKnightMoves(int x, int y) {
        x = Math.abs(x);
        y = Math.abs(y);
        
        int[][] directions = {{1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}, {-2, -1}, {-2, 1}, {-1, 2}};
        
        Queue<int[]> queue = new LinkedList<>();
        Set<String> visited = new HashSet<>();
        
        queue.offer(new int[]{0, 0});
        visited.add("0,0");
        
        int steps = 0;
        
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] curr = queue.poll();
                int currX = curr[0];
                int currY = curr[1];
                
                if (currX == x && currY == y) {
                    return steps;
                }
                
                for (int[] dir : directions) {
                    int newX = currX + dir[0];
                    int newY = currY + dir[1];
                    
                    if (!visited.contains(newX + "," + newY) && newX >= -1 && newY >= -1) {
                        queue.offer(new int[]{newX, newY});
                        visited.add(newX + "," + newY);
                    }
                }
            }
            steps++;
        }
        
        return -1; // Target not reachable
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1197 (Minimum Knight Moves)?

This page provides optimized solutions for LeetCode problem 1197 (Minimum Knight Moves) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1197 (Minimum Knight Moves)?

The time complexity for LeetCode 1197 (Minimum Knight Moves) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1197 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1197 in Java, C++, or Python.

Back to LeetCode Solutions