Unique Path (leetcode)

Today I want to share about some leetcode problems. Here is list of the problems:

• Unique Path
• Unique Path II
• Unique Path III

For the first and the second problem I will use a dynamic programming, and for the third problem I will use a Flood Fill algorithm.

Unique Path

There is a robot at the top-left corner of M x N grid. That robot only move right or move down. That robot wants to move to the bottom-right corner of the grid. How many possible unique paths that robot can take ?

red robot want to move to yellow star

Here is the full code.

The solve method has some parameters. Parameter x and y to determine the coordinate of the robot. Parameter m and n to determine size of the grid. And if the current position of the robot is at the right bottom of the grid (m-1, n-1), we can count that path as a unique path.

For this problem, the robot has 2 possibilities to move. It can move to the right or down. But we need to validate the moves so it won’t move outside of the grid.

This is simulation for 3 x 3 grid.

The colored circle means the overlapped sub problem.

if (x == n - 1 && y == m - 1) {
 return 1;
}

This is the base case, we need to return 1 if the robot current position is at the right bottom of the grid.

String key = String.format("%d-%d", x, y);
Integer mem = memo.get(key);
if (mem != null) {
 return mem;
}

Before we calculate the unique path, we need to check if the same sub problem already occurs before. If yes, then just return the value of memo.

int ret = 0;
if (x + 1 < n) {
 ret += solve(x + 1, y, m, n);
}
if (y + 1 < m) {
 ret += solve(x, y + 1, m, n);
}

We need to validate the possible moves so the robot position will not out of the grid. If the moves is valid, then just do recursive with smaller sub problem and add the return value to ret variable.

memo.put(key, ret);        
return ret;

Before we return the value, we need to store it in a memo variable. So when the same sub problems occur, we don’t need to calculate again.

Unique Path II

This problem is similar to the first problem, the difference is there are obstacles in the grid and the robot can’t move to the coordinate of the obstacles.

if (x == n - 1 && y == m - 1) {
 return obstacleGrid[y][x] == 0 ? 1 : 0;
}

We need to check if the right bottom of the grid is an obstacle or not. If it is an obstacle then return 0. Actually we can check the right bottom value from the start and return 0 if it is an obstacle.

int ret = 0;
if (x + 1 < n && obstacleGrid[y][x + 1] == 0) {
 ret += solve(x + 1, y, m, n, obstacleGrid);
}
if (y + 1 < m && obstacleGrid[y + 1][x] == 0) {
 ret += solve(x, y + 1, m, n, obstacleGrid);
}

There is additional validation for the robot to move. The target coordinate of the move can’t be an obstacle.

Unique Path III

This problem is a bit different with the previous two problems. We are given a 2 dimensional array. There are 4 types of square.

• 1 Represent the starting square.
• 2 Represent the ending square.
• 0 Represent empty squares (can move here).
• -1 Represent obstacles (can’t move here).

We can move to the top, bottom, right, and left. Every movable square must be visited. Find how many unique paths.

First, I will explain steps in method uniquePathsIII.

int m = grid.length;
int n = grid[0].length;

m and n is the size of the grid.

int startX = 0, startY = 0;
int totalObs = 0;
for (int i = 0; i < m; i++) {
 for (int j = 0; j < n; j++) {
  int tile = grid[i][j];
  if (tile == 1) {
   startX = j;
   startY = i;
  } else if (tile == -1) {
   totalObs++;
  }
 }
}

startX and startY are the coordinate of the start position. totalObs is the number of obstacles in the grid.

int moveNeeded= (m * n) - 1 - totalObs;

moveNeeded is the is the number of moves needed to be made before going to the target coordinate. Because all empty squares must be visited, just calculate the size of the grid and decrease it with total obstacles and 1 (start coordinate).

Steps in method dfs :

int dfs(int x, int y, int m, int n, int[][] grid, boolean[][] visited, int move, int moveNeeded)

x and y is the current coordinate. m and n is the size of the grid. Grid is the grid 😅. Visited is a 2 dimensional array that marks if the current coordinate is already visited or not. Because we just need to visit a square 1 time, we need to mark the coordinate of the square that has already been visited. move is the number of moves that has already been made. moveNeeded is the number of moves needed to be made.

int ret = 0;
visited[y][x] = true;
for (int i = 0; i < nextX.length; i++) {
 int nx = x + nextX[i];
 int ny = y + nextY[i];
 if (nx < 0 || nx >= n) continue;
 if (ny < 0 || ny >= m) continue;
 if (grid[ny][nx] == -1) continue;
 if (visited[ny][nx]) continue;
 ret += dfs(nx, ny, m, n, grid, cloneVisited(visited), move + 1, moveNeeded);
}

Everytime we visit a coordinate, we must mark visited of current coordinate. And before we go to another square, we must check if the coordinate is outside of the grid or not and validate if the coordinate already visited or not and validate if the coordinate is obstacle or not. If all the validation is pass, just do a recursive call with increasing the move variable and a new visited variable. We need to create a new visited variable because we don’t want the value of the array updated by the recursive call.

boolean[][] cloneVisited(boolean[][] visited) {
 boolean[][] ret = new boolean[visited.length][visited[0].length];
 for (int i = 0; i < visited.length; i++) {
  for (int j = 0; j < visited[0].length; j++) {
   ret[i][j] = visited[i][j];
  }
 }
 return ret;
}

This is the method for cloning the visited variable.