Grid Unique Paths

Problem Overview

In this article, we'll explore the LeetCode problem titled "Unique Paths." The challenge revolves around finding the number of distinct paths from the top-left corner of a grid to the bottom-right corner, using only moves to the right or down. This problem falls under the domain of combinatorial dynamic programming and is a classic example of problems involving paths and counting.

Understanding the Problem

Given a grid with dimensions m x n, your task is to determine how many unique ways you can start from the top-left corner [0,0] and reach the bottom-right corner [m-1,n-1], with the constraint that you can only move either down or right at any point in time.

Constraints

• Grid dimensions: m rows and n columns, where 1 <= m, n <= 100.
• No obstacles are present in the grid, meaning every cell is traversable.

Example

Imagine a 3x2 grid:

[ Start -> .     |     .     ]
[     v       |     v       ]
[     .     -> . -> Finish ]

For a 3 x 2 (3 rows and 2 columns) grid, there are 3 unique paths to reach the bottom-right cell.

Key DSA Concepts and Theory

Combinatorial Paths

The problem of "Unique Paths" can be solved using combinatorial methods. Since movement is restricted to right or down moves, each path is a combination of m-1 downs and n-1 rights. Thus, the problem translates to choosing m-1 down moves (or n-1 right moves) from the total m+n-2 movements, which is a combination problem:

[ C(m+n-2, m-1) = \frac{(m+n-2)!}{(m-1)!(n-1)!} ]

Dynamic Programming

We can also solve this problem using dynamic programming, where we build up the number of ways to reach each cell by leveraging previously computed results.

Solution Approach

We'll explore two approaches: dynamic programming and combinatorial mathematics.

Dynamic Programming Approach

1. Initialization: Create a 2D array dp with dimensions m x n, where dp[i][j] represents the number of unique paths to reach cell (i, j).

2. Base Case: Set dp[0][j] = 1 for all j and dp[i][0] = 1 for all i since there's only one way to reach cells in the first row or column — moving in a straight line.

3. State Transition: For other cells (i, j), use: [ dp[i][j] = dp[i-1][j] + dp[i][j-1] ] Each position is reached either from the top (i-1, j) or left (i, j-1).

4. Result: The number of unique paths to the bottom-right corner is stored in dp[m-1][n-1].

C++ Code

#include <vector>
using namespace std;

int uniquePaths(int m, int n) {
    vector<vector<int>> dp(m, vector<int>(n, 1));
    for (int i = 1; i < m; ++i) {
        for (int j = 1; j < n; ++j) {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }
    return dp[m - 1][n - 1];
}

Java Code

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            dp[i][0] = 1;
        }
        for (int j = 0; j < n; j++) {
            dp[0][j] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
}

Combinatorial Approach

We calculate the number of unique paths using combinations:

[ \text{uniquePaths} = C(m+n-2, m-1) = \frac{(m+n-2)!}{(m-1)!(n-1)!} ]

This can be calculated more efficiently by cancelling terms:

C++ Code

#include <vector>
using namespace std;

int uniquePaths(int m, int n) {
    long long int paths = 1;
    for (int i = 1; i <= m - 1; i++) {
        paths = paths * (n - 1 + i) / i;
    }
    return (int)paths;
}

Java Code

class Solution {
    public int uniquePaths(int m, int n) {
        long paths = 1;
        for (int i = 1; i <= m - 1; i++) {
            paths = paths * (n - 1 + i) / i;
        }
        return (int)paths;
    }
}

Time and Space Complexity Analysis

• Dynamic Programming Solution:

  • Time Complexity: (O(m \times n)) because we fill m*n cells in the table.
  • Space Complexity: (O(m \times n)) for storing the DP table.

• Combinatorial Solution:

  • Time Complexity: (O(\min(m, n))), since we compute up to m-1 or n-1 factors.
  • Space Complexity: (O(1)) as we use only a constant amount of extra space.

Common Mistakes to Avoid

• Misunderstanding grid boundaries: Always ensure that index operations stay within the boundaries of the grid.
• Not initializing the base cases correctly for the dynamic programming table: The first row and column should be fully initialized with 1s.
• Handling large numbers in combinatorial approach: Use long data types to handle larger intermediate results while computing factorials to avoid overflow.

Similar Problems on LeetCode

1. 62. Unique Paths II: Variant with obstacles.
2. 63. Minimum Path Sum: Finding the path with the minimum sum.
3. 64. Grid Unique Paths: A similar problem but optimized for different grid constraints.

Additional Resources and References

• Consider exploring texts on dynamic programming such as "Introduction to Algorithms" by Cormen et al. for a deeper understanding.
• For combinatorics, "Concrete Mathematics" by Graham, Knuth, and Patashnik offers foundational insights on combinatorial solutions.

By approaching this problem with both dynamic programming and combinatorial methods, we gain a versatile toolkit for tackling similar path-finding challenges in grid-based problems.