Check Knight Tour Configuration

Med

#2376Time: O(n^4). The outer loop runs `n*n - 1` times. For each iteration, the inner nested loops scan the grid, taking `O(n^2)` time in the worst case. This results in a total time complexity of `O(n^2 * n^2) = O(n^4)`.Space: O(1). Only a few variables are used to store the current position and loop counters.

Algorithms

Depth-First Search Breadth-First Search

Data structures

Array Matrix

Prompt

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.

Approaches

2 approaches with complexity analysis and trade-offs.

This method simulates the knight's journey step-by-step. Starting from move 0 at (0,0), it iteratively finds the location of the next move (1, 2, 3, ...) by scanning the entire grid. At each step, it verifies if the jump from the previous location to the current one is a valid knight's move.

Algorithm

1. Check if grid[0][0] is 0. If not, return false.
1. Initialize the current position (currR, currC) to (0, 0).
1. Loop through move numbers k from 1 to n*n - 1.
1. Inside the loop, perform a nested loop over the grid to find the cell (nextR, nextC) where grid[nextR][nextC] == k.
1. Validate the move from (currR, currC) to (nextR, nextC). If invalid, return false.
1. Update currR = nextR and currC = nextC.
1. If the loop completes, return true.

Walkthrough

First, it checks the starting condition: grid[0][0] must be 0. If not, the tour is invalid. It initializes the knight's current position to (0, 0). The algorithm then enters a loop that iterates from move k = 1 to n*n - 1. Inside the loop, it searches the entire n x n grid to find the coordinates (nextR, nextC) of the cell containing the value k. Once found, it calculates the difference in rows and columns between the current position and the next position: dr = abs(currR - nextR) and dc = abs(currC - nextC). It validates the move using the knight's move rule: (dr == 1 && dc == 2) || (dr == 2 && dc == 1). If the move is invalid, the function returns false. If the move is valid, it updates the current position to (nextR, nextC) and continues to the next iteration. If the loop completes without returning false, it means all n*n - 1 moves were valid, so the function returns true.

1class Solution {2    public boolean checkValidGrid(int[][] grid) {3        if (grid[0][0] != 0) {4            return false;5        }6        int n = grid.length;7        int currR = 0;8        int currC = 0;9 10        for (int k = 1; k < n * n; k++) {11            boolean foundNext = false;12            // Search for the cell with value k13            for (int r = 0; r < n; r++) {14                for (int c = 0; c < n; c++) {15                    if (grid[r][c] == k) {16                        int dr = Math.abs(currR - r);17                        int dc = Math.abs(currC - c);18                        if (!((dr == 2 && dc == 1) || (dr == 1 && dc == 2))) {19                            return false; // Invalid move20                        }21                        // Update current position for the next move22                        currR = r;23                        currC = c;24                        foundNext = true;25                        break;26                    }27                }28                if (foundNext) {29                    break;30                }31            }32        }33        return true;34    }35}

Complexity

Time

O(n^4). The outer loop runs `n*n - 1` times. For each iteration, the inner nested loops scan the grid, taking `O(n^2)` time in the worst case. This results in a total time complexity of `O(n^2 * n^2) = O(n^4)`.

Space

O(1). Only a few variables are used to store the current position and loop counters.

Trade-offs

Pros

Simple logic, easy to follow.
Requires no extra space, i.e., O(1) space complexity.

Cons

Inefficient time complexity of O(n^4) because for each of the n*n moves, it scans the entire n*n grid.
Will be very slow for larger grid sizes, though it passes for the given constraints.

This approach significantly improves performance by avoiding repeated searches. It first creates a lookup table (an array) to store the coordinates of every move number. After this one-time setup, it can retrieve the position of any move in constant time. The algorithm then iterates through the moves sequentially, using the lookup table to get the current and next positions, and verifies each move's validity.

Algorithm

1. Check if grid[0][0] is 0. If not, return false.
1. Create a positions array of size n*n to store (row, col) coordinates.
1. Iterate through the grid to populate the positions array: positions[grid[r][c]] = {r, c}.
1. Loop through move numbers i from 0 to n*n - 2.
1. Get current position (r1, c1) from positions[i] and next position (r2, c2) from positions[i+1].
1. Validate the move from (r1, c1) to (r2, c2). If invalid, return false.
1. If the loop completes, return true.

Walkthrough

The algorithm begins with the mandatory check: grid[0][0] must be 0. It then creates an auxiliary 2D array, positions, of size (n*n) x 2. This array will act as a map where positions[k] stores the (row, col) coordinates of the cell with value k. To populate this positions array, it iterates through the input grid once. For each cell (r, c), it performs the assignment: positions[grid[r][c]] = {r, c}. This entire pre-computation step takes O(n^2) time. With the positions map built, the algorithm verifies the tour. It loops from k = 0 to n*n - 2. In each iteration, it fetches the coordinates for the current move k and the next move k+1 directly from the positions array in O(1) time.

(r1, c1) = positions[k]
(r2, c2) = positions[k+1] It then checks if the move from (r1, c1) to (r2, c2) is a valid knight's move by checking if abs(r1 - r2) * abs(c1 - c2) == 2. If an invalid move is detected, it returns false. If the loop finishes, all moves are valid, and it returns true.

1class Solution {2    public boolean checkValidGrid(int[][] grid) {3        if (grid[0][0] != 0) {4            return false;5        }6 7        int n = grid.length;8        int[][] positions = new int[n * n][2];9        for (int r = 0; r < n; r++) {10            for (int c = 0; c < n; c++) {11                positions[grid[r][c]][0] = r;12                positions[grid[r][c]][1] = c;13            }14        }15 16        for (int i = 0; i < n * n - 1; i++) {17            int r1 = positions[i][0];18            int c1 = positions[i][1];19            int r2 = positions[i + 1][0];20            int c2 = positions[i + 1][1];21 22            int dr = Math.abs(r1 - r2);23            int dc = Math.abs(c1 - c2);24 25            if (!((dr == 2 && dc == 1) || (dr == 1 && dc == 2))) {26                return false;27            }28        }29 30        return true;31    }32}

Complexity

Time

O(n^2). Populating the `positions` array by iterating through the grid takes `O(n^2)`. Verifying the `n*n - 1` moves using the pre-computed positions takes another `O(n^2)`. The total complexity is dominated by these steps, resulting in `O(n^2)`.

Space

O(n^2). An auxiliary array of size `n*n` is used to store the coordinates of each move number.

Trade-offs

Pros

Highly efficient with a time complexity of O(n^2).
The logic is straightforward: build a map, then check the path.

Cons

Requires extra space of O(n^2) for the positions lookup table.

Solutions

Solution

1class Solution {2public3  boolean checkValidGrid(int[][] grid) {4    if (grid[0][0] != 0) {5      return false;6    }7    int n = grid.length;8    int[][] pos = new int[n * n][2];9    for (int i = 0; i < n; ++i) {10      for (int j = 0; j < n; ++j) {11        pos[grid[i][j]] = new int[]{i, j};12      }13    }14    for (int i = 1; i < n * n; ++i) {15      int[] p1 = pos[i - 1];16      int[] p2 = pos[i];17      int dx = Math.abs(p1[0] - p2[0]);18      int dy = Math.abs(p1[1] - p2[1]);19      boolean ok = (dx == 1 && dy == 2) || (dx == 2 && dy == 1);20      if (!ok) {21        return false;22      }23    }24    return true;25  }26}

1class Solution {2public:3  bool checkValidGrid(vector<vector<int>> &grid) {4    if (grid[0][0] != 0) {5      return false;6    }7    int n = grid.size();8    vector<pair<int, int>> pos(n * n);9    for (int i = 0; i < n; ++i) {10      for (int j = 0; j < n; ++j) {11        pos[grid[i][j]] = {i, j};12      }13    }14    for (int i = 1; i < n * n; ++i) {15      auto [x1, y1] = pos[i - 1];16      auto [x2, y2] = pos[i];17      int dx = abs(x1 - x2);18      int dy = abs(y1 - y2);19      bool ok = (dx == 1 && dy == 2) || (dx == 2 && dy == 1);20      if (!ok) {21        return false;22      }23    }24    return true;25  }26};

1class Solution:2    def checkValidGrid(self, grid: List[List[int]]) -> bool: if grid[0][0]: return False n = len(grid) pos = [None] * (n * n) for i in range(n): for j in range(n): pos[grid[i][j]] = (i, j) for (x1, y1), (x2, y2) in pairwise(pos): dx, dy = abs(x1 - x2), abs(y1 - y2) ok = (dx == 1 and dy == 2) or (dx == 2 and dy == 1) if not ok: return False return True

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem