1. Recursion

To solve this problem, we want to find the number of paths that lead into the bottom right corner. We can write a recursion that computes the number of paths that lead into a particular square.

The the number of ways get to any square is equal to the number of ways to get to that square from the top, plus the number of ways to get to it from the left.

numPaths(m, n) = numPaths(m-1, n) + numPaths(m, n-1)

2. Base case

The recursion will keep calling itself on smaller m's and n's, until it gets to a square that's out of bounds. You need a base case for when this happens. There are no ways for your car to get out of bounds:

numPaths(m, n < 0) = 0
numPaths(m < 0, n) = 0

You also need a base case to indicate that you start at the top left corner.

numPaths(0, 0) = 1

3. Code

You can code this up using regular recursion, but it's very slow.

def numMatrixPaths(m, n):

    def numPaths(m, n):
        if m == 0 and n == 0:
            return 1
        if m < 0 or n < 0:
            return 0
        return numPaths(m-1, n) + numPaths(m, n-1)

    return numPaths(m-1, n-1)

To code this up, you can use "Tabulation". The function call numPaths(m, n) depends on numPaths of smaller m and n, so we can compute the smallest m and n first and the biggest ones last. Here's the code:

def numMatrixPaths(m, n):
    # create an m x n matrix of zeros
    # to store numPaths[i][j]
    numPaths = [[0 for _ in range(n)] for _ in range(m)]

    for i in range(0, m):
        for j in range(0, n):
            # base cases
            if i == 0 and j == 0:
                numPaths[i][j] = 1
                continue
            if i < 0 or j < 0:
                numPaths[i][j] = 0
                continue
            
            # recursion
            numPaths[i][j] = numPaths[i-1][j] + numPaths[i][j-1]
            
    # return the final result
    return numPaths[m-1][n-1]

Time Complexity $O(n \cdot m)$

Space Complexity $O(n \cdot m)$

You don't have to know this for an interview, but you can solve this problem with only math. The car always steps right $\texttt{n-1}$ times, and down $\texttt{m-1}$ times, giving $\texttt{m-n-2}$ steps total. Out of all these steps, we want to choose $\texttt{m-1}$ of them to be down steps, and the rest of them to be right steps (or we could choose the other way, it doesn't matter). You can write this with math as:

Here's how you can code this up.

import math
def numMatrixPaths(m, n):
    down_moves = m-1
    right_moves = n-1
    total_moves = down_moves + right_moves

    # of the total number of moves, pick some moves to be down
    return math.comb(total_moves, down_moves)

Time Complexity $O(1)$

Space Complexity $O(1)$