Similar Problems
Similar Problems not available
Unique Paths Iii  Leetcode Solution
Companies:
LeetCode: Unique Paths Iii Leetcode Solution
Difficulty: Hard
Topics: matrix backtracking bitmanipulation array
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:
 (0,0), (0,1), (0,2), (0,3), (1,3), (1,2), (1,1), (1,0), (2,0), (2,1), (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 (DepthFirst 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
 Initialize the count of unique paths to 0
 Traverse the grid and calculate the count of empty cells and the starting point
 Initialize the visited array of size m x n, and mark all obstacles as visited
 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
 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
 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 worstcase 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.
Unique Paths Iii Solution Code
1