You are given a 2D array grid of size m x n, and an integer k. There are k cells in grid containing the values from 1 to k exactly once, and the rest of the cells have a value 0.
You can start at any cell, and move from a cell to its neighbors (up, down, left, or right). You must find a path in grid which:
grid exactly once.k in order.Return a 2D array result of size (m * n) x 2, where result[i] = [xi, yi] represents the ith cell visited in the path. If there are multiple such paths, you may return any one.
If no such path exists, return an empty array.
Example 1:
Input: grid = [[0,0,0],[0,1,2]], k = 2
Output: [[0,0],[1,0],[1,1],[1,2],[0,2],[0,1]]
Explanation:
Example 2:
Input: grid = [[1,0,4],[3,0,2]], k = 4
Output: []
Explanation:
There is no possible path that satisfies the conditions.
Constraints:
1 <= m == grid.length <= 51 <= n == grid[i].length <= 51 <= k <= m * n0 <= grid[i][j] <= kgrid contains all integers between 1 and k exactly once.Problem Overview: Sequential Grid Path Cover asks you to determine whether a grid can be traversed so that cells are visited in a strict sequence while forming a valid path across adjacent positions. You must follow grid adjacency rules and ensure every required step in the sequence is covered exactly once.
Approach 1: Backtracking DFS (Brute Force) (Time: O((mn)!), Space: O(mn))
The most direct approach uses recursive recursion with depth‑first search. Start from the cell that matches the first element of the sequence and explore all four directions in the matrix. Track visited cells so the path never revisits the same position. This brute force search enumerates every possible path that could match the sequence. It demonstrates the core idea clearly, but factorial growth makes it impractical once the grid size increases.
Approach 2: State Compression + DFS (Time: O((mn) * 2^(mn)), Space: O(2^(mn)))
An optimized strategy uses DFS with state compression. Instead of tracking visited cells using a full structure, represent the visited state as a bitmask where each bit corresponds to a cell index in the grid. During DFS, the state becomes (row, col, mask), meaning the current position and which cells have already been used in the path. Memoization avoids recomputing the same state multiple times. Each transition checks adjacent cells and updates the bitmask with a bitwise OR. This significantly prunes repeated exploration and works well when the grid is small enough for bitmask representation.
Bitmasking pairs naturally with array indexing because each grid coordinate maps to a single bit position. Combined with memoized DFS, the algorithm only explores unique states instead of all permutations of paths.
Recommended for interviews: Interviewers typically expect the state compression + DFS solution. Showing the brute force DFS first demonstrates you understand the search space and constraints of the grid traversal. Transitioning to bitmask state compression shows optimization skills and knowledge of dynamic state representation, which is the key technique used to handle exponential path exploration efficiently.
Note that the matrix size does not exceed 6 times 6, so we can use state compression to represent the visited cells. We can use an integer st to represent the visited cells, where the i-th bit being 1 means cell i has been visited, and 0 means it has not been visited.
Next, we iterate through each cell as a starting point. If the cell is 0 or 1, we start a depth-first search (DFS) from that cell. In the DFS, we add the current cell to the path and mark it as visited. Then, we check the value of the current cell. If it equals v, we increment v by 1. Next, we try to move in four directions to adjacent cells. If the adjacent cell has not been visited and its value is 0 or v, we continue the DFS.
If the DFS successfully finds a complete path, we return that path. If a complete path cannot be found, we backtrack, undo the visit mark for the current cell, and try other directions.
The time complexity is O(m^2 times n^2), and the space complexity is O(m times n), where m and n are the number of rows and columns of the matrix, respectively.
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking DFS (Brute Force) | O((mn)!) | O(mn) | Useful for understanding the path search logic or when the grid size is extremely small |
| State Compression + DFS | O((mn) * 2^(mn)) | O(2^(mn)) | Best general solution for small to medium grids where visited states can be encoded with a bitmask |
Sequential Grid Path Cover • Owen Wu • 8 views views
Practice Sequential Grid Path Cover with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor