Find The Number of Paths Through a 2D Grid - Apple Interview Question

Been wanting to do some more CS basics posts, so here ya go! Today we're solving the classic LeetCode interview question commonly asked at Apple, Google, Facebook, and the rest of the FAANG gang.

You're given a grid of size m x n. You need to find the number of paths you can take from coordinates 0,0 to the max coordinate of the grid. So if you were given a 12x12 grid, you need to navigate from 0,0 to 12,12.

There's a few solutions, but recursion tends to be the simplest. It comes with a performance curveball though, so watch out for that on interviews!

First let's consider the base cases. Obviously we have the variables m and n and of course if either of these coordinates are 1 or less, there's only 1 way through the grid, so let's just return that.

function countPaths(m: number, n: number): number {
    if (m <= 1 || n <= 1) return 1;
}

Nice, now let's assume we run the function on a 12x12 grid. Since we are conveniently at the end coordinate, we can work backwards.

To solve the problem we basically just want to take both directions we can go from the current position in the grid. So in our case, we want to recursively run the function for coordinates (m, n - 1) and (m - 1, n) and add these results together.

function countPaths(m: number, n: number): number {
    if (m <= 1 || n <= 1) return 1;
    return countPaths(m - 1, n) + countPaths(m, n - 1);
}

And that's the working solution. Kinda cool right? We can run it with a 4x4 grid and it will output that there are 20 paths through it. Run it with a 7x7 grid and it will tell you there are 924 paths through it.

As you can see, the possible paths increases exponentially with just small increases in grid size. At some point in the interview, you might get asked to run it with a bigger grid size, and the program might take a long time to compute the value.

We can fix this performance curveball by implementing caching. We are calling the count function for every position in the grid, even when we have already seen the result. We can just add a cache object to store the result and then lookup by coordinates to see if we have seen it before.

function countPaths(m: number, n: number, cache: { [coordinate in string]: number } = {}): number {
    const id = [m, n].join(',');
    if (cache[id]) return cache[id];

    cache[id] = countPaths(m - 1, n, cache) + countPaths(m, n - 1, cache);
    return cache[id];
}

Nice, much faster!