Return to Revisions

Number of Paths

You’re testing a new driverless car that is located at the Southwest (bottom-left) corner of an n×ばつn grid. The car is supposed to get to the opposite, Northeast (top-right), corner of the grid. Given n, the size of the grid’s axes, write a function numOfPathsToDest that returns the number of the possible paths the driverless car can take.

For convenience, let’s represent every square in the grid as a pair (i,j). The first coordinate in the pair denotes the east-to-west axis, and the second coordinate denotes the south-to-north axis. The initial state of the car is (0,0), and the destination is (n-1,n-1).

The car must abide by the following two rules: it cannot cross the diagonal border. In other words, in every step the position (i,j) needs to maintain i >= j. See the illustration above for n = 5. In every step, it may go one square North (up), or one square East (right), but not both. E.g. if the car is at (3,1), it may go to (3,2) or (4,1).

Example

input: n = 4
output: 5 # since there are five possibilities:
 # "EEENNN", "EENENN", "ENEENN", "ENENEN", "EENNEN",
 # where the 'E' character stands for moving one step
 # East, and the 'N' character stands for moving one step
 # North (so, for instance, the path sequence "EEENNN"
 # stands for the following steps that the car took:
 # East, East, East, North, North, North)

My approach:

import java.io.*;
import java.util.*;
class Solution {
 static int numOfPathsToDest(int n) {
 // your code goes here
 //n = 2
 int startX = 0;
 int startY = 0;
 
 int numPoss = numPaths(startX,startY,n);
 
 
 return numPoss;
 
 }
 
 static private int numPaths(int startX, int startY, int n )
 {
 int destX = n - 1;
 int destY = n - 1;
 int numPoss = 0;
 
 //Base case
 if((startX == destX) && (startY == destY ))
 numPoss++;
 
 //Recursive condition
 else 
 {
 if( (startX >= startY) && (startX < n) && ( startY < n ))
 {
 //East 
 numPoss += numPaths(startX+1, startY,n);
 
 //North
 numPoss += numPaths(startX,startY + 1, n);
 } 
 
 //Time complexity: O(2^n) -> O(n^2) in memoization
 //Space complexity: O(n^2)
 //Bottom up approach: O(n) space complexity
 //Time complexity: O(n)
 }
 
 return numPoss;
 }
 public static void main(String[] args) {
 System.out.println(numOfPathsToDest(2));
 }
}
//n = 4
//#squares = 4 + 3 + 2 + 1
//#squares = n + n-1 + n-2 + ... 1 = n(n + 1)/2
//square 0 - eastx 4/ n - 1 
//square (1,0): up - 1, east - 3/(n - 1)
//square (2,0): up - 2, east: 2/(n - 2)
//east + north : n 
//

I have the following questions with respect to the above code:

1. What can I further improve my code in terms of space and time complexity?

2. Is there any smarter approach to solve this question?

3. Does my code violate any of the coding conventions?

4. Are there any other ways that I can further optimize the code?

Reference