Watch 2 video solutions for Count Routes to Climb a Rectangular Grid, a hard level problem involving Array, Dynamic Programming, Matrix. This walkthrough by CodeWithMeGuys has 555 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given a string array grid of size n, where each string grid[i] has length m. The character grid[i][j] is one of the following symbols:
'.': The cell is available.'#': The cell is blocked.You want to count the number of different routes to climb grid. Each route must start from any cell in the bottom row (row n - 1) and end in the top row (row 0).
However, there are some constraints on the route.
d, where d is an integer parameter given to you. The Euclidean distance between two cells (r1, c1), (r2, c2) is sqrt((r1 - r2)2 + (c1 - c2)2).r to r - 1).Return an integer denoting the number of such routes. Since the answer may be very large, return it modulo 109 + 7.
Example 1:
Input: grid = ["..","#."], d = 1
Output: 2
Explanation:
We label the cells we visit in the routes sequentially, starting from 1. The two routes are:
.2 #1
32 #1
We can move from the cell (1, 1) to the cell (0, 1) because the Euclidean distance is sqrt((1 - 0)2 + (1 - 1)2) = sqrt(1) <= d.
However, we cannot move from the cell (1, 1) to the cell (0, 0) because the Euclidean distance is sqrt((1 - 0)2 + (1 - 0)2) = sqrt(2) > d.
Example 2:
Input: grid = ["..","#."], d = 2
Output: 4
Explanation:
Two of the routes are given in example 1. The other two routes are:
2. #1
23 #1
Note that we can move from (1, 1) to (0, 0) because the Euclidean distance is sqrt(2) <= d.
Example 3:
Input: grid = ["#"], d = 750
Output: 0
Explanation:
We cannot choose any cell as the starting cell. Therefore, there are no routes.
Example 4:
Input: grid = [".."], d = 1
Output: 4
Explanation:
The possible routes are:
.1
1.
12
21
Constraints:
1 <= n == grid.length <= 7501 <= m == grid[i].length <= 750grid[i][j] is '.' or '#'.1 <= d <= 750Problem Overview: You are given a rectangular grid and need to count how many valid routes exist to climb from the bottom row to the top row while respecting movement constraints between rows. Each step moves upward to a reachable column in the next row. The task is to efficiently compute the total number of valid routes across the matrix.
Approach 1: Dynamic Programming with Range Transitions (O(m * n^2) time, O(m * n) space)
Model the grid as a layered graph where each row represents a level. Let dp[r][c] represent the number of ways to reach cell (r, c). For each cell in row r, iterate over all columns in row r-1 that can transition into it and accumulate their counts. This produces the recurrence dp[r][c] += dp[r-1][k] for all valid previous columns k. The approach directly follows the definition of the problem and is easy to reason about, but the nested iteration over columns leads to O(m * n^2) time complexity. Space complexity remains O(m * n) for the DP table. This solution demonstrates the core idea behind dynamic programming on layered structures.
Approach 2: Dynamic Programming with Prefix Sum Optimization (O(m * n) time, O(n) space)
The quadratic bottleneck comes from repeatedly summing ranges of columns in the previous row. Instead of recomputing these sums, build a prefix sum array for every row. If a cell in row r can receive transitions from a column interval [L, R] in row r-1, compute the contribution in constant time using prefix[R] - prefix[L-1]. After processing a row, build a new prefix sum array for the next iteration. This converts range aggregation from O(n) to O(1), reducing total complexity to O(m * n). Only the previous row and prefix sums are needed, so space can be compressed to O(n). This technique combines matrix traversal with prefix sum range queries to eliminate redundant computation.
Recommended for interviews: Start by describing the straightforward DP formulation to show you understand the state definition and transitions. Then optimize it using prefix sums to avoid repeated range summations. Interviewers typically expect the O(m * n) dynamic programming solution with prefix sums because it demonstrates both algorithmic reasoning and practical optimization.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming with Direct Range Iteration | O(m * n^2) | O(m * n) | Useful for understanding the state transition before optimization |
| Dynamic Programming with Prefix Sum Optimization | O(m * n) | O(n) | Preferred solution for large grids and interview settings |