2912. Number of Ways to Reach Destination in the Grid

Hard
Leetcode Link

Problem Description

In this problem, you're given a grid of size n by m and starting at a 1-indexed position called source, you need to find the number of distinct ways to reach another 1-indexed position called dest, by moving exactly k steps. The condition for moving is that you can only move to another cell in the same row or column, but not to the cell you are currently in. Since the number of possible ways can be quite large, you are required to return the answer modulo 10^9 + 7 to keep the number within manageable limits.

The movement rules imply you're only allowed to travel in a straight line horizontally or vertically before changing directions, and you cannot stay in the same cell if you're making a move.

The goal is to return the number of unique paths that take exactly k moves from the source to dest, under these constraints.

Intuition

The solution to this problem revolves around the concept of dynamic programming, which roughly involves breaking down a larger problem into smaller, similar subproblems and storing the results to avoid redundant computations.

Here, we use an array f which will represent the number of different ways to end at a cell, under different conditions, after taking some number of steps:

  1. f[0]: Staying at the source cell.
  2. f[1]: Being in another cell in the same column as the source.
  3. f[2]: Being in another cell in the same row as the source.
  4. f[3]: Being in any cell that is neither in the same row nor column as the source.

At the start, f[0] is 1 because there's exactly one way to be at the source - by not moving. The others are zero because we've taken no steps to move elsewhere.

For each step from 1 to k, you update these numbers based on where you can move from each of these states, which is derived from:

  • From f[0], you can go to any other cell in the same row (f[2]) or column (f[1]).
  • From f[1], you can stay in the same column (f[1]), move back to the source (f[0]), or move to a different row and column (f[3]).
  • From f[2], you can stay in the same row (f[2]), move back to the source (f[0]), or move to a different row and column (f[3]).
  • From f[3], you can move to other cells not in the same row or column (f[3]), or move to a cell in the same row (f[2]) or column (f[1]) as the source.

The formulae in the 'Reference Solution Approach' uses these ideas to update a new array g from the previous f, representing the state after taking another step. After k steps, g represents the possible ways to end in each of the four kinds of cell from the source.

Finally, you look at the relationship between the source and the destination: if they're in the same row or column, there are only certain ways you could have gotten there (f[0] and f[2] if in the same row, f[0] and f[1] if in the same column). If they're not, then f[3] is the result. You can return this final result as the answer.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Suppose k is a very large integer(2^64). Which of the following is the largest as n grows to infinity?

Solution Approach

The solution uses dynamic programming, with the core idea being to track how many ways we can be in certain positions on the board after a given number of moves. The positions are categorized into four types, each represented by an array f with four elements. A secondary array g is introduced to calculate the next state based on the current state of f.

Here is the explanation for the code and how it implements the dynamic programming approach:

  1. Initialize the modulo variable mod = 10^9 + 7, which will be used to keep results within the specified limit by taking the modulo after each computation.

  2. The array f is initialized with [1, 0, 0, 0] since we start at the source and there's exactly one way to be at the source itself without making any move.

  3. We loop k times, each time calculating a new array g based on the current state of f. The logic for calculating the next state is based on the movement rules of the problem:

    • g[0] updates the number of ways to stay at the source cell, which is calculated from all the ways to come from another column or row to the source cell.
    • g[1] computes the ways to be in a different row, same column (excluding the source cell). It includes the ways to come from the source cell, from different rows in the same column and from different columns and rows.
    • g[2] is for different column, same row (excluding the source), adding ways from the source cell, different columns in the same row, and different columns and rows.
    • g[3] adds ways to be in cells not in the same row or column as the source. This is derived from moving from cells that are in the same column but different rows, same row but different columns, and different rows and columns.

  4. The calculations use (n - 1), (m - 1), (n - 2), and (m - 2) because these terms represent the number of cells available to move into for each movement category described above (minus the current or source cell).

  5. After computing g, the current state of f is updated to this new state, because f needs to represent the state of the number of ways to reach certain positions after an additional move.

  6. After all k steps are completed, the final result depends on whether source and dest are in the same row or column. Separate checks are performed:

    • If source and dest are the exact same cell, then return f[0].
    • If they're in the same row but different cells, return f[2].
    • If they're in the same column but different cells, return f[1].
    • Otherwise, return f[3], which represents reaching a cell that is neither in the same row nor column as the source.

This approach effectively avoids repeating the calculation for each possible path by summarizing the results after each step and updating them iteratively, a hallmark of dynamic programming which makes the solution efficient, even for large k.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the following array represent a max heap?

Example Walkthrough

Let's consider a small example with a 3x3 grid n = 3, m = 3, a source at (1,1), a dest at (3,3), and k = 2 steps.

Let's walk through the two iterations of the loop (since k = 2) to understand how the dynamic programming approach calculates the number of ways to reach the destination.

  1. Initialization: Our initial state f is [1, 0, 0, 0], indicating there is 1 way to be in the source without moving.

  2. First iteration:

    • We create a new array g to represent the ways to be at different types of cells after one move.
    • g[0]: This is still 0 because there's no way to leave the source cell and return to it in one move.
    • g[1]: We can move to any of the two other cells in the same column, so g[1] = 2*(f[0] + f[3]) = 2 (from the source and from any other different row and column).
    • g[2]: Similarly, we can move to any of the two cells in the same row, so g[2] = 2*(f[0] + f[3]) = 2.
    • g[3]: We cannot reach cells in a different row and column in just one move, so g[3] = 0.
    • f is now updated to be g, so f = [0, 2, 2, 0].

  3. Second iteration:

    • We again calculate a new g.
    • g[0]: We can move back to the source cell only from cells in the same row or the same column, g[0] = f[1] + f[2] = 2 + 2 = 4.
    • g[1]: This includes ways from the source cell, same column, and different row/column, g[1] = (f[0] + (f[1]*(n - 2)) + f[3]) % mod = (0 + (2 * 1) + 0) % mod = 2.
    • g[2]: For different columns, same row, g[2] = (f[0] + (f[2]*(m - 2)) + f[3]) % mod = (0 + (2 * 1) + 0) % mod = 2.
    • g[3]: Ways to be not in the same row/column, g[3] = ((f[1] + f[2])*(n + m - 4) + f[3]*(n * m - n - m + 1)) % mod = (4 * 2 + 0) % mod = 8.
    • We update f = [4, 2, 2, 8].

At the end of k moves, to reach (3,3) from (1,1), we need to consider f[3] since dest is neither in the same row nor column as source. Therefore, there are 8 distinct ways to reach the destination in exactly 2 steps. This makes the final answer f[3] = 8.

Solution Implementation

1class Solution:
2    def number_of_ways(self, rows: int, cols: int, steps: int, source: List[int], destination: List[int]) -> int:
3        # Define modulo as per the problem statement to handle large numbers
4        mod = 10**9 + 7
5      
6        # Initialization of counts for different scenarios - staying, moving in rows, moving in cols, and moving diagonally
7        counts = [1, 0, 0, 0] 
8      
9        # Loop over the number of steps to compute the number of ways dynamically
10        for _ in range(steps):
11            # Create a new list to store updated counts after each step
12            new_counts = [0] * 4 
13          
14            # Update new counts based on the previous counts
15            new_counts[0] = ((rows - 1) * counts[1] + (cols - 1) * counts[2]) % mod
16            new_counts[1] = (counts[0] + (rows - 2) * counts[1] + (cols - 1) * counts[3]) % mod
17            new_counts[2] = (counts[0] + (cols - 2) * counts[2] + (rows - 1) * counts[3]) % mod
18            new_counts[3] = (counts[1] + counts[2] + (rows - 2) * counts[3] + (cols - 2) * counts[3]) % mod
19          
20            # Overwrite previous counts with the new computed counts
21            counts = new_counts
22      
23        # Based on the position of source and destination, return the appropriate count
24        if source[0] == destination[0]:
25            # If on the same row, return staying count or row move count
26            return counts[0] if source[1] == destination[1] else counts[2]
27        else:
28            # If not on the same row, return column move count or diagonal move count
29            return counts[1] if source[1] == destination[1] else counts[3]
30
31# Note: The class expects the `List` to be imported from `typing`, so you should add `from typing import List` at the top of the file.
32
1class Solution {
2    // Method to calculate the number of ways to reach from source to destination within k steps
3    public int numberOfWays(int rows, int cols, int steps, int[] source, int[] dest) {
4        final int mod = 1000000007; // Define the modulo value for large number handling
5        long[] waysCountByPositionType = new long[4]; // Create an array to hold numbers of ways for the 4 types of positions
6        waysCountByPositionType[0] = 1; // Initialize with 1 way to stand still (i.e., 0 step)
7      
8        // Loop through the number of steps
9        while (steps-- > 0) {
10            long[] newWaysCount = new long[4]; // Temp array to hold the new count of ways after each step
11          
12            // Calculate number of ways to stand still
13            newWaysCount[0] = ((rows - 1) * waysCountByPositionType[1] + (cols - 1) * waysCountByPositionType[2]) % mod;
14            // Calculate number of ways for a source placed on the row border, except corners
15            newWaysCount[1] = (waysCountByPositionType[0] + (rows - 2) * waysCountByPositionType[1] + (cols - 1) * waysCountByPositionType[3]) % mod;
16            // Calculate number of ways for a source placed on the column border, except corners
17            newWaysCount[2] = (waysCountByPositionType[0] + (cols - 2) * waysCountByPositionType[2] + (rows - 1) * waysCountByPositionType[3]) % mod;
18            // Calculate number of ways for a source placed at the corners
19            newWaysCount[3] = (waysCountByPositionType[1] + waysCountByPositionType[2] + (rows - 2) * waysCountByPositionType[3] + (cols - 2) * waysCountByPositionType[3]) % mod;
20
21            // After each step, update the count of ways
22            waysCountByPositionType = newWaysCount;
23        }
24      
25        // If source and destination are on the same row
26        if (source[0] == dest[0]) {
27            // If they are also on the same column, return the count of standing still
28            if (source[1] == dest[1]) {
29                return (int) waysCountByPositionType[0];
30            } else {
31                // Otherwise, return the count for column border
32                return (int) waysCountByPositionType[2];
33            }
34        } else {
35            // If source and destination are on the same column
36            if (source[1] == dest[1]) {
37                // Return the count for row border
38                return (int) waysCountByPositionType[1];
39            } else {
40                // Otherwise, return count for corners
41                return (int) waysCountByPositionType[3];
42            }
43        }
44    }
45}
46
1class Solution {
2public:
3    int numberOfWays(int numRows, int numCols, int maxMoves, vector<int>& start, vector<int>& end) {
4        const int MOD = 1e9 + 7; // Define the modulus for large numbers
5
6        // 'dp' holds the current number of ways to reach points with various starting and ending constraints
7        vector<long long> dp(4);
8        dp[0] = 1; // Initialize the first element representing no constraints
9
10        // Iterate 'maxMoves' times applying the transition between states
11        while (maxMoves--) {
12            // 'nextDp' will hold the next state of our dp array
13            vector<long long> nextDp(4);
14
15            nextDp[0] = ((numRows - 1) * dp[1] + (numCols - 1) * dp[2]) % MOD; // Updating with constraints on rows and columns
16            nextDp[1] = (dp[0] + (numRows - 2) * dp[1] + (numCols - 1) * dp[3]) % MOD; // Updating with constraint on rows
17            nextDp[2] = (dp[0] + (numCols - 2) * dp[2] + (numRows - 1) * dp[3]) % MOD; // Updating with constraint on columns
18            nextDp[3] = (dp[1] + dp[2] + (numRows - 2) * dp[3] + (numCols - 2) * dp[3]) % MOD; // Updating with constraints on both
19
20            dp = move(nextDp); // Move to the next state, avoiding copying
21        }
22
23        // Check if the starting and ending rows are the same
24        if (start[0] == end[0]) {
25            // If they are in the same row, check if they are also in the same column
26            return start[1] == end[1] ? dp[0] : dp[2];
27        }
28
29        // If they are not in the same row, they must be in the same column or different column
30        return start[1] == end[1] ? dp[1] : dp[3];
31    }
32};
33
1const MOD = 1e9 + 7; // Define the modulus for large numbers
2
3let dp: bigint[]; // 'dp' will hold the current number of ways to reach points with various constraints
4
5// Function to update the number of ways to reach given points
6function updateDp(numRows: number, numCols: number): bigint[] {
7    let nextDp = new Array<bigint>(4);
8    nextDp[0] = (((numRows - 1n) * dp[1] + (numCols - 1n) * dp[2]) % BigInt(MOD));
9    nextDp[1] = ((dp[0] + (numRows - 2n) * dp[1] + (numCols - 1n) * dp[3]) % BigInt(MOD));
10    nextDp[2] = ((dp[0] + (numCols - 2n) * dp[2] + (numRows - 1n) * dp[3]) % BigInt(MOD));
11    nextDp[3] = ((dp[1] + dp[2] + (numRows - 2n) * dp[3] + (numCols - 2n) * dp[3]) % BigInt(MOD));
12    return nextDp; // Return the updated dp array
13}
14
15// Function to calculate the number of ways to move on the grid
16function numberOfWays(numRows: number, numCols: number, maxMoves: number, start: number[], end: number[]): bigint {
17    dp = new Array<bigint>(4).fill(0n);
18    dp[0] = 1n; // Initialize the first element representing no constraints
19
20    // Iterate 'maxMoves' times applying the transition between states
21    for (let move = 0; move < maxMoves; move++) {
22        dp = updateDp(BigInt(numRows), BigInt(numCols)); // Move to the next state
23    }
24
25    // Check if the starting and ending positions are the same (row and column)
26    if (start[0] === end[0]) {
27        // If in the same row, check if they are also in the same column
28        return start[1] === end[1] ? dp[0] : dp[2];
29    }
30
31    // If not in the same row, they must be in the same column or a different column
32    return start[1] === end[1] ? dp[1] : dp[3];
33}
34
Not Sure What to Study? Take the 2-min Quiz：

How does merge sort divide the problem into subproblems?

Time and Space Complexity

The given Python code calculates the number of ways to reach from source to dest within k moves on an n * m grid. Each cell can be visited any number of times, and we can move in four directions: up, down, left, and right.

Time Complexity

The main operation that contributes to the time complexity is the for loop, which iterates exactly k times, where k is the number of moves. The operations inside the loop are constant-time operations because they involve arithmetic operations and assignment, which do not depend on the size of the grid. Therefore, the loop runs k times, each with O(1) operations, making the overall time complexity O(k).

Space Complexity

Regarding space complexity, we have constant space usage. The function uses a fixed amount of extra space for the variables f, g, and mod, and these do not scale with the input size n, m, or k. Even though f and g are lists, they always contain exactly four elements. Thus, the space complexity is O(1), which is independent of the input size.

Fast Track Your Learning with Our Quick Skills Quiz:

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27
1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30
1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

Recommended Readings

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Runtime to Algo Cheat Sheet

Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫