Jobs

Interviews

Discussions

Unique Paths

Medium

Coupang

2 views

Topics:

Dynamic Programming

There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.

The test cases are generated so that the answer will be less than or equal to 2 * 10⁹.

Example 1:

Input: m = 3, n = 7
Output: 28

Example 2:

Input: m = 3, n = 2
Output: 3
Explanation: From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Down -> Down
2. Down -> Down -> Right
3. Down -> Right -> Down

Constraints:

1 <= m, n <= 100

Unique Paths

Medium

Coupang

2 views

Topics:

Dynamic Programming

Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.

The test cases are generated so that the answer will be less than or equal to 2 * 10⁹.

Example 1:

Input: m = 3, n = 7
Output: 28

Example 2:

Input: m = 3, n = 2
Output: 3
Explanation: From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Down -> Down
2. Down -> Down -> Right
3. Down -> Right -> Down

Constraints:

1 <= m, n <= 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:

What are the constraints on the values of m and n? Specifically, what is the maximum possible value for each, and can either be zero or negative?
If either m or n is 1, should I return 1, representing the single path along the edge?
Are m and n always integers, or could they be other numeric types?
Is there any concern about integer overflow when calculating the number of paths, given large values of m and n?
Could you provide a few example inputs and their expected outputs to ensure I fully understand the problem requirements?

Brute Force Solution

Approach

Imagine you're navigating a grid from the top left to the bottom right. The brute force approach involves trying every single possible path to get there. We explore each direction available at every step, one at a time, until we reach the end or get stuck.

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

Start at the top-left corner.
From there, you can only move either down or right. Try moving down first.
From that new spot, again try moving down if possible, or right if down is not an option because you're at the bottom.
Keep going until you either reach the bottom-right corner (success!) or go off the grid (failure).
If you reach the bottom-right corner, count that as one successful path.
Now, go back to the last spot where you had a choice (either down or right) and try the other direction. If there were no other options, go back further.
Keep repeating this process of trying every path, one direction at a time, until you've explored every possibility from every point.
The total number of successful paths you counted represents the number of unique paths.

Code Implementation

def unique_paths_brute_force(number_of_rows, number_of_columns):
    unique_path_count = 0

    def traverse_grid(current_row, current_column):
        nonlocal unique_path_count

        # Base case: Reached the destination
        if current_row == number_of_rows - 1 and current_column == number_of_columns - 1:
            unique_path_count += 1
            return

        # Explore moving down
        if current_row < number_of_rows - 1:
            # Prevents exceeding the grid's boundaries.
            traverse_grid(current_row + 1, current_column)

        # Explore moving right
        if current_column < number_of_columns - 1:
            # Prevents exceeding the grid's boundaries.
            traverse_grid(current_row, current_column + 1)

    # Start traversal from the top-left corner.
    traverse_grid(0, 0)

    return unique_path_count

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(2^(m+n)) – The brute force approach explores all possible paths by recursively trying to move right or down from each cell. In a grid of size m x n, any path from the top-left to the bottom-right requires a total of (m-1) downward moves and (n-1) rightward moves. At each step, we have two choices: move right or move down, resulting in a branching factor of 2. The depth of the recursion tree is roughly m+n. Therefore, the total number of possible paths explored grows exponentially with m and n, leading to a time complexity of O(2^(m+n)).

Space Complexity

O(m+n) – The brute force approach, described using recursion, explores each path until it reaches the end or goes off the grid. The maximum depth of the recursion stack is proportional to the number of steps needed to reach the bottom-right corner. In the worst case, the algorithm will call the recursive function until it reaches the bottom right corner of the grid. This requires at most m steps down and n steps right, meaning the maximum depth of the call stack is m + n. Therefore, the auxiliary space used by the recursion stack is O(m+n), where m and n are dimensions of the grid.

Optimal Solution

Approach

The best way to solve this is to realize that the number of ways to reach a spot is the sum of the ways to reach the spots above and to the left of it. We can build a grid that stores the number of ways to reach each location from the start.

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

Imagine the grid of possible spots we can move to.
The start position has one way to reach it - starting there. Fill that position in.
Each other position's value is simply the total number of ways you can come from above and from the left. Therefore, the number of unique paths to any given location is just the sum of the number of unique paths from the location directly above it and the location directly to its left.
Build the grid, filling it in row by row from top to bottom, using the rule in the step above.
The final answer will be the number in the bottom right corner of the grid, which represents all the unique paths to get to the destination.

Code Implementation

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

    # Initialize the starting position with one path.
    path_grid[0][0] = 1

    for row_index in range(number_of_rows):
        for column_index in range(number_of_columns):
            if row_index == 0 and column_index == 0:
                continue

            paths_from_above = 0
            if row_index > 0:
                # Add paths from the cell above.
                paths_from_above = path_grid[row_index - 1][column_index]

            paths_from_left = 0
            if column_index > 0:
                # Add paths from the cell to the left.
                paths_from_left = path_grid[row_index][column_index - 1]

            # Accumulate paths from above and left.
            path_grid[row_index][column_index] = paths_from_above + paths_from_left

    # The bottom-right cell contains total unique paths.
    return path_grid[number_of_rows - 1][number_of_columns - 1]

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(m*n) – The algorithm constructs an m x n grid to store the number of paths to each cell. It iterates through each cell of the grid once, calculating the number of paths to that cell based on the values of its top and left neighbors. This involves visiting each of the m * n cells in the grid. Therefore, the time complexity is directly proportional to the product of m and n.

Space Complexity

O(m * n) – The algorithm constructs a grid (or a 2D array) to store the number of ways to reach each cell. The dimensions of this grid are m x n, where m is the number of rows and n is the number of columns, representing the dimensions of the path. Therefore, the space required to store this grid grows linearly with both m and n. Thus, the auxiliary space used is proportional to m * n, which results in O(m * n) space complexity.

Edge Cases

Case	How to Handle
m or n is zero	Return 0, as no path exists if either dimension is zero.
m or n is negative	Return 0, as negative dimensions are invalid and indicate no path.
m and n are both 1	Return 1, as there is exactly one path: the robot is already at the destination.
Large values of m and n leading to integer overflow	Use a data type that can accommodate larger numbers, such as long, or consider using dynamic programming to avoid recalculating the same path counts repeatedly which also helps reduce stack overflow.
m is 1 and n is large	Return 1, as there's only one path: moving right n-1 times.
n is 1 and m is large	Return 1, as there's only one path: moving down m-1 times.
m and n are very large	Dynamic programming provides an efficient solution to avoid exponential time complexity and stack overflow issues of recursion.
Check for integer overflow when calculating intermediate path sums using dynamic programming	Use a larger data type or implement overflow detection and appropriate error handling to avoid incorrect results.

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:

What are the constraints on the values of m and n? Specifically, what is the maximum possible value for each, and can either be zero or negative?
If either m or n is 1, should I return 1, representing the single path along the edge?
Are m and n always integers, or could they be other numeric types?
Is there any concern about integer overflow when calculating the number of paths, given large values of m and n?
Could you provide a few example inputs and their expected outputs to ensure I fully understand the problem requirements?

Brute Force Solution

Approach

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

Start at the top-left corner.
From there, you can only move either down or right. Try moving down first.
From that new spot, again try moving down if possible, or right if down is not an option because you're at the bottom.
Keep going until you either reach the bottom-right corner (success!) or go off the grid (failure).
If you reach the bottom-right corner, count that as one successful path.
Now, go back to the last spot where you had a choice (either down or right) and try the other direction. If there were no other options, go back further.
Keep repeating this process of trying every path, one direction at a time, until you've explored every possibility from every point.
The total number of successful paths you counted represents the number of unique paths.

Code Implementation

def unique_paths_brute_force(number_of_rows, number_of_columns):
    unique_path_count = 0

    def traverse_grid(current_row, current_column):
        nonlocal unique_path_count

        # Base case: Reached the destination
        if current_row == number_of_rows - 1 and current_column == number_of_columns - 1:
            unique_path_count += 1
            return

        # Explore moving down
        if current_row < number_of_rows - 1:
            # Prevents exceeding the grid's boundaries.
            traverse_grid(current_row + 1, current_column)

        # Explore moving right
        if current_column < number_of_columns - 1:
            # Prevents exceeding the grid's boundaries.
            traverse_grid(current_row, current_column + 1)

    # Start traversal from the top-left corner.
    traverse_grid(0, 0)

    return unique_path_count

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Imagine the grid of possible spots we can move to.
The start position has one way to reach it - starting there. Fill that position in.
Each other position's value is simply the total number of ways you can come from above and from the left. Therefore, the number of unique paths to any given location is just the sum of the number of unique paths from the location directly above it and the location directly to its left.
Build the grid, filling it in row by row from top to bottom, using the rule in the step above.
The final answer will be the number in the bottom right corner of the grid, which represents all the unique paths to get to the destination.

Code Implementation

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

    # Initialize the starting position with one path.
    path_grid[0][0] = 1

    for row_index in range(number_of_rows):
        for column_index in range(number_of_columns):
            if row_index == 0 and column_index == 0:
                continue

            paths_from_above = 0
            if row_index > 0:
                # Add paths from the cell above.
                paths_from_above = path_grid[row_index - 1][column_index]

            paths_from_left = 0
            if column_index > 0:
                # Add paths from the cell to the left.
                paths_from_left = path_grid[row_index][column_index - 1]

            # Accumulate paths from above and left.
            path_grid[row_index][column_index] = paths_from_above + paths_from_left

    # The bottom-right cell contains total unique paths.
    return path_grid[number_of_rows - 1][number_of_columns - 1]

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
m or n is zero	Return 0, as no path exists if either dimension is zero.
m or n is negative	Return 0, as negative dimensions are invalid and indicate no path.
m and n are both 1	Return 1, as there is exactly one path: the robot is already at the destination.
Large values of m and n leading to integer overflow	Use a data type that can accommodate larger numbers, such as long, or consider using dynamic programming to avoid recalculating the same path counts repeatedly which also helps reduce stack overflow.
m is 1 and n is large	Return 1, as there's only one path: moving right n-1 times.
n is 1 and m is large	Return 1, as there's only one path: moving down m-1 times.
m and n are very large	Dynamic programming provides an efficient solution to avoid exponential time complexity and stack overflow issues of recursion.
Check for integer overflow when calculating intermediate path sums using dynamic programming	Use a larger data type or implement overflow detection and appropriate error handling to avoid incorrect results.