Skip to main content
Talentd

Sequential Grid Path Cover - Solution & Explanation

MediumPremiumFree on FleetCodeArrayRecursionMatrix12 min read
Practice this problem

Problem Statement

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:

  • Visits each cell in grid exactly once.
  • Visits the cells with values from 1 to 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 <= 5
  • 1 <= n == grid[i].length <= 5
  • 1 <= k <= m * n
  • 0 <= grid[i][j] <= k
  • grid contains all integers between 1 and k exactly once.

Approach Overview

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.

Solution

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen 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 + DFSO((mn) * 2^(mn))O(2^(mn))Best general solution for small to medium grids where visited states can be encoded with a bitmask

Video Solution

Sequential Grid Path Cover • Owen Wu • 8 views views

Frequently Asked Questions

Is Sequential Grid Path Cover easy or hard?
Sequential Grid Path Cover is considered a medium difficulty problem. The traversal logic is straightforward, but recognizing when to apply bitmask state compression and memoized DFS is the main challenge.
Sequential Grid Path Cover Python/Java solution
Most implementations use recursive DFS with a bitmask to represent visited cells. The same logic translates directly across Python, Java, C++, Go, and TypeScript by mapping each grid cell to a bit index and caching DFS states.
How to solve Sequential Grid Path Cover in O(n)?
A strict O(n) solution generally does not exist because the problem explores combinations of grid paths. The optimal practical approach is DFS with state compression, which reduces repeated work using memoized bitmask states and runs in O((mn) * 2^(mn)).
What is the best approach for Sequential Grid Path Cover?
The most effective solution uses DFS with state compression. Each visited configuration is encoded as a bitmask representing which grid cells are already included in the path. The DFS state becomes (row, column, mask), and memoization prevents recomputing identical states. This reduces redundant exploration compared to plain backtracking.
Is Sequential Grid Path Cover asked at Google/Amazon/Meta?
Grid path traversal and state compression problems are common in interviews at companies like Google, Amazon, and Meta. Variants involving Hamiltonian paths, grid traversal with constraints, or bitmask DFS appear frequently in onsite algorithm rounds.
What data structure is used in Sequential Grid Path Cover?
The solution mainly relies on recursion with depth‑first search, a bitmask integer for state compression, and a memoization map or array to cache visited states. The grid itself is typically represented using a 2D array or matrix.
What is the time complexity of Sequential Grid Path Cover?
The optimized state compression DFS runs in O((mn) * 2^(mn)) time where m and n are grid dimensions. Each grid cell can appear in a bitmask state, and DFS transitions to neighboring cells. Space complexity is O(2^(mn)) for memoization of visited states.

Ready to solve this problem?

Practice Sequential Grid Path Cover with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays