Number of Ways to Reach Destination in the Grid solution and explanation
The problem
You are given two integers n and m which represent the size of a 1-indexed grid. You are also given an integer k, a 1-indexed integer array source and a 1-indexed integer array dest, where source and dest are in the form [x, y] representing a cell on the given grid.
You can move through the grid in the following way:
- You can go from cell
[x1, y1]to cell[x2, y2]if eitherx1 == x2ory1 == y2. - Note that you can't move to the cell you are already in e.g.
x1 == x2andy1 == y2.
Return the number of ways you can reach dest from source by moving through the grid exactly k times.
Since the answer may be very large, return it modulo 109 + 7.
Example 1:
Input: n = 3, m = 2, k = 2, source = [1,1], dest = [2,2] Output: 2 Explanation: There are 2 possible sequences of reaching [2,2] from [1,1]: - [1,1] -> [1,2] -> [2,2] - [1,1] -> [2,1] -> [2,2]
Example 2:
Input: n = 3, m = 4, k = 3, source = [1,2], dest = [2,3] Output: 9 Explanation: There are 9 possible sequences of reaching [2,3] from [1,2]: - [1,2] -> [1,1] -> [1,3] -> [2,3] - [1,2] -> [1,1] -> [2,1] -> [2,3] - [1,2] -> [1,3] -> [3,3] -> [2,3] - [1,2] -> [1,4] -> [1,3] -> [2,3] - [1,2] -> [1,4] -> [2,4] -> [2,3] - [1,2] -> [2,2] -> [2,1] -> [2,3] - [1,2] -> [2,2] -> [2,4] -> [2,3] - [1,2] -> [3,2] -> [2,2] -> [2,3] - [1,2] -> [3,2] -> [3,3] -> [2,3]
Constraints:
2 <= n, m <= 1091 <= k <= 105source.length == dest.length == 21 <= source[1], dest[1] <= n1 <= source[2], dest[2] <= m
Approach overview
Problem Overview: You start at a cell in an m x n grid and must reach a destination cell in exactly k moves. In one move you can jump to any other cell in the same row or the same column. The task is to count how many valid sequences of moves reach the destination after exactly k steps.
Approach 1: Brute Force DFS Enumeration (Exponential Time)
A direct idea is to simulate every possible move sequence. From each cell you can jump to (n-1) cells in the same row and (m-1) cells in the same column. Recursively explore all possibilities until k moves are used, then check whether the current cell equals the destination. This approach explores roughly ((m+n)^k) possibilities, leading to O((m+n)^k) time and O(k) recursion space. It quickly becomes infeasible even for moderate k, but it helps reveal the structure of the state transitions.
Approach 2: Dynamic Programming by Relative Position (O(k))
The key observation: the exact cell is less important than its relationship to the destination. Every position falls into one of four categories: exactly at the destination, same row as the destination, same column as the destination, or completely different row and column. Instead of tracking all m * n cells, you track counts for these four states.
Use dynamic programming where dp[i][state] represents the number of ways to be in that relative state after i moves. Transitions are derived using grid counts. For example, from the destination you can move to any other cell in the same row (n-1 choices) or column (m-1 choices). From the "same row" state you can move back to the destination, to other same-row cells, or to cells that share the destination's column. The counts depend on simple combinatorial quantities such as n-2 or m-2.
This compression reduces the state space to just four integers per step. Each iteration updates them using arithmetic and modulo operations. The total complexity becomes O(k) time and O(1) space. The transitions rely on counting valid targets using basic combinatorics and grid dimensions, which avoids iterating through the grid entirely.
Mathematically, the DP behaves like a small state machine where each step redistributes counts between the four categories. Because the number of states is constant, performance depends only on k, not on m or n. This makes it efficient even when the grid is very large.
Recommended for interviews: The compressed dynamic programming approach. Interviewers expect you to recognize that tracking every cell is unnecessary and that only the relationship to the destination matters. Mentioning the brute force approach first shows understanding of the move structure, but reducing the problem to four states using math and DP demonstrates strong problem‑solving skill.
Solution
We define the following states:
f[0]represents the number of ways to move fromsourcetosourceitself;f[1]represents the number of ways to move fromsourceto another row in the same column;f[2]represents the number of ways to move fromsourceto another column in the same row;f[3]represents the number of ways to move fromsourceto another row and another column.
Initially, f[0] = 1, and the other states are all 0.
For each state, we can calculate the current state based on the previous state, as follows:
$
\begin{aligned}
g[0] &= (n - 1) times f[1] + (m - 1) times f[2] \
g[1] &= f[0] + (n - 2) times f[1] + (m - 1) times f[3] \
g[2] &= f[0] + (m - 2) times f[2] + (n - 1) times f[3] \
g[3] &= f[1] + f[2] + (n - 2) times f[3] + (m - 2) times f[3]
\end{aligned}
We loop k times, and finally check whether source and dest are in the same row or column, and return the corresponding state.
The time complexity is O(k), where k is the number of moves. The space complexity is O(1)$.
class Solution:
def numberOfWays(
self, n: int, m: int, k: int, source: List[int], dest: List[int]
) -> int:
mod = 10**9 + 7
f = [1, 0, 0, 0]
for _ in range(k):
g = [0] * 4
g[0] = ((n - 1) * f[1] + (m - 1) * f[2]) % mod
g[1] = (f[0] + (n - 2) * f[1] + (m - 1) * f[3]) % mod
g[2] = (f[0] + (m - 2) * f[2] + (n - 1) * f[3]) % mod
g[3] = (f[1] + f[2] + (n - 2) * f[3] + (m - 2) * f[3]) % mod
f = g
if source[0] == dest[0]:
return f[0] if source[1] == dest[1] else f[2]
return f[1] if source[1] == dest[1] else f[3]class Solution {
public int numberOfWays(int n, int m, int k, int[] source, int[] dest) {
final int mod = 1000000007;
long[] f = new long[4];
f[0] = 1;
while (k-- > 0) {
long[] g = new long[4];
g[0] = ((n - 1) * f[1] + (m - 1) * f[2]) % mod;
g[1] = (f[0] + (n - 2) * f[1] + (m - 1) * f[3]) % mod;
g[2] = (f[0] + (m - 2) * f[2] + (n - 1) * f[3]) % mod;
g[3] = (f[1] + f[2] + (n - 2) * f[3] + (m - 2) * f[3]) % mod;
f = g;
}
if (source[0] == dest[0]) {
return source[1] == dest[1] ? (int) f[0] : (int) f[2];
}
return source[1] == dest[1] ? (int) f[1] : (int) f[3];
}
}class Solution {
public:
int numberOfWays(int n, int m, int k, vector<int>& source, vector<int>& dest) {
const int mod = 1e9 + 7;
vector<long long> f(4);
f[0] = 1;
while (k--) {
vector<long long> g(4);
g[0] = ((n - 1) * f[1] + (m - 1) * f[2]) % mod;
g[1] = (f[0] + (n - 2) * f[1] + (m - 1) * f[3]) % mod;
g[2] = (f[0] + (m - 2) * f[2] + (n - 1) * f[3]) % mod;
g[3] = (f[1] + f[2] + (n - 2) * f[3] + (m - 2) * f[3]) % mod;
f = move(g);
}
if (source[0] == dest[0]) {
return source[1] == dest[1] ? f[0] : f[2];
}
return source[1] == dest[1] ? f[1] : f[3];
}
};func numberOfWays(n int, m int, k int, source []int, dest []int) int {
const mod int = 1e9 + 7
f := []int{1, 0, 0, 0}
for i := 0; i < k; i++ {
g := make([]int, 4)
g[0] = ((n-1)*f[1] + (m-1)*f[2]) % mod
g[1] = (f[0] + (n-2)*f[1] + (m-1)*f[3]) % mod
g[2] = (f[0] + (m-2)*f[2] + (n-1)*f[3]) % mod
g[3] = (f[1] + f[2] + (n-2)*f[3] + (m-2)*f[3]) % mod
f = g
}
if source[0] == dest[0] {
if source[1] == dest[1] {
return f[0]
}
return f[2]
}
if source[1] == dest[1] {
return f[1]
}
return f[3]
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force DFS Enumeration | O((m+n)^k) | O(k) | Useful only for understanding the transition rules or very small k |
| Full Grid Dynamic Programming | O(k * m * n) | O(m * n) | Conceptual DP that tracks every cell; simpler but too slow for large grids |
| Compressed State DP (Row/Column Relation) | O(k) | O(1) | Optimal approach for large grids; tracks only four relative states |
Frequently asked questions
Is Number of Ways to Reach Destination in the Grid easy or hard?
The problem is classified as Hard because the grid size can be very large, making naive DP impossible. The challenge is recognizing that the exact coordinates do not matter and that only the relationship to the destination determines transitions. Once the four-state DP is identified, the implementation becomes straightforward.
Number of Ways to Reach Destination in the Grid Python/Java solution
Implement the compressed DP with four variables representing the states relative to the destination. Loop for k steps, update each state using grid counts and modulo operations, and return the value representing the destination state. The same logic translates directly to Python, Java, C++, and Go.
How to solve Number of Ways to Reach Destination in the Grid in O(k)?
Define four DP states representing the relationship of the current cell to the destination: exact cell, same row, same column, and different row/column. For each move, compute how many cells each state can transition to using counts like (n−1), (m−1), (n−2), and (m−2). Update these four values iteratively for k steps while applying modulo arithmetic.
What is the best approach for Number of Ways to Reach Destination in the Grid?
The optimal solution uses dynamic programming with state compression. Instead of tracking every grid cell, you classify positions based on their relationship to the destination: at destination, same row, same column, or different row and column. Transition counts are computed using combinatorics from grid dimensions. This reduces the complexity to O(k) time and O(1) space.
Is Number of Ways to Reach Destination in the Grid asked at Google/Amazon/Meta?
Grid dynamic programming and combinatorics problems like this commonly appear in interviews at companies such as Google, Amazon, and Meta. Variants that require counting paths with constrained moves or compressed DP states are particularly popular in system design and algorithm rounds.
What data structure is used in Number of Ways to Reach Destination in the Grid?
The core technique is dynamic programming using a small fixed-size array or variables to represent four states. No complex data structures are required. The transitions rely on mathematical counting and simple integer arithmetic.
What is the time complexity of Number of Ways to Reach Destination in the Grid?
The optimized dynamic programming solution runs in O(k) time because only four state values are updated for each move. Space complexity is O(1) since the algorithm keeps only the current counts of the four states. Brute force enumeration would take exponential time roughly O((m+n)^k).