Unique Paths III - Practice Coding Problems

Unique Paths III - Problem

You are given an m x n integer array grid where grid[i][j] could be:

1 representing the starting square. There is exactly one starting square.
2 representing the ending square. There is exactly one ending square.
0 representing empty squares we can walk over.
-1 representing obstacles that we cannot walk over.

Return the number of 4-directional walks from the starting square to the ending square, that walk over every non-obstacle square exactly once.

Input & Output

Example 1 — Basic 3x3 Grid

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

› Output: 2

💡 Note: We have 7 walkable squares (including start and end). Two valid paths exist: 1→0→0→0→0→0→2 going around the obstacle in different ways.

Example 2 — Small Grid with Obstacle

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

› Output: 4

💡 Note: All 8 squares are walkable. Multiple paths exist from start (1) to end (2) visiting all squares exactly once.

Example 3 — No Valid Path

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

› Output: 0

💡 Note: Start at (0,1) with value 1, end at (1,0) with value 2. Only 4 squares total, but impossible to visit all and reach end due to grid layout.

Constraints

m == grid.length
n == grid[i].length
1 ≤ m, n ≤ 20
1 and 2 appear exactly once in grid

Visualization

Tap to expand

Understanding the Visualization

Input Grid

Grid with start (1), end (2), walkable (0), and obstacles (-1)

Path Exploration

Use backtracking to try all possible paths

Count Valid Paths

Count paths that visit all walkable squares and reach the end

Key Takeaway

🎯 Key Insight: Use backtracking to systematically try all paths while tracking visited squares

Asked in

G Google 15 a Amazon 12 M Microsoft 8 f Facebook 6

The key insight is to use backtracking with state restoration to systematically explore all possible paths from start to end while ensuring every walkable square is visited exactly once. The optimal approach uses DFS with backtracking - mark cells as visited during exploration, then restore them when backtracking to try alternative paths. Time: O(4^(m×n)), Space: O(m×n)

Common Approaches

Approach	Time	Space	Notes
✓ Backtracking with State Restoration	O(4^(m×n))	O(m×n)	Systematically explore paths with proper state management
Brute Force DFS	O(4^(m×n))	O(m×n)	Try all possible paths using basic DFS without optimization

Backtracking with State Restoration — Algorithm Steps

Find start position and count all walkable squares
Use DFS with visited marking to explore paths
Restore state when backtracking to try alternative paths
Count paths that visit all squares exactly once

Visualization

Tap to expand

Step-by-Step Walkthrough

Mark and Explore

Mark current cell as visited, explore all 4 directions

Backtrack

When path is complete or blocked, restore original state

Try Alternatives

Continue with other unexplored directions from restored state

Code -

solution.c — C

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

int grid[20][20];
int m, n, walkableCount;

int backtrack(int row, int col, int visitedCount) {
    // Base cases
    if (row < 0 || row >= m || col < 0 || col >= n) {
        return 0;
    }
    if (grid[row][col] == -1) { // Obstacle or visited
        return 0;
    }
    
    // Reached end
    if (grid[row][col] == 2) {
        return visitedCount == walkableCount - 1 ? 1 : 0;
    }
    
    // Mark as visited
    int temp = grid[row][col];
    grid[row][col] = -1;
    
    // Explore all 4 directions
    int paths = 0;
    int directions[4][2] = {{0,1}, {1,0}, {0,-1}, {-1,0}};
    for (int i = 0; i < 4; i++) {
        paths += backtrack(row + directions[i][0], col + directions[i][1], visitedCount + 1);
    }
    
    // Restore state
    grid[row][col] = temp;
    
    return paths;
}

int solution() {
    int startRow = 0, startCol = 0;
    walkableCount = 0;
    
    // Find start position and count walkable squares
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 1) {
                startRow = i;
                startCol = j;
                walkableCount++;
            } else if (grid[i][j] == 2 || grid[i][j] == 0) {
                walkableCount++;
            }
        }
    }
    
    return backtrack(startRow, startCol, 0);
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Simple parsing for 2D array
    char *ptr = line + 1; // Skip first '['
    m = 0;
    
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            n = 0;
            while (*ptr && *ptr != ']') {
                if (*ptr == '-' || (*ptr >= '0' && *ptr <= '9')) {
                    grid[m][n] = atoi(ptr);
                    n++;
                    while (*ptr && *ptr != ',' && *ptr != ']') ptr++;
                } else {
                    ptr++;
                }
            }
            m++;
        }
        ptr++;
    }
    
    printf("%d\n", solution());
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(4^(m×n))

In worst case, we explore 4 directions from each of m×n cells

✓ Linear Growth

Space Complexity

O(m×n)

Recursion stack depth up to m×n plus grid space

⚡ Linearithmic Space

85.0K Views

Medium Frequency

~25 min Avg. Time

2.8K 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 State Restoration — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler