Sequential Grid Path Cover - Practice Coding Problems

Sequential Grid Path Cover - Problem

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.

Input & Output

Example 1 — Basic 2x2 Grid

$ Input: grid = [[1,2],[3,0]], k = 3

› Output: [[0,0],[0,1],[1,0],[1,1]]

💡 Note: Start at (0,0) with value 1, move to (0,1) with value 2, then (1,0) with value 3, finally (1,1) with value 0. This visits all numbered cells 1→2→3 in order and covers all cells exactly once.

Example 2 — No Solution

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

› Output: []

💡 Note: Must visit cell with value 1 before cell with value 2, but they are positioned such that any Hamiltonian path visits 2 before 1, making a solution impossible.

Example 3 — Single Row

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

› Output: [[0,0],[0,1],[0,2],[0,3]]

💡 Note: Simple path from left to right visits 1 then 2 in correct order while covering all cells.

Constraints

1 ≤ m, n ≤ 4
1 ≤ k ≤ m × n
0 ≤ grid[i][j] ≤ k
Each value from 1 to k appears exactly once in grid

Visualization

Tap to expand

Understanding the Visualization

Input Grid

2D grid with numbered cells 1 to k and zeros

Find Path

Create path visiting all cells exactly once

Check Order

Ensure numbered cells are visited in sequence 1→2→...→k

Output Path

Return coordinates of cells in visit order

Key Takeaway

🎯 Key Insight: Use backtracking to explore Hamiltonian paths while enforcing sequential ordering constraints

Asked in

G Google 15 f Facebook 12 a Amazon 8

The key insight is to use backtracking with early constraint checking. We must visit numbered cells 1 to k in sequential order while covering all grid cells exactly once. The backtracking approach explores all possible paths but prunes branches when numbered cells are encountered out of order. Time: O(4^(m×n)), Space: O(m×n).

Common Approaches

Approach	Time	Space	Notes
✓ Backtracking with Early Pruning	O(4^(m×n))	O(m×n)	Explore paths recursively with constraint checking
Brute Force with All Paths	O((m×n)!)	O(m×n)	Generate all possible paths and check constraints

Backtracking with Early Pruning — Algorithm Steps

Start DFS from each possible starting cell
At each step, check if numbered cells are visited in order
Prune branches that violate the sequential constraint
Continue until all cells are visited or no solution exists

Visualization

Tap to expand

Step-by-Step Walkthrough

Start DFS

Begin depth-first search from a starting cell

Check Constraints

Verify numbered cells are visited in order

Prune Invalid

Backtrack when constraints are violated

Find Solution

Return first valid complete path

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define MAX_SIZE 100

int grid[MAX_SIZE][MAX_SIZE];
int result[MAX_SIZE * MAX_SIZE][2];
int path[MAX_SIZE * MAX_SIZE][2];
bool visited[MAX_SIZE][MAX_SIZE];
int m, n, k;

bool backtrack(int r, int c, int pathLen, int nextNum) {
    // Check if current cell should be a numbered cell
    if (nextNum <= k && grid[r][c] == nextNum) {
        nextNum++;
    } else if (grid[r][c] != 0 && grid[r][c] < nextNum) {
        return false; // Found numbered cell out of order
    }
    
    // If we've visited all cells
    if (pathLen == m * n) {
        if (nextNum > k) {
            for (int i = 0; i < pathLen; i++) {
                result[i][0] = path[i][0];
                result[i][1] = path[i][1];
            }
            return true;
        }
        return false;
    }
    
    // Try all four directions
    int directions[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    for (int d = 0; d < 4; d++) {
        int nr = r + directions[d][0];
        int nc = c + directions[d][1];
        if (nr >= 0 && nr < m && nc >= 0 && nc < n && !visited[nr][nc]) {
            visited[nr][nc] = true;
            path[pathLen][0] = nr;
            path[pathLen][1] = nc;
            if (backtrack(nr, nc, pathLen + 1, nextNum)) {
                return true;
            }
            visited[nr][nc] = false;
        }
    }
    return false;
}

int main() {
    // Simple parsing for demonstration
    scanf("%d %d %d", &m, &n, &k);
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &grid[i][j]);
        }
    }
    
    // Try starting from each cell
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            memset(visited, false, sizeof(visited));
            visited[i][j] = true;
            path[0][0] = i;
            path[0][1] = j;
            int nextNum = grid[i][j] == 1 ? 2 : 1;
            if (backtrack(i, j, 1, nextNum)) {
                printf("[");
                for (int p = 0; p < m * n; p++) {
                    printf("[%d,%d]", result[p][0], result[p][1]);
                    if (p < m * n - 1) printf(",");
                }
                printf("]\n");
                return 0;
            }
        }
    }
    printf("[]\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(4^(m×n))

Each cell has at most 4 neighbors, with pruning reducing the search space

✓ Linear Growth

Space Complexity

O(m×n)

Recursion stack depth and visited set

⚡ Linearithmic Space

12.5K Views

Medium Frequency

~35 min Avg. Time

432 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Backtracking with Early Pruning — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler