Unique Paths Iii - Leetcode Solution

Problem statement: You are given an m x n integer array grid where:

• Start is a coordinate in the grid. Each move consists of moving one space in the north, east, south, or west direction. You can only move to a cell that is not blocked.

• An empty cell is marked with the value 0.

• A cell with an obstacle is marked with -1.

• Return the number of unique paths from start to finish such that:

  • You can take any path in any order.
  • The start and the finish cells are not blocked.
  • If a cell is visited, then it must be visited exactly once.

Input: grid = [[1,0,0,0],[0,0,0,0],[0,0,2,-1]] Output: 2 Explanation: We have the following two paths:

1. (0,0), (0,1), (0,2), (0,3), (1,3), (1,2), (1,1), (1,0), (2,0), (2,1), (2,2)
2. (0,0), (1,0), (2,0), (2,1), (1,1), (1,2), (0,2), (0,3), (1,3), (2,3)

Solution:

Approach:

We need to find a path from the start to the end point. There can be many paths that may lead to the end point, but all those paths should be unique, which means that each cell can be visited only once. We will use DFS (Depth-First Search) to check all possible paths, and we will keep a count of all unique paths that can lead us to the end. We will start from the starting point and explore all nearby cells by considering four possible directions (north, east, south, west). If we find the end point, we will increment the count of unique paths. Additionally, to consider that all cells are visited exactly once, we need to use a visited array to mark the already visited cells. We will also keep track of the count of empty cells and the starting point to calculate the total number of unique paths.

Algorithm:

Let m be the number of rows and n be the number of columns in the grid

1. Initialize the count of unique paths to 0
2. Traverse the grid and calculate the count of empty cells and the starting point
3. Initialize the visited array of size m x n, and mark all obstacles as visited
4. Call the recursive DFS function with the following parameters:
   • x: row of the current cell
   • y: column of the current cell
   • empty: count of empty cells
5. Inside the DFS function:
   • Base case: if the current cell is the end point, check if all cells are visited exactly once, and if they are, then increment the count of unique paths
   • Recursive case: visit all possible directions (north, east, south, west) and increment the visited count for each visited cell
6. Return the count of unique paths

Pseudo code:

function uniquePathsIII(grid: number[][]): number { let unique: number = 0; let empty: number = 0; let m: number = grid.length; let n: number = grid[0].length; let startRow: number; let startCol: number; let visited: boolean[][] = new Array(m).fill(false).map(() => new Array(n).fill(false));

// Traverse the grid to calculate the count of empty cells and the starting point
for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
        if (grid[i][j] === 0) {
            empty++;
        } else if (grid[i][j] === 1) {
            startRow = i;
            startCol = j;
        }
    }
}

// Initialize visited array and mark obstacles as visited
for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
        if (grid[i][j] === -1) {
            visited[i][j] = true;
        }
    }
}

// Recursive DFS function to traverse the grid and count unique paths
function DFS(x: number, y: number, visitedCount: number) {
    // Base case: if the current cell is the end point, check if all cells are visited exactly once, and if they are, then increment the count of unique paths
    if (grid[x][y] === 2) {
        if (visitedCount === empty + 1) {
            unique++;
        }
        return;
    }
    // Recursive case: visit all possible directions (north, east, south, west) and increment the visited count for each visited cell
    let directions: number[][] = [[-1, 0], [0, 1], [1, 0], [0, -1]];
    for (let dir of directions) {
        let newX: number = x + dir[0];
        let newY: number = y + dir[1];
        if (newX >= 0 && newX < m && newY >= 0 && newY < n && !visited[newX][newY]) {
            visited[newX][newY] = true;
            DFS(newX, newY, visitedCount + 1);
            visited[newX][newY] = false;
        }
    }
}

// Call the recursive DFS function with the starting point and starting visited count
visited[startRow][startCol] = true;
DFS(startRow, startCol, 1);

return unique;

}

Time Complexity: O(3^(m * n))

• During the DFS call, for each cell, we can make three possible moves (excluding the visited cells and obstacle blocks). Hence, the number of possible paths will be 3 ^ (m * n), which is the maximum possible paths.
• But, as the number of empty cells will always be less than (m * n), the actual time complexity will be less than this worst-case scenario.

Space Complexity: O(m x n)

• We need to use the visited array, and its size will be m x n.
• Additionally, we need to use recursive space for the DFS function.

1