Number of Paths (BackTracking) in Java

Question

Illustration

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 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

Answer 1

I have a feeling there is a direct way to compute this amount, but I am not really into all the mathematics, you could possibly look it up. I'll talk about your code as is:

• You should really remove all the superfluous white space, it hampers readability.

• In Java, opening braces are not on a new line.

• private before static.

• Do not save te result of your recursive function in a variable, you can return at once.

• The problem states you move from (0, 0) to (n,n). If you model your code the other way around, you can simplify it quite a bit. No need to pass n to your recursive function for example, as you can simply compare with 0.

• Try to always use braces, even if you only have one line inside the block, as for example with the if part in your recursive function. It helps prevent unnoticed bugs due to formatting, and helps ease up modifying it later on.

• In the else block, you do not need to check if x and y are valid, if you check for 0 up front.

• In the recursive function, if the initial if succeeds, the result will always be 1. So you can return at once, it makes it more readable. Return early is a good thing in my opinion. The variable can then be put inside the else, reducing the scope.

• You mention memoization, yet you do not seem to be using it. If you take the example, and the paths taken there:

  “EEENNN”
  
  “EEN|ENN”
  “EEN|NEN”
  
  “ENE|NEN”
  “ENE|ENN”
  

Note that EEN will bring you to the same spot as ENE. You can see that each of those share the same second parts as well. This is duplication which we can use to speed up the algorithm.

If you think about it, there are generally multiple ways to get to some point (x,y). If you think of this as the starting point, the possible paths to the destination will obviously be the same, no matter how you get there. So what you can do is create a lookup table for a calculated location, so you calculate each one only once. This will give you an extreme amount of speedup I would think, on problems with a big amount of possible paths. Which you will get to quickly, even for small values of n.

Answer 2

As Koekje has already pointed out, using recursion here is inefficient, because for every valid location (x, y), numPaths(x, y, n) will be called not once, but the number of times equivalent to the number of possible paths leading up to this location. I don't know what the overall time complexity would be, but from looking at the number of method calls necessary for every \$n\leq24\$, which can be calculated by summing the number of possible paths to every valid location for this \$n\$, it seems that it is some monstrosity slightly worse than \$O(3^n)\$.

Equipping the recursive method with a cache would be a way to rectify this, but I can imagine that this could make the code a bit ugly. Instead, you could try to fill up the lookup table not via recursion, but in an iterative manner. So you start out with this (let's say \$n\$ is \$6\$):

            ? ← destination
          ? ?
        ? ? ?
      ? ? ? ?
    ? ? ? ? ?
  ? ? ? ? ? ?
  ↑
start

If you are already at the destination, there is obviously only one possible path to the destination, so we set the value for the destination to 1 (this would be the base case in your recursive version):

          1
        ? ?
      ? ? ?
    ? ? ? ?
  ? ? ? ? ?
? ? ? ? ? ?

Since every value in the lookup table is the sum of the value above it and the value to its right, we can first fill up the rightmost column from top to bottom (since the values in the rightmost column have no value to their right, every value in this column is identical to the value above it):

          1
        ? 1
      ? ? 1
    ? ? ? 1
  ? ? ? ? 1
? ? ? ? ? 1

Now we fill up the next rightmost column in the same way. The upmost element has no value above it, so it is identical to the value to its right.

          1
        1 1
      ? 2 1
    ? ? 3 1
  ? ? ? 4 1
? ? ? ? 5 1

Repeat this for all the other columns until you have the final lookup table:

                1
             1  1
          2  2  1
       5  5  3  1
   14 14  9  4  1
42 42 28 14  5  1

The time complexity will be \$O(n+(n-1)+(n-2)+\ldots+1) = O({n+1\choose 2})\$