Taro Logo

Number of Ways to Reach Destination in the Grid

#153 Most AskedHard
41 views
Topics:
Dynamic ProgrammingArrays

You are in a city that consists of n x n blocks arranged in a grid. You want to reach the destination block (n - 1, n - 1), which is the bottom-right corner. You start at the source block (0, 0), which is the top-left corner.

You can move one block at a time, either in the down direction or in the right direction. However, you are required to move exactly k steps.

Given two integers n and k, return the number of possible ways to reach the destination block (n - 1, n - 1) by taking exactly k steps. Since the answer may be very large, return it modulo 109 + 7.

Example 1:

Input: n = 3, k = 6
Output: 5
Explanation: The following diagram shows all possible paths:
- (0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2)
- (0,0) -> (0,1) -> (1,1) -> (2,1) -> (2,2)
- (0,0) -> (1,0) -> (1,1) -> (1,2) -> (2,2)
- (0,0) -> (1,0) -> (1,1) -> (2,1) -> (2,2)
- (0,0) -> (1,0) -> (2,0) -> (2,1) -> (2,2)

Example 2:

Input: n = 2, k = 2
Output: 2
Explanation: The following diagram shows all possible paths:
- (0,0) -> (0,1) -> (1,1)
- (0,0) -> (1,0) -> (1,1)

Example 3:

Input: n = 2, k = 3
Output: 0
Explanation: It is not possible to reach the destination using exactly 3 steps.

Constraints:

  • 1 <= n <= 50
  • 1 <= k <= 100

Solution


Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

  1. What are the dimensions of the grid (number of rows and columns), and what is the data type and range for these dimensions?
  2. Are obstacles allowed in the grid? If so, how are they represented (e.g., as -1, 0, or another value)?
  3. Are we only allowed to move down and right, or are other movements (like up or left) permitted?
  4. Is the starting point always the top-left corner (0, 0), and the destination always the bottom-right corner (rows-1, cols-1)?
  5. If there is no valid path to the destination, what should the function return (e.g., 0, -1, or null)?

Brute Force Solution

Approach

The brute force approach to finding the number of ways to reach a destination in a grid involves trying every possible path. We start at the beginning and explore all available directions, eventually counting how many of these paths successfully lead to the end.

Here's how the algorithm would work step-by-step:

  1. Begin at the starting point of the grid.
  2. From the starting point, consider every possible direction you can move (usually right and down).
  3. For each possible move, imagine you've taken that step and are now at a new location.
  4. From this new location, again consider every possible direction you can move.
  5. Continue doing this, exploring all possible paths, until you either reach the destination or go off the grid.
  6. If you reach the destination, count that path as one successful way.
  7. If you go off the grid, discard that path and try another one.
  8. Repeat this process for every possible starting move and subsequent moves.
  9. Finally, count all the successful paths that led to the destination. This total is the number of ways to reach the destination using the brute-force method.

Code Implementation

def number_of_ways_brute_force(
    number_of_rows, number_of_columns
):
    number_of_ways = 0

    def explore_path(current_row, current_column):
        nonlocal number_of_ways

        # If we are out of bounds, this path is invalid
        if (
            current_row >= number_of_rows
            or current_column >= number_of_columns
        ):
            return

        # We found a way when we arrive at the destination
        if (
            current_row == number_of_rows - 1
            and current_column == number_of_columns - 1
        ):
            number_of_ways += 1
            return

        # Explore moving down
        explore_path(current_row + 1, current_column)

        # Explore moving right
        explore_path(current_row, current_column + 1)

    explore_path(0, 0)
    return number_of_ways

Big(O) Analysis

Time Complexity
O(2^(m+n)) – The brute force approach explores all possible paths in the grid. At each cell, we have two choices: move right or move down. In an m x n grid, to reach the destination from the top-left corner, we need to take m-1 steps down and n-1 steps right, a total of m+n-2 steps. Since at each step we potentially explore two paths, in the worst case, we explore all possible combinations of right and down moves, leading to an exponential growth in the number of paths explored. Therefore, the time complexity is O(2^(m+n)).
Space Complexity
O(m*n) – The brute force approach explores all possible paths using recursion. In the worst-case scenario, the recursion depth could be proportional to the number of cells in the grid, resulting in a call stack with a height of m*n, where m is the number of rows and n is the number of columns. Each recursive call requires a new stack frame, consuming memory. Therefore, the space complexity due to the recursion stack is O(m*n).

Optimal Solution

Approach

The key to efficiently finding the number of ways to reach the destination is recognizing overlapping subproblems. Instead of recalculating the same paths repeatedly, we remember the number of paths we've already found to each location.

Here's how the algorithm would work step-by-step:

  1. Imagine the grid as a map and you want to count the different ways to reach the bottom-right corner from the top-left corner.
  2. Notice that to get to any spot on the grid, you can only come from the spot above or the spot to the left.
  3. Start from the top-left corner, and set the number of ways to get there as 1 (because you start there).
  4. Now, move across the top row and down the left column. There is only one way to reach any cell in the first row or column, so mark each of these as 1.
  5. For every other spot in the grid, calculate the number of ways to reach that spot by adding the number of ways to reach the spot above it and the number of ways to reach the spot to its left.
  6. Continue this process until you reach the bottom-right corner. The number at the bottom-right corner is the total number of ways to reach the destination.
  7. This approach avoids recomputing paths by storing the number of paths to each grid location.

Code Implementation

def number_of_ways_to_reach_destination(
    number_of_rows, number_of_columns
):
    grid = [([0] * number_of_columns) for _ in range(number_of_rows)]

    grid[0][0] = 1

    for column_index in range(1, number_of_columns):
        # First row can only be reached from the left.
        grid[0][column_index] = 1

    for row_index in range(1, number_of_rows):
        # First column can only be reached from above.
        grid[row_index][0] = 1

    for row_index in range(1, number_of_rows):
        for column_index in range(1, number_of_columns):
            # Sum paths from above and the left.
            grid[row_index][column_index] = (
                grid[row_index - 1][column_index]
                + grid[row_index][column_index - 1]
            )

    # Return the number of ways to reach the destination.
    return grid[number_of_rows - 1][number_of_columns - 1]

Big(O) Analysis

Time Complexity
O(m*n) – The provided solution iterates through an m x n grid to calculate the number of ways to reach each cell. The outer loop iterates 'm' times (rows), and the inner loop iterates 'n' times (columns). Inside the inner loop, a constant-time operation (addition) is performed. Therefore, the total number of operations is proportional to m*n, representing the size of the grid. This results in a time complexity of O(m*n).
Space Complexity
O(M*N) – The algorithm creates a grid to store the number of ways to reach each cell. If the input grid has dimensions M rows and N columns, the auxiliary space required is proportional to the size of this grid. Therefore, the space complexity is O(M*N) because we store intermediate results (the number of paths) for each cell in the M x N grid. Specifically, we store a number for each cell calculated based on previous values in the matrix.

Edge Cases

Null or empty grid
How to Handle:
Return 0, as there are no paths in an empty grid.
1x1 grid (single cell)
How to Handle:
Return 1, as there is one way to reach the destination which is the starting point itself if start and destination are the same.
Grid with obstacles blocking all paths
How to Handle:
Return 0 if no path exists by checking if the final count from top left to bottom right is zero.
Large grid that could lead to integer overflow
How to Handle:
Use long or BigInteger to store the number of paths to prevent overflow.
Start or end point is an obstacle
How to Handle:
Return 0 immediately if the starting point or the destination is an obstacle, as no path is possible.
Very long and narrow grid (e.g., 1xN or Nx1)
How to Handle:
The algorithm should efficiently traverse the grid even if highly skewed.
Grid with negative values representing extremely costly paths (if applicable)
How to Handle:
If negative values are invalid, return 0, otherwise handle them based on the cost interpretation in path selection (if applicable and defined).
Maximum grid size to test memory constraints and efficiency
How to Handle:
Ensure the chosen approach (DP or recursion with memoization) doesn't exceed memory limits for the maximum grid size (within constraints).
0/495 completed