Count Paths Through a Grid Moving Only Down or Right

Medium20–25 min

Topics

BacktrackingRecursionMatrix

Companies

AmazonMicrosoftAdobe

You're given a grid of open (1) and blocked (0) cells. Starting at the top-left cell and moving only down or right one step at a time, count every distinct path that reaches the bottom-right cell without ever stepping on a blocked one. Recursively trying both directions from every cell finds every path, but the same cell gets reached by many different down/right sequences on the way to the corner, and each arrival re-explores everything reachable from that cell all over again. Remembering a cell's path count the first time it's fully computed turns every later arrival at that same cell into a single lookup — the search still considers the same set of paths, it just never re-derives a cell's contribution to them more than once.

Test Case 1:

Input:grid = [[1,1,1],[1,0,1],[1,1,1]]

Output:2

Explanation:The blocked center forces every path around it — exactly 2 distinct down/right routes reach the bottom-right corner.

Test Case 2:

Input:grid = [[1,1],[1,1]]

Output:2

Explanation:A fully open 2×2 grid: go down-then-right, or right-then-down.

Test Case 3:

Input:grid = [[0,1],[1,1]]

Output:0

Explanation:The starting cell itself is blocked, so no path can begin at all.

Constraints

◆1 ≤ grid.length, grid[0].length ≤ 15
◆Every cell holds 1 (open) or 0 (blocked)
◆Movement is restricted to one step down or one step right at a time — no other directions are allowed
◆A path starts at the top-left cell and ends at the bottom-right cell; if either is blocked, no path exists

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Recompute Every Cell's Path Count From Scratch

Brute

From each cell, recursively count paths reachable by moving down (if that cell is open) plus paths reachable by moving right (if that cell is open), until the bottom-right corner is reached. This is correct, but many different down/right sequences pass through the exact same cell on their way to the corner — and this version has no memory of a cell it's already fully explored, so it recomputes that cell's entire path count over again, branch by branch, every single time a different route happens to pass through it.

TimeO(2^(rows+cols))

SpaceO(rows+cols)

Java

Try it out

class Solution {
    public int countGridPaths(int[][] grid) {
        int n = grid.length, m = grid[0].length;
        if (grid[0][0] == 0 || grid[n - 1][m - 1] == 0) return 0;
        return countFrom(grid, 0, 0);
    }

    private int countFrom(int[][] grid, int r, int c) {
        int n = grid.length, m = grid[0].length;
        if (r == n - 1 && c == m - 1) return 1;
        int total = 0;
        if (r + 1 < n && grid[r + 1][c] == 1) total += countFrom(grid, r + 1, c);
        if (c + 1 < m && grid[r][c + 1] == 1) total += countFrom(grid, r, c + 1);
        return total;
    }
}

Optimal — Remember Each Cell's Path Count Once Computed

Optimal

Same recursive shape, but the first time a cell's path count is fully computed, store it. Before doing any work for a cell, check whether it's already stored — if so, return that stored count immediately instead of re-exploring everything reachable from it a second time. Since a cell can only be reached going down or right, every one of the (rows × cols) cells needs its count computed at most once; after that, every other route through it is an O(1) lookup instead of a fresh exploration.

TimeO(rows · cols)

SpaceO(rows · cols)