0062. Unique Paths

leetcode

Problem Overview

The problem "Unique Paths" requires determining the number of unique paths from the top-left corner to the bottom-right corner of an m x n grid. The only allowed moves are either down or right.

Solution Outline

Preferred Structure: Use a 2D array (matrix) for dynamic programming (DP).
Brute Force vs Optimal Solution:
- Brute Force: Explore all possible paths recursively.
- Optimal Solution: Use dynamic programming to store the number of paths to each cell.
Algorithm Choice: Dynamic programming is most suitable. It has a time complexity of O(m*n) and space complexity of O(m*n).

Setup and Testing Skeleton

/**
 * Unique Paths - Determine the number of unique paths from top-left to bottom-right in a grid.
 * @param {number} m - The number of rows.
 * @param {number} n - The number of columns.
 * @returns {number} - The number of unique paths.
 */
function uniquePaths(cols, rows) {
    function rec(col, row) {
        if (col >= cols) {
            return null;
        }

        if (row >= rows) {
            return null;
        }
        return {col, row};
    }


    if (cols === 0 || rows  === 0) {
        return 0;
    }

    const dp = Array(cols).fill(1).map(() => Array(rows).fill(0));

    console.table(dp);

    let stack = [];

    dp[0][0] = 1;
    stack.push(rec(0,0));
    while (stack.length > 0) {
        let c = stack.pop();
        const right = rec(c.col + 1, c.row);
        const bot = rec(c.col, c.row + 1);

        // console.log(`right = ${JSON.stringify(right)}; bot = ${JSON.stringify(bot)};`)

        if (right) {

            dp[right.col][right.row] += 1;
            stack.push(right);
        }

        if (bot) {
            dp[bot.col][bot.row] += 1;
            stack.push(bot);
        }
        console.table(dp);

    }

    return dp[cols - 1][rows - 1];
}

// Test cases
const testCases = [
    { m: 3, n: 7, expected: 28 },
    { m: 3, n: 2, expected: 3 },
    { m: 7, n: 3, expected: 28 },
    { m: 3, n: 3, expected: 6 },
    { m: 1, n: 1, expected: 1 },
];

testCases.forEach((test, index) => {
    const result = uniquePaths(test.m, test.n);
    console.log(`Test Case ${index + 1}: ${result === test.expected ? 'Passed' : 'Failed'} 
    (Expected: ${test.expected}, Got: ${result})`);
});