Unique Paths Solution

Problem Description

Given a grid of size m x n, find the number of unique paths a robot can take from the top-left corner to the bottom-right corner, where the robot can only move down or right.

Naive Approach (Brute Force - Recursion)

A straightforward approach is to use recursion. Start from the top-left corner and explore all possible paths. At each step, the robot can either move down or right. When the robot reaches the bottom-right corner, we increment the path count.

Code (Python)

def unique_paths_recursive(m, n):
    if m == 1 or n == 1:
        return 1
    return unique_paths_recursive(m - 1, n) + unique_paths_recursive(m, n - 1)

Time Complexity

O(2^(m+n)). In the worst case, the function explores all possible paths, leading to exponential time complexity.

Space Complexity

O(m+n). Due to the call stack during recursion.

This approach is highly inefficient for larger values of m and n due to overlapping subproblems.

Optimal Approach (Dynamic Programming)

A more efficient approach is to use dynamic programming. We can create a 2D array dp of size m x n where dp[i][j] represents the number of unique paths to reach cell (i, j). The base cases are the first row and first column, where the number of paths is always 1.

For any other cell (i, j), the number of unique paths is the sum of the paths from the cell above (i-1, j) and the cell to the left (i, j-1). This is because the robot can only move down or right.

Code (Python)

def unique_paths_dp(m, n):
    dp = [[0] * n for _ in range(m)]

    for i in range(m):
        dp[i][0] = 1
    for j in range(n):
        dp[0][j] = 1

    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i-1][j] + dp[i][j-1]

    return dp[m-1][n-1]

Time Complexity

O(m*n). We iterate through each cell in the m x n grid once.

Space Complexity

O(m*n). We use a 2D array of size m x n to store the number of unique paths for each cell.

Further Optimization (Space)

We can further optimize space complexity to O(n) by using only one row to store the current number of paths, since the previous row is no longer needed. This involves updating the array iteratively.

Code (Python)

def unique_paths_optimized(m, n):
    row = [1] * n

    for i in range(1, m):
        for j in range(1, n):
            row[j] += row[j-1]

    return row[n-1]

Time Complexity

O(m*n). We iterate through each cell in the m x n grid once.

Space Complexity

O(n). We use a 1D array of size n to store the number of unique paths for the current row.

Edge Cases

1. If either m or n is 1, there is only one possible path.
2. Both m and n are greater than 0, as per constraints.

Summary

The dynamic programming approach provides an efficient solution to find the number of unique paths in a grid. The space-optimized version further reduces memory usage, making it an ideal solution for larger grids.