3565. Sequential Grid Path Cover 🔒

Problem Description

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 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] = [x_i, y_i] represents the i-th 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.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

Since the grid has cells with special numbers 1, 2, ..., k that must be visited in order, the path needs to not only visit every cell once (like a Hamiltonian path) but also respect the sequence of these special cells. The grid is small, so we can try every possible path using DFS and mark visited cells efficiently, for example with bitmasking. The main idea is to start from any possible cell (0 or 1), try to walk through the grid one cell at a time, always choosing the next unvisited cell, and make sure that we step on numbered cells (1, 2, ..., k) in order. If a path successfully visits all cells exactly once and respects the required order, we've found a valid solution; otherwise, we backtrack and try other options.

Solution Approach

The implementation uses a combination of state compression (bitmasking) and depth-first search (DFS) to efficiently explore all possible paths on the grid.

State Compression: The grid has at most 6 x 6 cells, so we can use an integer to represent which cells have been visited. For example, using the formula i * n + j (where i and j are row and column indices), we map each cell to a unique bit in an integer. If the bit is set (1), the cell has been visited.
Depth-First Search (DFS): We try starting from every cell in the grid that is either empty (0) or contains the number 1. For each such starting cell, we begin a DFS that tries to visit all cells exactly once. During the DFS, we:
- Add the current cell to the path.
- Mark the cell as visited in our bitmask.
- If the current cell contains the next expected value in the sequence (v), we increment v (so we look for the next numbered cell in order).
- Move in each of the four directions (up, down, left, right), continuing the DFS for any adjacent cell that is unvisited and is either 0 or the next value we need to visit.
Checking for Success and Backtracking: If our path contains all m * n cells, we've found a valid solution. Otherwise, we backtrack: we remove the last cell from the path and unmark it as visited.
Returning the Result: If a valid path is found, it is returned immediately. If no valid Hamiltonian path exists that meets the special visiting order, an empty array is returned.

Overall, the approach efficiently enumerates all possible paths using DFS, leverages bitmasking to keep track of visits, and enforces the order of special cells through value comparison and incrementing.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's use a 2x3 grid as an example and set k = 2:

grid = [
  [0, 1, 0],
  [0, 2, 0]
]

The cells with 1 and 2 must be visited in that order (1 before 2).
We need to find a path that visits every cell exactly once and steps on 1 before 2.

Step 1: Identify Possible Starting Points

We can start from any cell with 0 or 1. Suppose we start at (0, 1), which contains 1.

Step 2: Keep Track of State

We use a bitmask to indicate which cells we've visited. For a 2x3 grid, that's 6 bits: Bit 0 = (0,0), Bit 1 = (0,1), ..., Bit 5 = (1,2).

Our initial bitmask after starting at (0,1): visited = 0b000010 (or decimal 2).

Current expected number to step on: next_required = 2 (since we've visited 1).

Path so far: [(0,1)]

Step 3: Run DFS Recursively

From (0,1), we have two valid neighbors:

Up: Not valid (out of bounds)
Down: (1,1) (contains 2), which is the next required number.
Left: (0,0) (contains 0)
Right: (0,2) (contains 0)

Since we must visit numbered cells in order, we must step on (1,1) before any cells holding higher numbers.

Let's go down to (1,1) (contains 2):

Update visited = 0b010010 (bits for (0,1) and (1,1) set).
Increment next_required to 3 (all special numbers covered for k = 2).
Add (1,1) to path: [(0,1), (1,1)]

Now, we continue from (1,1) to its neighbors that are unvisited:

Up: (0,1) already visited
Down: (2,1) out of bounds
Left: (1,0) (contains 0)
Right: (1,2) (contains 0)

Suppose we move to (1,0):

Update visited: 0b010110
Add (1,0) to path.

Continue to (1,2):

From (1,0) right to (1,2) (only unvisited neighbor), update visited.
Continue to (0,2) (unvisited, add to path).
Finally, move to (0,0) (the last unvisited cell).

Completed path: [(0,1), (1,1), (1,0), (1,2), (0,2), (0,0)]

Step 4: All Cells Visited

The path visits all 6 cells, and steps on 1 first, then 2 as mandated. The bitmask is full (0b111111).

Step 5: Return the Path

Return the path coordinates: [[0,1], [1,1], [1,0], [1,2], [0,2], [0,0]]

This process illustrates how the algorithm:

Picks a starting cell.
Uses bitmasking to track visited cells.
Recursively explores moves, backtracking as needed.
Enforces the rule to visit special numbers in order.

Alternate valid paths could be found by trying other moves or starting points, but each must step on 1 before 2 and visit all cells exactly once.

Solution Implementation

1from typing import List
2
3class Solution:
4    def findPath(self, grid: List[List[int]], k: int) -> List[List[int]]:
5        # Helper: maps grid cell i,j to an integer bit position
6        def cell_id(row: int, col: int) -> int:
7            return row * num_cols + col
8
9        # Depth-First Search to find valid path
10        def dfs(row: int, col: int, required_val: int) -> bool:
11            nonlocal visited_mask
12            path.append([row, col])
13
14            # If we have visited all cells, return success
15            if len(path) == num_rows * num_cols:
16                return True
17
18            # Mark current cell as visited in the bitmask
19            visited_mask |= 1 << cell_id(row, col)
20
21            current_val = required_val
22            # If the cell matches the required value, increment for next step
23            if grid[row][col] == required_val:
24                current_val += 1
25
26            # Directions: right, down, left, up
27            directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]
28            for dr, dc in directions:
29                next_row, next_col = row + dr, col + dc
30                # Check bounds, not visited, and next cell is valid (0 or current required value)
31                if (
32                    0 <= next_row < num_rows and
33                    0 <= next_col < num_cols and
34                    (visited_mask & (1 << cell_id(next_row, next_col))) == 0 and
35                    grid[next_row][next_col] in (0, current_val)
36                ):
37                    if dfs(next_row, next_col, current_val):
38                        return True
39
40            # Backtrack: remove cell from path/visited
41            path.pop()
42            visited_mask ^= 1 << cell_id(row, col)
43            return False
44
45        num_rows, num_cols = len(grid), len(grid[0])
46        visited_mask = 0  # Bitmask for visited cells
47        path = []
48
49        # Try every cell as a starting point with value 0 or 1
50        for row in range(num_rows):
51            for col in range(num_cols):
52                if grid[row][col] in (0, 1):
53                    if dfs(row, col, 1):
54                        return path
55                    # Reset path and visited mask for next attempt
56                    path.clear()
57                    visited_mask = 0
58
59        # No valid path found
60        return []
61

1import java.util.ArrayList;
2import java.util.Arrays;
3import java.util.List;
4
5class Solution {
6    // Grid dimensions
7    private int m, n;
8    // Bitmask to record visited cells
9    private long st = 0;
10    // Result path
11    private List<List<Integer>> path = new ArrayList<>();
12    // Directions: up, right, down, left
13    private final int[] dirs = {-1, 0, 1, 0, -1};
14
15    // Converts 2D grid coordinate to 1D index for bitmasking
16    private int f(int row, int col) {
17        return row * n + col;
18    }
19
20    /**
21     * Backtracking DFS to find a valid path covering all cells.
22     * @param row current row
23     * @param col current column
24     * @param expectedValue expected value for the next non-zero cell
25     * @param grid given grid
26     * @return true if a valid path is found
27     */
28    private boolean dfs(int row, int col, int expectedValue, int[][] grid) {
29        // Add current cell to current path
30        path.add(Arrays.asList(row, col));
31        // If path covers all cells, return success
32        if (path.size() == m * n) {
33            return true;
34        }
35        // Mark current cell as visited
36        st |= 1L << f(row, col);
37        // If current cell matches expected value, increment it for future expected values
38        if (grid[row][col] == expectedValue) {
39            expectedValue++;
40        }
41        // Explore four directions
42        for (int d = 0; d < 4; d++) {
43            int dx = dirs[d], dy = dirs[d + 1];
44            int newRow = row + dx, newCol = col + dy;
45            // Check boundaries and if the next cell is unvisited and valid for transition
46            if (0 <= newRow && newRow < m && 0 <= newCol && newCol < n
47                && (st & (1L << f(newRow, newCol))) == 0
48                && (grid[newRow][newCol] == 0 || grid[newRow][newCol] == expectedValue)) {
49                // Recursively search from the next cell
50                if (dfs(newRow, newCol, expectedValue, grid)) {
51                    return true;
52                }
53            }
54        }
55        // Backtrack: unmark cell and remove from path
56        path.remove(path.size() - 1);
57        st ^= 1L << f(row, col);
58        return false;
59    }
60
61    /**
62     * Public method to find a valid path as per constraints.
63     * @param grid input grid
64     * @param k not used (can be removed or kept for compatibility)
65     * @return path as list of [row, col] pairs, or empty list if not found
66     */
67    public List<List<Integer>> findPath(int[][] grid, int k) {
68        m = grid.length;
69        n = grid[0].length;
70        // Try every cell as a starting point if it's 0 or 1
71        for (int i = 0; i < m; i++) {
72            for (int j = 0; j < n; j++) {
73                if (grid[i][j] == 0 || grid[i][j] == 1) {
74                    if (dfs(i, j, 1, grid)) {
75                        return path;
76                    }
77                    // Reset state for next starting cell
78                    path.clear();
79                    st = 0;
80                }
81            }
82        }
83        // No valid path found
84        return List.of();
85    }
86}
87

1class Solution {
2    int rows, cols;
3    unsigned long long state = 0; // Bitmask for visited cells
4    std::vector<std::vector<int>> path; // Stores the current valid path
5    int directions[5] = {-1, 0, 1, 0, -1}; // Deltas for 4-directional moves
6
7    // Flatten 2D indices to a single number for bitmasking
8    int flattenIndex(int i, int j) {
9        return i * cols + j;
10    }
11
12    // DFS search for valid path covering all cells
13    bool dfs(int i, int j, int nextValue, std::vector<std::vector<int>>& grid) {
14        path.push_back({i, j});
15        // If the path covers every cell, return true
16        if (path.size() == static_cast<size_t>(rows * cols)) {
17            return true;
18        }
19        // Mark current cell as visited
20        state |= 1ULL << flattenIndex(i, j);
21
22        // If current cell matches the expected value, increment nextValue
23        if (grid[i][j] == nextValue) {
24            nextValue += 1;
25        }
26
27        // Explore 4 directions (up, right, down, left)
28        for (int dir = 0; dir < 4; ++dir) {
29            int dx = directions[dir], dy = directions[dir + 1];
30            int x = i + dx, y = j + dy;
31            // Check bounds and if the cell is unvisited
32            if (x >= 0 && x < rows && y >= 0 && y < cols && (state & (1ULL << flattenIndex(x, y))) == 0
33                && (grid[x][y] == 0 || grid[x][y] == nextValue)) {
34                if (dfs(x, y, nextValue, grid)) {
35                    return true;
36                }
37            }
38        }
39        // Backtrack: remove current cell from path and visited state
40        path.pop_back();
41        state ^= 1ULL << flattenIndex(i, j);
42        return false;
43    }
44
45public:
46    // Entry function to find the required path
47    std::vector<std::vector<int>> findPath(std::vector<std::vector<int>>& grid, int k) {
48        rows = grid.size();
49        cols = grid[0].size();
50        // Try every cell as a starting point where value is 0 or 1
51        for (int i = 0; i < rows; ++i) {
52            for (int j = 0; j < cols; ++j) {
53                if (grid[i][j] == 0 || grid[i][j] == 1) {
54                    if (dfs(i, j, 1, grid)) {
55                        return path;
56                    }
57                    // Reset path and state to try next starting point
58                    path.clear();
59                    state = 0;
60                }
61            }
62        }
63        return {}; // Return empty path if no valid path is found
64    }
65};
66

1// Find a path in a grid such that you visit every cell exactly once.
2// The path must start on a cell with 0 or 1. You can only visit each cell once.
3// You can step onto a cell if it is 0, or if it equals the current 'value' v.
4// If current cell's value matches v, increment v.
5
6const directions = [-1, 0, 1, 0, -1]; // [dx0, dy0, dx1, dy1, ...] for 4 directions
7
8let pathResult: number[][] = [];   // Store the current path
9let visited = 0;                   // Bitmask to mark visited cells
10let rows = 0, cols = 0;            // Dimensions of grid
11
12/**
13 * Returns a unique position id for cell (i, j)
14 */
15function getPosition(i: number, j: number): number {
16    return i * cols + j;
17}
18
19/**
20 * Depth-first search to build the path.
21 * @param i Current row
22 * @param j Current column
23 * @param value Current allowed value
24 * @returns true if a valid path covering all grid cells is found
25 */
26function dfs(i: number, j: number, value: number, grid: number[][]): boolean {
27    pathResult.push([i, j]);
28
29    // If path includes all cells, return true
30    if (pathResult.length === rows * cols) {
31        return true;
32    }
33
34    // Mark (i, j) as visited
35    visited |= 1 << getPosition(i, j);
36
37    // If cell matches current required value, increment value
38    let nextValue = value;
39    if (grid[i][j] === value) {
40        nextValue += 1;
41    }
42
43    // Try all 4 directions
44    for (let d = 0; d < 4; d++) {
45        const ni = i + directions[d];
46        const nj = j + directions[d + 1];
47        const pos = getPosition(ni, nj);
48
49        // Check in bounds and not visited, and destination cell requirements
50        if (
51            ni >= 0 && ni < rows &&
52            nj >= 0 && nj < cols &&
53            (visited & (1 << pos)) === 0 &&
54            (grid[ni][nj] === 0 || grid[ni][nj] === nextValue)
55        ) {
56            if (dfs(ni, nj, nextValue, grid)) {
57                return true;
58            }
59        }
60    }
61
62    // Backtrack: unmark visited and remove last from path
63    pathResult.pop();
64    visited ^= 1 << getPosition(i, j);
65
66    return false;
67}
68
69/**
70 * Main function to find a valid path in the grid.
71 * @param grid The input grid
72 * @param k Not used in logic but included for signature completeness
73 * @returns An array of [row, col] pairs representing the path, or empty array if none exists
74 */
75function findPath(grid: number[][], k: number): number[][] {
76    rows = grid.length;
77    cols = grid[0].length;
78
79    // Try starting from every cell with value 0 or 1
80    for (let i = 0; i < rows; i++) {
81        for (let j = 0; j < cols; j++) {
82            if (grid[i][j] === 0 || grid[i][j] === 1) {
83                visited = 0;               // Reset bitmask
84                pathResult = [];           // Reset current path
85                if (dfs(i, j, 1, grid)) {  // Start DFS with initial value 1
86                    return pathResult;
87                }
88            }
89        }
90    }
91    return [];
92}
93

Time and Space Complexity

Time Complexity: The code explores all possible paths starting from every cell where grid[i][j] is 0 or 1. For each such start, it attempts a DFS to cover all m * n cells. In the worst case, the number of recursive calls can be factorial with respect to the number of cells, i.e., O((m * n)!), because each cell can only be visited once in a path, potentially generating all permutations. However, the reference answer states O(m^2 \times n^2), which may be an estimation under heuristic pruning due to constraints like early returns and only searching from certain starting points. For the raw backtracking algorithm, the true upper bound would be O((m \times n)!).
Space Complexity: The space is dominated by the recursion stack and the path list, both up to O(m \times n) for the longest possible path. Additionally, there is a bitmask st that tracks visited cells, which uses O(1) space if m * n is limited (by the size of an integer in Python), or O(m \times n) in general.
Summary in code/math format:
- Time complexity: O((m \times n)!)
- Space complexity: O(m \times n)

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan: