Count Routes to Climb a Rectangular Grid - Video Solutions
Leetcode 3797 | Count Routes to Climb a Rectangular Grid | Leetcode biweekly 173
Count Routes to Climb a Rectangular Grid - Video Solution
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 601 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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.
- You can only move from one available cell to another available cell.
- The Euclidean distance of each move is at most
d, wheredis an integer parameter given to you. The Euclidean distance between two cells(r1, c1),(r2, c2)issqrt((r1 - r2)2 + (c1 - c2)2). - Each move either stays on the same row or moves to the row directly above (from row
rtor - 1). - You cannot stay on the same row for two consecutive turns. If you stay on the same row in a move (and this move is not the last move), your next move must go to the row above.
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 <= 750
Approach Overview
Problem 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.
Complexity Analysis
| 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 |