LeetCode Problem 3797

Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming, Matrix, Prefix Sum

Solution

LeetCode 3797 - Count Routes to Climb a Rectangular Grid

Problem Understanding

We are given an n × m grid where each cell is either available ('.') or blocked ('#').

A route starts from any available cell in the bottom row and must eventually end in the top row. During the route, every visited cell must be available.

The movement rules are unusual:

1. A move may either stay in the same row or move to the row immediately above.
2. The Euclidean distance between the source and destination cells must be at most d.
3. Two consecutive same-row moves are forbidden. If we make a same-row move, the next move must go upward.

The goal is to count all valid routes modulo 10^9 + 7.

A key observation is that because consecutive same-row moves are not allowed, each row can contribute at most one horizontal move. Once we move horizontally within a row, the next move must go to the row above.

The constraints are large:

• n ≤ 750
• m ≤ 750
• Total cells can reach 562,500

Any solution that explicitly enumerates routes or transitions between every pair of cells would be far too slow. We need an algorithm close to linear in the number of cells.

Important edge cases include:

• A completely blocked bottom row, which means no route can start.
• A grid with only one row, where routes consist entirely of choosing one cell or making a single same-row move.
• Large values of d, where a cell may connect to almost every cell in a row.
• Rows containing only blocked cells, which immediately eliminate all routes passing through that row.

Approaches

Brute Force

A direct approach would treat every available cell as a state and recursively explore all valid next moves.

For each cell we would:

• Try every available cell in the same row within distance d.
• Try every available cell in the row above within distance d.
• Track whether the previous move stayed in the same row.

This correctly enumerates every valid route, but the number of routes grows exponentially. Even with memoization, each state could have up to O(m) outgoing transitions, leading to an impractical complexity for m,n ≤ 750.

Key Insight

The restriction on consecutive same-row moves dramatically simplifies the structure of a route.

When we arrive at a row:

• We are standing on some cell.
• We may either stop using that row immediately.
• Or perform exactly one same-row move.
• After that, we must move upward.

Therefore, every row is processed independently in two stages:

1. Convert "arrival counts" into "departure counts" within the same row.
2. Transfer those departure counts to the row above.

Both stages become range-sum operations on a one-dimensional array of columns.

For a same-row move, the column difference must satisfy:

$$|c_1-c_2| \le d$$

For an upward move from row r to row r-1, the row difference is exactly 1, so:

$$1 + (c_1-c_2)^2 \le d^2$$

Thus:

$$|c_1-c_2| \le \left\lfloor \sqrt{d^2-1} \right\rfloor$$

Let

$$k = \left\lfloor \sqrt{d^2-1} \right\rfloor$$

Every transition becomes a contiguous column interval. Range sums can therefore be computed using prefix sums in O(1) time per cell.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	Exponential	Enumerates routes directly
Optimal	O(nm)	O(m)	Uses row DP and prefix sums

Algorithm Walkthrough

State Definition

Let arr[j] denote the number of ways to arrive at column j in the current row.

For the bottom row:

• Every available cell can be chosen as a starting point.
• Therefore arr[j] = 1 for available cells.
• Otherwise arr[j] = 0.

Step 1: Process Same-Row Moves

Suppose we have arrived at the current row.

Let dep[j] be the number of ways to finish processing this row at column j.

A route can finish at column j in two ways:

• Arrive directly at j and make no same-row move.
• Arrive at some column within distance d and make a single same-row move to j.

Therefore:

$$dep[j] = \sum arr[x]$$

over all columns satisfying:

$$|x-j| \le d$$

This is a sliding-window sum and can be computed using a prefix sum of arr.

Blocked cells receive value 0.

Step 2: Move to the Row Above

For upward transitions, the maximum allowed column difference is

$$k=\lfloor\sqrt{d^2-1}\rfloor$$

If next[j] is the arrival count in the row above, then:

$$next[j] = \sum dep[x]$$

over all columns satisfying:

$$|x-j| \le k$$

Again, this is a range sum and can be computed with prefix sums.

Blocked cells receive value 0.

Step 3: Repeat for Every Row

Process rows from bottom to top.

After computing arrivals for row r-1, continue the same procedure.

Step 4: Compute the Answer

When we reach the top row, we still need to account for the optional same-row move inside that row.

The dep array for the top row already represents all valid ways to finish the route.

The answer is:

$$\sum dep[j]$$

over all columns.

Why it Works

The crucial invariant is that arr[j] always stores the number of valid routes that have reached column j as the entry point of the current row.

The same-row processing step enumerates all legal ways to finish using the current row, respecting the rule that at most one same-row move can occur before moving upward.

The upward transition step enumerates all legal moves to the next row using the Euclidean distance constraint.

Since every valid route can be uniquely decomposed into these row-by-row decisions, and every legal decision is counted exactly once, the dynamic programming recurrence counts all routes correctly.

Python Solution

from typing import List
from math import isqrt

class Solution:
    def numberOfRoutes(self, grid: List[str], d: int) -> int:
        MOD = 1_000_000_007

        n = len(grid)
        m = len(grid[0])

        k = isqrt(d * d - 1)

        arr = [1 if grid[n - 1][c] == '.' else 0 for c in range(m)]

        for r in range(n - 1, -1, -1):
            prefix = [0] * (m + 1)
            for c in range(m):
                prefix[c + 1] = (prefix[c] + arr[c]) % MOD

            dep = [0] * m

            for c in range(m):
                if grid[r][c] == '#':
                    continue

                left = max(0, c - d)
                right = min(m - 1, c + d)

                dep[c] = (prefix[right + 1] - prefix[left]) % MOD

            if r == 0:
                return sum(dep) % MOD

            prefix = [0] * (m + 1)
            for c in range(m):
                prefix[c + 1] = (prefix[c] + dep[c]) % MOD

            next_arr = [0] * m

            for c in range(m):
                if grid[r - 1][c] == '#':
                    continue

                left = max(0, c - k)
                right = min(m - 1, c + k)

                next_arr[c] = (prefix[right + 1] - prefix[left]) % MOD

            arr = next_arr

        return 0

The implementation follows the algorithm directly.

The array arr stores arrival counts for the current row. For the bottom row, every available cell is a valid starting position, so those entries are initialized to 1.

For each row, a prefix sum of arr allows the computation of all same-row transitions in constant time per column. The resulting values are stored in dep.

If the current row is the top row, all routes terminate here, so the answer is simply the sum of dep.

Otherwise, another prefix sum is built over dep, and range queries of width k compute arrivals in the row above. The resulting array becomes the new arr.

Because every row is processed once and every column is touched only a constant number of times, the algorithm runs efficiently within the constraints.

Go Solution

package main

import "math"

func numberOfRoutes(grid []string, d int) int {
	const MOD int = 1_000_000_007

	n := len(grid)
	m := len(grid[0])

	k := int(math.Sqrt(float64(d*d - 1)))

	arr := make([]int, m)
	for c := 0; c < m; c++ {
		if grid[n-1][c] == '.' {
			arr[c] = 1
		}
	}

	for r := n - 1; r >= 0; r-- {
		prefix := make([]int, m+1)
		for c := 0; c < m; c++ {
			prefix[c+1] = prefix[c] + arr[c]
			if prefix[c+1] >= MOD {
				prefix[c+1] -= MOD
			}
		}

		dep := make([]int, m)

		for c := 0; c < m; c++ {
			if grid[r][c] == '#' {
				continue
			}

			left := c - d
			if left < 0 {
				left = 0
			}

			right := c + d
			if right >= m {
				right = m - 1
			}

			val := prefix[right+1] - prefix[left]
			if val < 0 {
				val += MOD
			}

			dep[c] = val
		}

		if r == 0 {
			ans := 0
			for _, v := range dep {
				ans += v
				ans %= MOD
			}
			return ans
		}

		prefix = make([]int, m+1)
		for c := 0; c < m; c++ {
			prefix[c+1] = prefix[c] + dep[c]
			prefix[c+1] %= MOD
		}

		nextArr := make([]int, m)

		for c := 0; c < m; c++ {
			if grid[r-1][c] == '#' {
				continue
			}

			left := c - k
			if left < 0 {
				left = 0
			}

			right := c + k
			if right >= m {
				right = m - 1
			}

			val := prefix[right+1] - prefix[left]
			if val < 0 {
				val += MOD
			}

			nextArr[c] = val
		}

		arr = nextArr
	}

	return 0
}

The Go version mirrors the Python solution closely. The primary difference is explicit modular arithmetic using int values. Prefix sums are maintained modulo MOD, and negative subtraction results are corrected by adding MOD.

Worked Examples

Example 1

grid = ["..",
        "#."]
d = 1

We have:

k = floor(sqrt(1^2 - 1)) = 0

Bottom row:

Column	Available	arr
0	#	0
1	.	1

Processing row 1:

Column	dep
0	0
1	1

Move upward (k = 0):

Column	arr(top)
0	0
1	1

Process top row:

Column	dep
0	1
1	1

Answer:

1 + 1 = 2

Example 2

grid = ["..",
        "#."]
d = 2

Now:

k = floor(sqrt(3)) = 1

Bottom row:

arr = [0, 1]

Row 1:

dep = [0, 1]

Move upward:

arr(top) = [1, 1]

Process top row:

For each column, the interval covers both cells.

dep = [2, 2]

Answer:

2 + 2 = 4

Example 3

grid = ["#"]

Bottom row contains no available cells.

arr = [0]
dep = [0]

Answer:

0

Example 4

grid = [".."]
d = 1

Single row.

Initial:

arr = [1, 1]

Processing top row:

dep[0] = 2
dep[1] = 2

Answer:

2 + 2 = 4

Complexity Analysis

Measure	Complexity	Explanation
Time	O(nm)	Each row performs a constant number of prefix-sum passes
Space	O(m)	Only current-row arrays are stored

The algorithm never stores DP values for all rows simultaneously. At any time it keeps only the current arrival array, the departure array, and prefix sums, all of size m. Since every cell participates in only a constant number of operations, the total running time is linear in the number of grid cells.

Test Cases

from typing import List

s = Solution()

assert s.numberOfRoutes(["..", "#."], 1) == 2      # Example 1
assert s.numberOfRoutes(["..", "#."], 2) == 4      # Example 2
assert s.numberOfRoutes(["#"], 750) == 0           # Example 3
assert s.numberOfRoutes([".."], 1) == 4            # Example 4

assert s.numberOfRoutes(["."], 1) == 1             # Single available cell
assert s.numberOfRoutes(["#"], 1) == 0             # Single blocked cell

assert s.numberOfRoutes(["...", "..."], 1) > 0     # Small multi-row grid
assert s.numberOfRoutes(["###", "###"], 5) == 0    # Completely blocked

assert s.numberOfRoutes(["...."], 750) == 16       # Every cell can reach every cell in one row

assert s.numberOfRoutes(
    [
        "...",
        "...",
        "..."
    ],
    750
) > 0                                              # Large connectivity

assert s.numberOfRoutes(
    [
        ".#.",
        "#.#",
        ".#."
    ],
    1
) == 0                                              # No valid vertical chain

Test Summary

Test	Why
Example 1	Validates minimum upward reach
Example 2	Validates larger distance transitions
Example 3	Validates blocked starting row
Example 4	Validates single-row behavior
["."]	Smallest valid grid
["#"]	Smallest invalid grid
Two open rows	Basic multi-row connectivity
All blocked	No route exists
Single wide row, large d	Maximum same-row connectivity
Fully open grid	Stress test for many routes
Alternating blocks	Ensures unreachable layouts return zero

Edge Cases

Completely Blocked Bottom Row

If every cell in the bottom row is blocked, no route can even begin. A naive implementation might still try to perform transitions. In this solution, the initial arr array becomes all zeros, causing every subsequent DP value to remain zero automatically.

Single-Row Grid

When n = 1, the bottom row is also the top row. The route never needs to move upward. The algorithm handles this naturally because it processes the row, computes all legal same-row choices, and immediately returns the sum of the resulting dep values.

Very Large Distance

When d is large, nearly every column may connect to every other column. A pairwise transition implementation would become quadratic per row. The prefix-sum formulation still performs only constant-time range queries per cell, preserving O(nm) complexity.

Rows With No Available Cells

If an intermediate row is entirely blocked, every arrival count for that row becomes zero. Since all later transitions originate from these counts, the DP correctly propagates zero routes upward without requiring any special-case logic.