Unique Paths III

​A robot is located at the top-left corner of a m x n grid (marked as ‘Start’ in the diagram below). The robot can either move right or diagonally at any point of time. The robot is trying to reach the top-right corner of the grid (marked as ‘Star’ in the diagram below). How many possible unique paths are there?

Followings are the moves allowed at any given point of time:

Consider i is the row index and j is the column index for the 2D grid.
Allowed Moves:
1. i, (j + 1) -> Right
2. (i + 1), (j + 1) -> Diagonnaly Down
3. (i - 1), (j + 1) -> Diagonnaly Up

This is an Extension of Find Unique Paths in a 2D Grid from Source to Destination. Only the allowed moves are different from source to destination. The problem can also be solved using backtracking and Memoization. 

class PathFinder {

  int height, width;

  public int countPaths(int h, int w) {
    this.height = h;
    this.width = w;
    int[][] board = new int[h][w];
    board[0][w - 1] = 1;
    int count = backTrack(board, 0, 0);
    return count;
  }

  private int backTrack(int[][] board, int i, int j) {
    if (i >= height || j >= width || i < 0) return 0;
    if (board[i][j] != 0) return board[i][j];
    int c1 = backTrack(board, i, (j + 1));
    int c2 = backTrack(board, (i + 1), (j + 1));
    int c3 = backTrack(board, (i - 1), (j + 1));
    board[i][j] = (c1 + c2 + c3);
    return board[i][j];
  }
}

public class UniquePath_III {
  public static void main(String[] args) {
    PathFinder pathFinder = new PathFinder();
    int path = pathFinder.countPaths(3, 3);
    System.out.println(path);
  }
}

Complexity Analysis

  • Time Complexity: O(mn). Each cell will be calculated once and only once.
  • Space Complexity : O(mn). Size of the 2D board used as a cache for backtracking.

Categories: Backtracking, DFS

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s