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:
[x1, y1] to cell [x2, y2] if either x1 == x2 or y1 == y2.x1 == x2 and y1 == 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] <= mProblem 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.
We define the following states:
f[0] represents the number of ways to move from source to source itself;f[1] represents the number of ways to move from source to another row in the same column;f[2] represents the number of ways to move from source to another column in the same row;f[3] represents the number of ways to move from source to 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)$.
| 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 |
NUMBER OF ISLANDS - Leetcode 200 - Python • NeetCode • 384,140 views views
Watch 9 more video solutions →Practice Number of Ways to Reach Destination in the Grid with our built-in code editor and test cases.
Practice on FleetCode