Watch the video solution for Sequential Grid Path Cover, a medium level problem involving Array, Recursion, Matrix. This walkthrough by Owen Wu has 8 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |