LeetCode 3565 - Sequential Grid Path Cover

The problem asks us to find a path that visits every cell of a given m x n grid exactly once while visiting certain numbered cells in a specified order. Specifically, the grid contains integers from 1 to k in exactly one cell each, and the rest of the cells are zeros.

leetcodemediumarrayrecursionmatrix

LeetCode Problem 3565

Difficulty: 🟡 Medium
Topics: Array, Recursion, Matrix

Solution

Problem Understanding

The problem asks us to find a path that visits every cell of a given m x n grid exactly once while visiting certain numbered cells in a specified order. Specifically, the grid contains integers from 1 to k in exactly one cell each, and the rest of the cells are zeros. The path can start at any cell, and each step must move to a neighboring cell (up, down, left, right). The output should be the list of coordinates visited in the path, or an empty array if no valid path exists.

Key points to note include that the grid is small (1 <= m, n <= 5), which allows exhaustive search approaches, and that every number from 1 to k must be visited in order. Edge cases could include grids where no sequential path exists or where numbers are positioned in a way that forces backtracking.

Approaches

The brute-force approach would involve generating all possible permutations of cells in the grid and checking each one to see if it satisfies the sequential number constraint and adjacency requirement. While this guarantees correctness, it is computationally infeasible, as the number of permutations of an m x n grid grows factorially ((m*n)!). Even with m=n=5, (25)! is astronomically large.

The optimal approach leverages backtracking with pruning. We use the following observations: we must follow the sequence from 1 to k, and each step must be to a neighboring unvisited cell. By recursively attempting valid moves and backtracking when a dead end is reached, we can systematically explore all possible paths while immediately discarding invalid paths. This significantly reduces the search space compared to brute force.

Approach Time Complexity Space Complexity Notes
Brute Force O((m*n)!) O(m*n) Generates all permutations and checks adjacency and sequence; infeasible for m*n > 9
Backtracking O((m_n) * 4^(m_n)) O(m*n) Explores all valid paths recursively, pruning dead ends early

Algorithm Walkthrough

  1. Locate Numbered Cells: Create a mapping from each number 1..k to its coordinates in the grid for quick access. This helps enforce the sequential constraint efficiently.
  2. Initialize Visited Grid: Maintain a boolean grid to track which cells have already been visited.
  3. Recursive Backtracking: Start from any cell and recursively attempt to move to unvisited neighbors. When a numbered cell is encountered, check that it matches the expected sequential number.
  4. Path Recording: Keep track of the sequence of visited cells in a list. When all cells have been visited and all numbers 1..k were seen in order, record the path as the solution.
  5. Pruning: If a step leads to a numbered cell out of order or there are no valid moves left, backtrack immediately.
  6. Return Result: If a valid path is found, return it. Otherwise, return an empty array.

Why it works: The backtracking algorithm guarantees that every cell is visited exactly once and that numbered cells are visited in order because we enforce both constraints recursively. Pruning ensures that invalid paths are never fully explored, keeping the search efficient.

Python Solution

from typing import List

class Solution:
    def findPath(self, grid: List[List[int]], k: int) -> List[List[int]]:
        m, n = len(grid), len(grid[0])
        number_pos = {}
        for i in range(m):
            for j in range(n):
                if grid[i][j] > 0:
                    number_pos[grid[i][j]] = (i, j)
        
        visited = [[False]*n for _ in range(m)]
        path = []

        def dfs(x: int, y: int, next_num: int) -> bool:
            if visited[x][y]:
                return False
            if grid[x][y] == next_num:
                next_num += 1

            visited[x][y] = True
            path.append([x, y])

            if len(path) == m*n and next_num == k+1:
                return True

            for dx, dy in [(-1,0),(1,0),(0,-1),(0,1)]:
                nx, ny = x+dx, y+dy
                if 0 <= nx < m and 0 <= ny < n and not visited[nx][ny]:
                    if dfs(nx, ny, next_num):
                        return True

            visited[x][y] = False
            path.pop()
            return False

        for i in range(m):
            for j in range(n):
                if dfs(i, j, 1):
                    return path
        return []

Explanation: The solution first records positions of all numbered cells. The recursive dfs function attempts to visit all neighboring cells, updating the sequential number next_num whenever a numbered cell is encountered. If a full path covering all cells is found while visiting numbers in order, it returns immediately. Backtracking ensures all alternative paths are explored if a dead end occurs.

Go Solution

func findPath(grid [][]int, k int) [][]int {
    m, n := len(grid), len(grid[0])
    numberPos := make(map[int][2]int)
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if grid[i][j] > 0 {
                numberPos[grid[i][j]] = [2]int{i, j}
            }
        }
    }

    visited := make([][]bool, m)
    for i := range visited {
        visited[i] = make([]bool, n)
    }

    var path [][]int

    var dfs func(x, y, nextNum int) bool
    dfs = func(x, y, nextNum int) bool {
        if visited[x][y] {
            return false
        }
        if grid[x][y] == nextNum {
            nextNum++
        }

        visited[x][y] = true
        path = append(path, []int{x, y})

        if len(path) == m*n && nextNum == k+1 {
            return true
        }

        dirs := [][2]int{{-1,0},{1,0},{0,-1},{0,1}}
        for _, d := range dirs {
            nx, ny := x+d[0], y+d[1]
            if nx >= 0 && nx < m && ny >= 0 && ny < n && !visited[nx][ny] {
                if dfs(nx, ny, nextNum) {
                    return true
                }
            }
        }

        visited[x][y] = false
        path = path[:len(path)-1]
        return false
    }

    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if dfs(i, j, 1) {
                return path
            }
        }
    }
    return [][]int{}
}

Go-specific notes: The Go implementation mirrors the Python logic closely. Slices are used for path and visited structures. Slicing path for backtracking avoids memory leaks, and Go arrays handle integer pairs efficiently.

Worked Examples

Example 1:

Input: [[0,0,0],[0,1,2]], k=2

Starting at [0,0], DFS proceeds:

Step Current Cell Next Num Path
1 [0,0] 1 [[0,0]]
2 [1,0] 1 [[0,0],[1,0]]
3 [1,1] 1->2 [[0,0],[1,0],[1,1]]
4 [1,2] 2->3 [[0,0],[1,0],[1,1],[1,2]]
5 [0,2] 3 [[0,0],[1,0],[1,1],[1,2],[0,2]]
6 [0,1] 3 [[0,0],[1,0],[1,1],[1,2],[0,2],[0,1]]

Path complete, solution found.

Example 2:

Input: [[1,0,4],[3,0,2]], k=4

DFS explores all possibilities, but sequential constraints cannot be satisfied. Returns [].

Complexity Analysis

Measure Complexity Explanation
Time O((m*n)_4^(m_n)) Each cell may attempt 4 neighbors recursively; exponential in grid size, but feasible due to m,n <= 5
Space O(m*n) visited grid and path array, both O(m*n)

The recursion depth is at most m*n, and backtracking ensures that only valid paths are explored, so the algorithm remains practical for the given constraints.

Test Cases

# Provided examples
assert Solution().findPath([[0,0,0],[0,1,2]], 2) != []  # path exists
assert Solution().findPath([[1,0,4],[3,0,2]], 4) == []  # no valid path

# Edge cases
assert Solution().findPath([[1]], 1) == [[0,0]]

The problem gives, in which case the algorithm correctly returns an empty result.