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).

Description Hints 6 Solution

2912. Number of Ways to Reach Destination in the Grid

Hard57.7% acceptance1 companyPremium elsewhere, free here

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 [x₁, y₁] to cell [x₂, y₂] if either x₁ == x₂ or y₁ == y₂.
Note that you can't move to the cell you are already in e.g. x₁ == x₂ and y₁ == y₂.

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 10⁹ + 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 <= 10⁹
1 <= k <= 10⁵
source.length == dest.length == 2
1 <= source[1], dest[1] <= n
1 <= source[2], dest[2] <= m

Asked at 1 company

Uber

Topics

Hints open one at a time

Hint 1

We are asked to count the number of sequences of length k + 1 that start from (x_s, y_s) and end with (x_d, y_d). i.e., (x_s, y_s), (x₁, y₁), ..., (x_{k - 1}, y_{k - 1}), (x_d, y_d).

Hint 2

The key point is to see x and y separately.

Hint 3

Suppose we do i vertical moves and k - i horizontal moves.

Hint 4

In each vertical move, we change only y. Now let's count the number of sequences of length i + 1 that start with source[2] and end with dest[2]. Let's call this number vertical_count.

Hint 5

Do the same for horizontal moves and let it be horizontal_count.

Hint 6

For each i, the number of ways would be vertical_count * horizontal_count * C(n, i) since the order of vertical and horizontal moves could be arbitrary.

Still stuck?Read the written solution.

Open solution

LanguageLoading editor…

1class Solution:
  def solve(self):
      pass


Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

3
2
2
[1,1]
[2,2]

Input

3
4
3
[1,2]
[2,3]

Your code is saved on this device.Solution