Unique Paths

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 * 109.

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

Approach: Dynamic Programming (Bottom-Up)

Algorithm

1. Let dp[i][j] be the number of unique paths to reach cell (i, j)
2. The robot can only arrive from above (dp[i - 1][j]) or from the left (dp[i][j - 1]), so dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
3. The first row and first column each have exactly 1 path (only moving right/down)
4. Return dp[m - 1][n - 1]

Time & Space Complexity

• Time Complexity: O(m × n) - visit every cell once
• Space Complexity: O(m × n) - the 2D DP table (can be optimized to O(n))

Java Implementation

public class UniquePaths {

    /**
     * Count the number of unique paths from top-left to bottom-right.
     * @param m Number of rows
     * @param n Number of columns
     * @return Number of unique paths
     */
    public static int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];

        // First row: only one way (move right)
        for (int j = 0; j < n; j++) {
            dp[0][j] = 1;
        }
        // First column: only one way (move down)
        for (int i = 0; i < m; i++) {
            dp[i][0] = 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];
    }

    // Test method
    public static void main(String[] args) {
        System.out.println("Input: m = 3, n = 7");
        System.out.println("Output: " + uniquePaths(3, 7)); // Expected: 28

        System.out.println("Input: m = 3, n = 2");
        System.out.println("Output: " + uniquePaths(3, 2)); // Expected: 3
    }
}

Space-Optimized Implementation (O(n) Space)

Each row only depends on the previous row, so a single 1D array suffices.

public class UniquePathsOptimized {

    public static int uniquePaths(int m, int n) {
        int[] dp = new int[n];
        for (int j = 0; j < n; j++) {
            dp[j] = 1;
        }

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[j] = dp[j] + dp[j - 1];
            }
        }

        return dp[n - 1];
    }
}

Mathematical Alternative: Combinatorics

Any valid path consists of exactly m - 1 down moves and n - 1 right moves, for a total of (m - 1) + (n - 1) moves. The answer is the binomial coefficient:

C((m - 1) + (n - 1), m - 1)

Example Walkthrough

For m = 3, n = 2:

1. Row 0: [1, 1]
2. Row 1: dp[1][1] = dp[0][1] + dp[1][0] = 1 + 1 = 2
3. Row 2: dp[2][1] = dp[1][1] + dp[2][0] = 2 + 1 = 3

Answer: 3.

Key Points

1. Only Two Moves: Down and right, so each cell depends on exactly two neighbors
2. Base Cases: First row and first column have exactly one path
3. O(n) Space Option: Process row by row with a 1D array
4. Combinatorics: The answer is C(m + n - 2, m - 1)
5. Answer Bound: Answers fit within 2 * 10^9, safe for int