Sequential grid path cover

Array Recursion Matrix

59.8% acceptance

Mar 31, 2026

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.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn find_path(grid: Vec<Vec<i32>>, k: i32) -> Vec<Vec<i32>> {
    let m = grid.len();
    let n = grid[0].len();
    let total = m * n;
    let k = k as usize;
    
    // Find positions of values 1..=k
    let mut checkpoints = vec![(0usize, 0usize); k + 1];
    for i in 0..m {
      for j in 0..n {
        if grid[i][j] > 0 {
          checkpoints[grid[i][j] as usize] = (i, j);
        }
      }
    }
    
    // Backtracking: find Hamiltonian path visiting all cells, 
    // visiting checkpoint 1, then 2, ..., then k in order.
    let mut visited = vec![vec![false; n]; m];
    let mut path = Vec::with_capacity(total);
    let dirs = [(0i32, 1i32), (0, -1), (1, 0), (-1, 0)];
    
    fn backtrack(
      r: usize, c: usize, 
      visited: &mut Vec<Vec<bool>>, 
      path: &mut Vec<Vec<i32>>,
      next_checkpoint: usize,
      checkpoints: &[(usize, usize)],
      grid: &Vec<Vec<i32>>,
      m: usize, n: usize, total: usize, k: usize,
      dirs: &[(i32, i32)],
    ) -> bool {
      visited[r][c] = true;
      path.push(vec![r as i32, c as i32]);
      
      let mut next_cp = next_checkpoint;
      if next_cp <= k && checkpoints[next_cp] == (r, c) {
        next_cp += 1;
      }
      
      if path.len() == total {
        // Must have visited all checkpoints
        if next_cp > k {
          return true;
        }
        visited[r][c] = false;
        path.pop();
        return false;
      }
      
      for &(dr, dc) in dirs {
        let nr = r as i32 + dr;
        let nc = c as i32 + dc;
        if nr >= 0 && nr < m as i32 && nc >= 0 && nc < n as i32 {
          let nr = nr as usize;
          let nc = nc as usize;
          if !visited[nr][nc] {
            // Pruning: if next checkpoint hasn't been reached yet,
            // don't skip it (can't visit a later checkpoint before it).
            // Check if the cell we're about to visit has a checkpoint
            // number that's > next_cp (meaning we'd visit it out of order)
            // Actually, we only block if the cell IS a checkpoint with 
            // number < next_cp (already visited, fine) or > next_cp+1 
            // and IS the next checkpoint... Actually the constraint is 
            // we must visit 1,2,...,k in order. So if cell (nr,nc) has 
            // value v where v <= k, then v must equal next_cp or we 
            // can visit it later (when it's the right turn).
            // No special blocking needed - the checkpoint tracking handles it.
            
            if backtrack(nr, nc, visited, path, next_cp, checkpoints, grid, m, n, total, k, dirs) {
              return true;
            }
          }
        }
      }
      
      visited[r][c] = false;
      path.pop();
      false
    }
    
    // Try starting from every cell
    for r in 0..m {
      for c in 0..n {
        if backtrack(r, c, &mut visited, &mut path, 1, &checkpoints, &grid, m, n, total, k, &dirs) {
          return path;
        }
      }
    }
    
    vec![]
  }
}