Grid Traveler or Unique Paths

The weather is acting somewhat erratic. Today the forecasted high in the Twin Cities of Minneapolis and St. Paul will be 20F lower than yesterday. Tomorrow it should be 10F lower than today and should be raining. The water level in pond in my backyard is very low. Some rain should help. I noticed that a couple of cranes have made their home for summer the pond. Not sure if they are the same that return every year or they are an offspring of the ones from last year. I do not know much about cranes.

Since the weather will be nice today; my wife and I will go for a walk after the end of the workday. Not sure what we will do tomorrow. Perhaps we will go to the Mall of America.

On a different note, as you might know, I work in 2-hour blocks. After each block I go up and get something to drink. A few minutes later I head back to work. A few weeks ago I moved a stationary bike from a utility room and set it up in the lower level living room. I started biking for 5 minutes after completing a 2-hour block. That is working very well. I get between 20 to 25 minutes biking each workday. Since the bike is indoors I can do it year round.

As I mentioned in a previous post, I am watching a YouTube video titled:  Dynamic Programming – Learn to Solve Algorithmic Problems & Coding Challenges. I am also experimenting with code as it progresses. The video uses JavaScript but I am writing code in Java using the VSCode IDE.

The requirement for one of the examples is as follows:

Say you are a traveler on a 2D grid.
You begin in the top-left corner
and your goal is to travel to the bottom-right corner.
You may only move down and right.

In how many ways can you travel to the goal on a grid with dimensions m * n?

The idea is to start at the top-left corner of the grid and end at the lower-right corner. We need to figure out how many ways can this be accomplished.

Since I will be writing the associated code in Java the signature would be something like:

public int gridTraveler(int m, int n) {
}

The video shows how to approach Dynamic Programs. It does not make sense for me to repeat what is suggested it here. The video in question is over 5-hours long. If interested in the subject, I suggest you watch the video and as you go try solving the sample programs.

1,1
main <<< m: 1 n: 1
main <<< ans: 1
main <<< ans: 1


0,1
main <<< m: 0 n: 1
main <<< ans: 0
main <<< ans: 0


1,0
main <<< m: 1 n: 0
main <<< ans: 0
main <<< ans: 0


2,3
main <<< m: 2 n: 3
main <<< ans: 3
<<< memo:
[1, 1, 1]
[1, 2, 3]
main <<< ans: 3


3,2
main <<< m: 3 n: 2
main <<< ans: 3
<<< memo:
[1, 1]
[1, 2]
[1, 3]
main <<< ans: 3


3,3
main <<< m: 3 n: 3
main <<< ans: 6
<<< memo:
[1, 1, 1]
[1, 2, 3]
[1, 3, 6]
main <<< ans: 6


6,6
main <<< m: 6 n: 6
main <<< ans: 252
<<< memo:
[1, 1, 1, 1, 1, 1]
[1, 2, 3, 4, 5, 6]
[1, 3, 6, 10, 15, 21]
[1, 4, 10, 20, 35, 56]
[1, 5, 15, 35, 70, 126]
[1, 6, 21, 56, 126, 252]
main <<< ans: 252


7,3
main <<< m: 7 n: 3
main <<< ans: 28
<<< memo:
[1, 1, 1]
[1, 2, 3]
[1, 3, 6]
[1, 4, 10]
[1, 5, 15]
[1, 6, 21]
[1, 7, 28]
main <<< ans: 28


3,7
main <<< m: 3 n: 7
main <<< ans: 28
<<< memo:
[1, 1, 1, 1, 1, 1, 1]
[1, 2, 3, 4, 5, 6, 7]
[1, 3, 6, 10, 15, 21, 28]
main <<< ans: 28

Our test program reads the values for the m * n dimensions for the grid. The values are then displayed. I wrote two approaches. It is important to always start with small examples and make then grow. This helps finding patterns that we can use to decompose the main problem into a recursive one and then add memoization.

As you look into the examples the matrix used for memoization is displayed. It is important for the second implementation to make a connection between the values to get to a faster and perhaps more elegant solution.

62. Unique Paths
https://leetcode.com/problems/unique-paths/

A robot is located at the top-left corner of a m x n grid.
The robot can only move either down or right at any point in time.
The robot is trying to reach the bottom-right corner of the grid.
How many possible unique paths are there?

Related topics:

o Array
o Dynamic Programming

After I finished with the code for the original problem I wanted to make sure that my solution was solid. One of the simplest ways to do so is to find the same or very similar problem in HackerRank or LeetCode. Believe it or not I was able to find a very similar problem stated completely different in LeetCode. I would assume that HackerRank has the same problem with a different description.

As you can tell the problem is exactly the same but the description is completely different. The good thing is that in LeetCode you have to pass a large set of test cases for your solution to be approved. That gives you a confidence level that cannot be achieved with running five or so test cases.

    /**
     * Test scaffold
     * @throws IOException
     */
    public static void main(String[] args) throws IOException {
        
        // **** open buffered reader ****
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // **** read m and n ****
        int[] mn = Arrays.stream(br.readLine().trim().split(","))
                    .mapToInt(Integer::parseInt)
                    .toArray();

        // **** close buffered reader ****
        br.close();

        // **** extract m and n ****
        int m = mn[0];
        int n = mn[1];
        
        // ???? ????
        System.out.println("main <<< m: " + m + " n: " + n);

        // **** generate and display answer ****
        System.out.println("main <<< ans: " + gridTraveler(m, n));

        // **** generate and display answer ****
        System.out.println("main <<< ans: " + gridTravelerNRM(m, n));

The test code is quite simple. It reads the line with the m and n values and displays them. It then call to versions of the solution.

    /**
     * Say you are a traveler on a 2D grid.
     * You begin in the top-left corner
     * and your goal is to travelto the bottom-right corner.
     * You may only move down and right.
     *
     * In how many ways can you travel to the goal on a grid with dimensions m * n?
     * 
     * Without memoization:
     * Time: O(2^m+n)  Space: O(m + n)
     * 
     * With memoization:
     * Time:  Space: O(m + n)
     * 
     * Runtime: 9 ms, faster than 5.36% of Java online submissions.
     * Memory Usage: 38.6 MB, less than 5.05% of Java online submissions.
     */
    static int gridTraveler(int m, int n) {

        // **** initialization ****
        int ans                         = 0;
        int[] callCounter               = new int[1];
        HashMap<String, Integer> memo   = new HashMap<>();

        // **** recursive call ****
        ans = gridTraveler(m, n, memo, callCounter);

        // ???? ????
        // System.out.println("<<< memo: " + memo.toString());
        // System.out.println("<<< callCounter: " + callCounter[0]);

        // **** return answer ****
        return ans;
    }

This is the implementation of the first approach with memoization. As you can see it works but is quite slow for LeetCode standards. This is the entry point for the recursive method. Note that I decided to use a hash map. We could have used a matrix.

Note that at some point we used a callCounter to see the number of recursive calls. It might be a good idea to enable the call counter. Disabling memoization is quite simple as we will see in the following code snippet.

    /**
     * Say you are a traveler on a 2D grid.
     * You begin in the top-left corner
     * and your goal is to travelto the bottom-right corner.
     * You may only move down and right.
     *
     * In how many ways can you travel to the goal on a grid with dimensions m * n?
     * 
     * Recursive call.
     */
    static int gridTraveler(int m, int n, HashMap<String, Integer> memo, int[] callCounter) {

        // ???? increment call counter ????
        callCounter[0]++;

        // **** base case(s) ****
        if (m == 1 && n == 1) return 1;
        if (m == 0 || n == 0) return 0;

        // **** generate key ****
        String key = "" + (m - 1) + "," + n;

        // **** generate value for key ****
        if (!memo.containsKey(key))
            memo.put(key, gridTraveler(m - 1, n, memo, callCounter) + gridTraveler(m, n - 1, memo, callCounter));

        // **** return value ****
        return memo.get(key);
    } 

This is the recursive call with memoization. For starts we increment the call counter. This is not needed by the function. It just provides statistics on the number of recursive calls made.

We then have the base cases.

We then generate a key for the hash map.

The key is looked up in the hash map. If it is not contained in it, the value is generated and added to the hash map with the specified key.

We then return the value associated with the key. We could have optimized somewhat this code but I decided to leave it as is.

If you want to disable memoization, the simplest this is to not just compute the sum of values resulting from the calls to the gridTraveler() function and return it.

BTW, if you rename the functions and paste the code into the LeetCode IDE the solution should be accepted as illustrated in the comment section.

    /**
     * A robot is located at the top-left corner of a m x n grid.
     * The robot can only move either down or right at any point in time.
     * The robot is trying to reach the bottom-right corner of the grid.
     * How many possible unique paths are there?
     * 
     * No recursion using memoization.
     * 
     * Time:  O(m * n)  Space: O(m * n)
     * 
     * Runtime: 0 ms, faster than 100.00% of Java online submissions.
     * Memory Usage: 35.7 MB, less than 67.17% of Java online submissions.
     */
    static int gridTravelerNRM(int m, int n) {

        // **** sanity check(s) ****
        if (m == 1 && n == 1) return 1;
        if (m == 0 || n == 0) return 0;

        // **** memoization ****
        int[][] memo = new int[m][n];

        // **** loop (no recursion) ****
        for (int i = 0;  i < m; i++) {

            for (int j = 0; j < n; j++) {

                // **** save distance to target ****
                if (i == 0 || j == 0)       // top row or left column
                    memo[i][j] = 1;
                else
                    memo[i][j] = memo[i - 1][j] + memo[i][j - 1];
            }
        }

        // ???? ????
        System.out.println("<<< memo: ");
        for (int k = 0; k < m; k++)
            System.out.println(Arrays.toString(memo[k]));       

        // **** return answer ****
        return memo[m - 1][n - 1];
    }

This is the function that performs the calculations for the LeetCode problem. You can also change the name or just paste the body into the LeetCode IDE.

Note that this is not a recursive call. It contains two nested loops.

Before proceeding, take a look at the last test case in this post. The memo array is displayed. Spend a few minutes understanding how the values are being set in this matrix.

The top row and left column are set to 1 because that is the only option available at the time.

The rest of the entries are filled in by computing the sum of the specified cell using existing data from previous rows or columns. Remember that we can only move right or down.

The answer is left in the lower-right cell of the memo matrix.

This was a very educational exercise. The first approach was intuitive and follows a pattern to solve dynamic programming problems. The second approach takes some specific observations made with the knowledge that we will be using memoization.

Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.

If you have comments or questions regarding this, or any other post in this blog, please do not hesitate and leave me a note below. I will reply as soon as possible.

Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer toolset.

Thanks for reading this post, feel free to connect with me John Canessa at LinkedIn.

Regards;

John