We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Number of Ways to Reach Destination in the Grid

Number: 3198

Difficulty: Hard

Paid? Yes

Companies: Uber

Problem Description

Given an n x m grid (indexed from 1) and two cells – source and dest – count the number of valid sequences of exactly k moves that take you from source to dest. In one move you may jump from a cell to any cell in the same row or the same column (but not remain in the same cell), and every intermediate cell must lie inside the grid. Since the answer can be huge, return it modulo 10^9+7.

Key Insights

  • The grid movement splits naturally into independent vertical (row) and horizontal (column) moves.
  • In each move you choose either to change rows or to change columns. In total, if you make r vertical moves and c horizontal moves (with r+c=k), then the vertical part must result in a net change equal to dest_row − source_row and similarly for the horizontal part.
  • Because from any cell you can jump to any other cell in that row/column, the transitions for rows (and similarly for columns) form a complete directed “graph” (without self loops) of size n (or m). The number of ways to go from one fixed vertex to another in t moves in such a graph can be computed in closed form using eigen‐decomposition.
  • The closed‐form formulas are:
    For a graph of size N, the number of t‑move walks from vertex a to b is:
    • If a == b: ( (N‑1)^t + (N‑1)⋅(–1)^t ) / N
    • If a != b: ( (N‑1)^t − (–1)^t ) / N
  • The overall answer is then summing over all splits of k moves into vertical and horizontal parts, with an extra combinatorial factor (the number of ways to interleave these moves).

Space and Time Complexity

Time Complexity: O(k) – mainly due to summing over the possible split of k moves, and precomputing factorials/inverses for binomial coefficients. Space Complexity: O(k) – for storing factorials and inverse factorials up to k.

Solution

We first note that a valid path consists of a mix of vertical moves (affecting the row coordinate) and horizontal moves (affecting the column coordinate). Let r be the number of vertical moves and c = k − r be the number of horizontal moves. For each such split, the ways to perform vertical moves from source_row to dest_row can be computed using the formula for complete graphs:   • If source_row == dest_row: vertical_ways = ( (n−1)^r + (n−1)⋅(–1)^r ) / n
  • If source_row != dest_row: vertical_ways = ( (n−1)^r − (–1)^r ) / n
A similar expression holds for horizontal moves (using m and the source/dest column values).

Since the order in which the vertical and horizontal moves occur matters, we multiply the product of the two counts by C(k, r) (i.e. “k choose r”) for interleaving.

The final answer is the sum over all valid splits of the product:   answer = Σ[r=0 to k] ( C(k, r) * vertical_ways(r) * horizontal_ways(k − r) ) mod (10^9+7)

To handle large k, we precompute factorials and inverse factorials modulo (10^9+7) to calculate binomial coefficients efficiently. Exponentiations and modulo inversions are computed using fast modular exponentiation.

Code Solutions

# Python solution with detailed comments
MOD = 10**9 + 7

# Fast modular exponentiation
def mod_pow(base, exp, mod):
    result = 1
    base %= mod
    while exp:
        if exp & 1:
            result = (result * base) % mod
        base = (base * base) % mod
        exp //= 2
    return result

# Precompute factorials and inverse factorials up to max_n (which will be k)
def precompute_factorials(max_n, mod):
    fact = [1]*(max_n+1)
    inv_fact = [1]*(max_n+1)
    for i in range(2, max_n+1):
        fact[i] = fact[i-1] * i % mod
    inv_fact[max_n] = mod_pow(fact[max_n], mod-2, mod)
    for i in range(max_n, 0, -1):
        inv_fact[i-1] = inv_fact[i] * i % mod
    return fact, inv_fact

# Binomial coefficient nCk modulo mod
def nCk(n, k, fact, inv_fact, mod):
    if k < 0 or k > n:
        return 0
    return fact[n] * inv_fact[k] % mod * inv_fact[n-k] % mod

def number_of_ways(n, m, k, source, dest):
    fact, inv_fact = precompute_factorials(k, MOD)
    
    src_row, src_col = source[0], source[1]
    dest_row, dest_col = dest[0], dest[1]
    
    # Helper function to calculate ways on complete graph of size N in t moves
    # a indicates if the start and end are the same (True) or not.
    def ways_on_line(N, t, same):
        term1 = mod_pow(N-1, t, MOD)  # (N-1)^t
        # (-1)^t mod MOD: if t is even then 1, else MOD -1
        term2 = 1 if t % 2 == 0 else MOD - 1
        if same:
            # ( (N-1)^t + (N-1)*(-1)^t ) / N
            result = (term1 + (N-1)*term2) % MOD
        else:
            # ( (N-1)^t - (-1)^t ) / N
            result = (term1 - term2) % MOD
        # Multiply by modular inverse of N to perform division modulo MOD
        result = result * mod_pow(N, MOD-2, MOD) % MOD
        return result
    
    total = 0
    # Try every possible split: r vertical moves and (k-r) horizontal moves
    for r in range(k+1):
        c = k - r
        # For vertical moves: only valid if r = 0 when source and dest are same.
        if src_row != dest_row or r > 0:
            vertical = ways_on_line(n, r, src_row == dest_row)
        else:
            vertical = 0
            
        if src_col != dest_col or c > 0:
            horizontal = ways_on_line(m, c, src_col == dest_col)
        else:
            horizontal = 0
            
        interleave = nCk(k, r, fact, inv_fact, MOD)
        total = (total + interleave * vertical % MOD * horizontal) % MOD
    return total

# Example usage:
# Example 1:
print(number_of_ways(3, 2, 2, [1,1], [2,2]))  # Output should be 2
# Example 2:
print(number_of_ways(3, 4, 3, [1,2], [2,3]))  # Output should be 9
← Back to All Questions