0
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ Where is the illustration that you mention? \$\endgroup\$ – Martin R May 13 '18 at 8:14
  • \$\begingroup\$ Your reference link requires a login. \$\endgroup\$ – Martin R May 13 '18 at 8:31
  • \$\begingroup\$ @MartinR, sorry for the delay, I have changed the reference and put a link to the illustration mentioned in the program too. \$\endgroup\$ – Anirudh Thatipelli May 14 '18 at 16:28
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Actually, the code is modeled after the problem description. The description says that the starting point is (0,0) and the destination is (n-1, n-1). Also, the check whether x and y are valid is necessary, because otherwise, the method would recursively call itself for invalid values of x and y and would never reach the base case, thereby ending up in an infinite recursive loop. \$\endgroup\$ – Stingy May 14 '18 at 7:42
  • \$\begingroup\$ @Stingy remind me to never review again when tired :D I do not know how I misread that. However, I did not say you do not need to check x and y, you can let the base case handle that. \$\endgroup\$ – Koekje May 14 '18 at 8:15
  • \$\begingroup\$ Ah, so you mean making two distinct base cases, one for the destination that returns 1, and one for an invalid location that return 0. Yes, that would be very straightforward, it's just that I found your wording "if you check for 0 up front" to be a bit unclear. \$\endgroup\$ – Stingy May 14 '18 at 8:26
1
\$\begingroup\$

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})\$

\$\endgroup\$
  • \$\begingroup\$ Yes, I calculated the time to be 2^n. This could be greatly reduced on using memoization techniques. \$\endgroup\$ – Anirudh Thatipelli May 14 '18 at 17:07
  • \$\begingroup\$ I actually was thinking about adding this possible solution, as it came to my mind. Seems I was to late. This is definitely an elegant solution! I still wonder if there is a direct way to calculate it though... \$\endgroup\$ – Koekje May 14 '18 at 18:21
  • 2
    \$\begingroup\$ @Koekje: oeis.org/A000108: "... Then the number of such paths that never go below the x-axis (Dyck paths) is C(n)" \$\endgroup\$ – Martin R May 16 '18 at 9:02
  • \$\begingroup\$ @MartinR aha! That is pretty awesome :D \$\endgroup\$ – Koekje May 22 '18 at 15:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.