Leetcode — 980. Unique Paths III

The link to the problem: https://leetcode.com/problems/unique-paths-iii/

On a 2-dimensional grid, there are 4 types of squares:

  • 1 represents the starting square. There is exactly one starting square.
  • 2 represents the ending square. There is exactly one ending square.
  • 0 represents empty squares we can walk over.
  • -1 represents 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.

Example
Input: [[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),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2)

Thoughts:

If you have solved 62. Unique Paths and 63. Unique Paths II on Leetcode, you might find that both of these questions can use dynamic programming to solve it. Since there are restrictions on our moving directions and we always start from top left to bottom right in problem 62 and 63, we can use a 2D array to store the number of paths so that the number of paths to the position (i, j) will always be the aggregation of the number of paths to its top cell and its left cell.

However, you will notice that this problem is totally different than the previous two problems. Now the starting and ending positions vary in every test case, we can forward all 4 directions in each cell, and we have to walk through each cell exactly one time. It is impossible for us to use dynamic programming to solve this problem since we need to keep track of the cells that we have walked through.

Since we will always have 4 directions to head to while we are on the current cell, these 4 cells are possible to be our next step. We will try to head to all these possible cells from the current position to see if we can create new possible paths based on the current choices. And yes, this is what backtracking does — we make a choice and keep making other choices based on the choice till we cannot continue the choices, then we redo the previous choices and make another choice.

Code Logic:

Before we start to make any choices (i.e., decide which cell we are going to step on next), we should first find the starting position and the total number of cells we should traverse.

Since we need to know which cells we have visited, I will use a List to record all the visited paths. If we found the current cell is invalid, has an obstacle, or has been visited, then we should redo the choice and choose another valid cell. We will continue traversing the next possible cells until we have traversed all the cells for the current path.

Below is the 20ms code that beats 5% —

public int uniquePathsIII(int[][] grid) {
int m = grid.length, n = grid[0].length;
int[] start = new int[2];
int count = 0;//number of 0s and starting point
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
if(grid[i][j]==1)
{
start[0] = i;
start[1] = j;
}
else if(grid[i][j]==0)
count++;
}
}
return helper(grid, start[0],start[1], count+1, new ArrayList<>());
}
public int helper(int[][] grid,int i,int j, int count, List<String> visited){
if(i<0||j<0||i>=grid.length||j>=grid[i].length||grid[i][j]==-1 ||visited.contains(i+" "+j))
return 0;
if(grid[i][j]==2)
{
if(visited.size()==count)
return 1;
return 0;
}
visited.add(i+" "+j);
int rst = 0;
rst += helper(grid, i+1, j, count, new ArrayList<>(visited));
rst += helper(grid, i-1, j, count, new ArrayList<>(visited));
rst += helper(grid, i, j+1, count, new ArrayList<>(visited));
rst += helper(grid, i, j-1, count, new ArrayList<>(visited));
return rst;
}

Since we are allowed to change the value of the given 2D array, we can also record the cells that we have visited in the 2D array.

After we visited the cells, we can put a stone (some obstacles) on the cell so that we won’t accidentally revisit them later. Hence, we will just set grid[i][j] to -1 and remove the stone (i.e., set grid[i][j] to 0) after we traversed all the possible paths based on the current cell.

Below is the 0ms code that beats 100% —

public int uniquePathsIII(int[][] grid) {
int m = grid.length, n = grid[0].length;
int[] start = new int[2];
int count = 0;//number of 0s and starting point
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
if(grid[i][j]==1)
{
start[0] = i;
start[1] = j;
}
else if(grid[i][j]==0)
count++;
}
}
return helper(grid, start[0],start[1], count+1);
}
public int helper(int[][] grid,int i,int j, int count){
if(i<0||j<0||i>=grid.length||j>=grid[i].length||grid[i][j]==-1)
return 0;
if(grid[i][j]==2)
{
if(count==0)
return 1;
return 0;
}
grid[i][j] = -1;
int rst = 0;
rst += helper(grid, i+1, j, count-1);
rst += helper(grid, i-1, j, count-1);
rst += helper(grid, i, j+1, count-1);
rst += helper(grid, i, j-1, count-1);
grid[i][j] = 0;
return rst;
}

--

--

--

Click here to view all the stories posted on this blog: https://anj910.medium.com/bookmark-c95e4c52cf44

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Complete Guideline from react hooks And React Router

Spinnaker/Echo + Google Cloud Functions + Stackdriver Logging == Spinnaker Audit Log

Maintain Firebase Cloud Messaging Tokens

FCM Architectural

To Upper Case in 30 Seconds— JavaScript

Zero to Hero: Web3.0 and Solidity Development Roadmap 2021

Screen with some code on it

React Native:

React: Rendering using Concurrent Mode and Suspense

A Quick Guide to Styled Components with Interactive Examples

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Anj

Anj

Click here to view all the stories posted on this blog: https://anj910.medium.com/bookmark-c95e4c52cf44

More from Medium

Interviews à la carte

Software engineering interview

Leetcode — 1 problem

Career Note — Two Year at Amazon

Nailing your engineering interviews: Tips from a technical recruiter

Bold graphics depict an interviewing timeline with various roadblocks, triumphs, and energetic shapes.