Count Paths That Visit Every Open Cell Exactly Once

Hard25–30 min

Topics

BacktrackingRecursionMatrix

Companies

AmazonGoogleAirbnb

You're given a grid with exactly one start cell (1), exactly one end cell (2), some obstacle cells (-1), and the rest open (0). Count the number of paths from start to end, moving one step at a time horizontally or vertically and never revisiting a cell, that pass through every single open cell along the way — not just some of them. Checking full coverage by scanning the entire grid every time the end cell is reached works, but the end cell is often reached by paths that haven't covered everything yet, and each of those arrivals pays for a full scan regardless. Counting the total number of cells that need covering once, up front, and carrying a running "how many are left" count down through the recursion turns that scan into a single number already sitting there the moment it's needed — no re-inspection of the grid required.

Test Case 1:

Input:grid = [[1,0,0,0],[0,0,0,0],[0,0,2,-1]]

Output:2

Explanation:Two different routes from the start manage to cover every open cell before reaching the end.

Test Case 2:

Input:grid = [[1,2]]

Output:1

Explanation:Two cells total, both must be visited — exactly one way to do that.

Test Case 3:

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

Output:0

Explanation:Every route that reaches the end cell does so before covering all 4 open cells — no path satisfies full coverage.

Constraints

◆1 ≤ grid.length, grid[0].length ≤ 5
◆Exactly one cell holds 1 (start) and exactly one holds 2 (end); -1 marks an obstacle, 0 an open walkable cell
◆Movement is one step at a time, horizontally or vertically, never onto an obstacle and never revisiting a cell already on the current path
◆A path only counts if it visits every non-obstacle cell exactly once before reaching the end

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Re-Scan the Whole Grid to Confirm Full Coverage

Brute

Explore outward from the start with ordinary backtracking. Whenever the end cell is reached, check whether the path actually covered every open cell by scanning the entire grid and confirming each non-obstacle cell's visited flag is set. This gets the right answer, but the end cell can be reached by many different partial paths across the search — some covering everything, most not — and every single arrival re-scans the whole grid from scratch to find out which case it is.

TimeO(3^(cells) · cells)

SpaceO(cells)

Java

Try it out

class Solution {
    public int countFullCoveragePaths(int[][] grid) {
        int n = grid.length, m = grid[0].length;
        int sr = 0, sc = 0;
        boolean[][] visited = new boolean[n][m];
        for (int r = 0; r < n; r++) {
            for (int c = 0; c < m; c++) {
                if (grid[r][c] == 1) { sr = r; sc = c; }
            }
        }
        int[] count = new int[1];
        dfs(grid, sr, sc, visited, count);
        return count[0];
    }

    private void dfs(int[][] grid, int r, int c, boolean[][] visited, int[] count) {
        int n = grid.length, m = grid[0].length;
        if (r < 0 || r >= n || c < 0 || c >= m || visited[r][c] || grid[r][c] == -1) return;
        if (grid[r][c] == 2) {
            if (allVisited(grid, visited)) count[0]++;
            return;
        }
        visited[r][c] = true;
        dfs(grid, r + 1, c, visited, count);
        dfs(grid, r - 1, c, visited, count);
        dfs(grid, r, c + 1, visited, count);
        dfs(grid, r, c - 1, visited, count);
        visited[r][c] = false;
    }

    private boolean allVisited(int[][] grid, boolean[][] visited) {
        int n = grid.length, m = grid[0].length;
        for (int r = 0; r < n; r++) {
            for (int c = 0; c < m; c++) {
                if (grid[r][c] != -1 && !visited[r][c] && grid[r][c] != 2) return false;
            }
        }
        return true;
    }
}

Optimal — Track a Remaining-Cells Counter

Optimal

Count the total number of non-obstacle cells once, up front. Carry a remaining count down through the recursion, one lower at every step taken. When the end cell is reached, full coverage is simply remaining == 1 — the end cell itself is the last one left to account for. No grid scan is ever needed: every arrival at the end cell already carries the exact number that answers "was everything covered," computed incrementally as the path was built rather than re-derived by inspection afterward.

TimeO(3^(cells))