2596. Check Knight Tour Configuration LeetCode Solution

Last updated: March 5, 2025

In this guide, you will get 2596. Check Knight Tour Configuration LeetCode Solution with the best time and space complexity. The solution to Check Knight Tour Configuration problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Check Knight Tour Configuration solution in C++
Check Knight Tour Configuration solution in Java
Check Knight Tour Configuration solution in Python
Additional Resources

2596. Check Knight Tour Configuration LeetCode Solution image

Problem Statement of Check Knight Tour Configuration

There is a knight on an n x n chessboard. In a valid configuration, the knight starts at the top-left cell of the board and visits every cell on the board exactly once.
You are given an n x n integer matrix grid consisting of distinct integers from the range [0, n * n – 1] where grid[row][col] indicates that the cell (row, col) is the grid[row][col]th cell that the knight visited. The moves are 0-indexed.
Return true if grid represents a valid configuration of the knight’s movements or false otherwise.
Note that a valid knight move consists of moving two squares vertically and one square horizontally, or two squares horizontally and one square vertically. The figure below illustrates all the possible eight moves of a knight from some cell.

Example 1:

Input: grid = [[0,11,16,5,20],[17,4,19,10,15],[12,1,8,21,6],[3,18,23,14,9],[24,13,2,7,22]]
Output: true
Explanation: The above diagram represents the grid. It can be shown that it is a valid configuration.

Example 2:

Input: grid = [[0,3,6],[5,8,1],[2,7,4]]
Output: false
Explanation: The above diagram represents the grid. The 8th move of the knight is not valid considering its position after the 7th move.

Constraints:

n == grid.length == grid[i].length
3 <= n <= 7
0 <= grid[row][col] < n * n
All integers in grid are unique.

Complexity Analysis

Time Complexity: O(8n^2) = O(n^2)
Space Complexity: O(1)

2596. Check Knight Tour Configuration LeetCode Solution in C++

class Solution {
 public:
  bool checkValidGrid(vector<vector<int>>& grid) {
    if (grid[0][0] != 0)
      return false;

    const int n = grid.size();
    int i = 0;
    int j = 0;

    for (int target = 1; target < n * n; ++target) {
      const auto [x, y] = nextGrid(grid, i, j, target);
      if (x == -1 && y == -1)
        return false;
      // Move (x, y) to (i, j).
      i = x;
      j = y;
    }

    return true;
  }

 private:
  static constexpr int dirs[8][2] = {{-2, 1}, {-1, 2}, {1, 2},   {2, 1},
                                     {2, -1}, {1, -2}, {-1, -2}, {-2, -1}};

  // Returns (x, y), where grid[x][y] == target if (i, j) can reach target.
  pair<int, int> nextGrid(const vector<vector<int>>& grid, int i, int j,
                          int target) {
    const int n = grid.size();
    for (const auto& [dx, dy] : dirs) {
      const int x = i + dx;
      const int y = j + dy;
      if (x < 0 || x >= n || y < 0 || y >= n)
        continue;
      if (grid[x][y] == target)
        return {x, y};
    }
    return {-1, -1};
  }
};
/* code provided by PROGIEZ */

2596. Check Knight Tour Configuration LeetCode Solution in Java

class Solution {
  public boolean checkValidGrid(int[][] grid) {
    if (grid[0][0] != 0)
      return false;

    final int n = grid.length;
    int i = 0;
    int j = 0;

    for (int target = 1; target < n * n; ++target) {
      Pair<Integer, Integer> pair = nextGrid(grid, i, j, target);
      final int x = pair.getKey();
      final int y = pair.getValue();
      if (x == -1 && y == -1)
        return false;
      // Move (x, y) to (i, j).
      i = x;
      j = y;
    }

    return true;
  }

  private static final int[][] dirs = {{-2, 1}, {-1, 2}, {1, 2},   {2, 1},
                                       {2, -1}, {1, -2}, {-1, -2}, {-2, -1}};

  // Returns (x, y), where grid[x][y] == target if (i, j) can reach target.
  private Pair<Integer, Integer> nextGrid(int[][] grid, int i, int j, int target) {
    final int n = grid.length;
    for (int[] dir : dirs) {
      final int x = i + dir[0];
      final int y = j + dir[1];
      if (x < 0 || x >= n || y < 0 || y >= n)
        continue;
      if (grid[x][y] == target)
        return new Pair<>(x, y);
    }
    return new Pair<>(-1, -1);
  }
}
// code provided by PROGIEZ

2596. Check Knight Tour Configuration LeetCode Solution in Python

class Solution:
  def checkValidGrid(self, grid: list[list[int]]) -> bool:
    if grid[0][0] != 0:
      return False

    dirs = ((1, 2), (2, 1), (2, -1), (1, -2),
            (-1, -2), (-2, -1), (-2, 1), (-1, 2))
    n = len(grid)
    i = 0
    j = 0

    def nextGrid(i: int, j: int, target: int) -> tuple[int, int]:
      """
      Returns (x, y), where grid[x][y] == target if (i, j) can reach target.
      """
      for dx, dy in dirs:
        x = i + dx
        y = j + dy
        if x < 0 or x >= n or y < 0 or y >= n:
          continue
        if grid[x][y] == target:
          return (x, y)
      return (-1, -1)

    for target in range(1, n * n):
      x, y = nextGrid(i, j, target)
      if x == -1 and y == -1:
        return False
      # Move (x, y) to (i, j).
      i = x
      j = y

    return True
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents