Skip to main content
Talentd

Count Routes to Climb a Rectangular Grid - Solution & Explanation

HardArrayDynamic ProgrammingMatrixPrefix Sum4 min readAsked at: Microsoft
Practice this problem

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, 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).
  • Each move either stays on the same row or moves to the row directly above (from row r to r - 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 <= 750
  • 1 <= m == grid[i].length <= 750
  • grid[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.

Solutions for this problem are being prepared.

Try solving it yourself

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Dynamic Programming with Direct Range IterationO(m * n^2)O(m * n)Useful for understanding the state transition before optimization
Dynamic Programming with Prefix Sum OptimizationO(m * n)O(n)Preferred solution for large grids and interview settings

Video Solution

Leetcode 3797 | Count Routes to Climb a Rectangular Grid | Leetcode biweekly 173 • CodeWithMeGuys • 601 views views

Watch 1 more video solutions →

Frequently Asked Questions

Is Count Routes to Climb a Rectangular Grid easy or hard?
Count Routes to Climb a Rectangular Grid is categorized as a Hard problem because it combines matrix traversal, dynamic programming state transitions, and prefix sum optimization. The main challenge is identifying how to convert repeated range transitions into constant-time prefix queries.
Count Routes to Climb a Rectangular Grid Python/Java solution
Implement a dynamic programming loop over grid rows while maintaining a prefix sum array for the previous row. For each column, compute the number of reachable routes using a prefix range difference. The same logic works in Python, Java, C++, and Go with O(m * n) time complexity.
How to solve Count Routes to Climb a Rectangular Grid in O(m*n)?
Use a dynamic programming array where dp[c] stores the number of ways to reach column c in the current row. Before computing the next row, build a prefix sum array of dp. For every column, compute valid transitions from the previous row using prefix range queries in O(1). This converts repeated range summation into constant-time operations.
What is the best approach for Count Routes to Climb a Rectangular Grid?
The most efficient approach uses dynamic programming combined with prefix sums. Each row builds the number of ways to reach its cells using the previous row, while prefix sums allow fast range aggregation. This reduces the complexity from O(m * n^2) to O(m * n) and avoids repeated summation across columns.
Is Count Routes to Climb a Rectangular Grid asked at Google/Amazon/Meta?
Grid path counting with dynamic programming and prefix sum optimization appears frequently in interviews at companies like Google, Amazon, and Meta. Variants often involve counting paths across rows with restricted column transitions or distance constraints.
What data structure is used in Count Routes to Climb a Rectangular Grid?
The solution mainly relies on arrays for dynamic programming and prefix sum computation. The grid is treated as a matrix while prefix arrays enable fast range sum queries for transitions between rows.
What is the time complexity of Count Routes to Climb a Rectangular Grid?
The optimized solution runs in O(m * n) time where m is the number of rows and n is the number of columns. Each cell is processed once and range transitions are computed in constant time using prefix sums. Space complexity can be reduced to O(n) by storing only the previous row.

Ready to solve this problem?

Practice Count Routes to Climb a Rectangular Grid with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays