Unique Paths - Combinatorial JS Solution

Editorial

Editorial solutions and visualizations are prepared with care, but we do not guarantee 100% accuracy or completeness. Please use your own judgment to verify results. Visucodize is not responsible for decisions made based on this content.

function visMainFunction(m, n) {
    explanationNotification();
    
    startBatch();
    const movesRight = n - 1;
    const movesDown = m - 1;

    // Use min/max naming for clarity
    const minMoves = Math.min(movesRight, movesDown);
    const maxMoves = Math.max(movesRight, movesDown);
    const totalMoves = movesDown + movesRight;
    let result = 1;

    makeVisVariable(totalMoves).options({ label: 'totalMoves (m+n-2)' }).createVis();
    makeVisVariable(minMoves).options({ label: 'minMoves' }).createVis();
    makeVisVariable(maxMoves).options({ label: 'maxMoves' }).createVis();
    makeVisVariable(result).options({ label: 'Result' }).createVis();
    endBatch();

    notification(`
        🎯 <b>Initialization complete</b>:
        <ul>
            <li><b>Total moves</b> = <b>${totalMoves}</b>.</li>
            <li>We compute both:
                <ul>
                <li><b>minMoves</b> = <code>min(movesDown (${movesDown}), movesRight (${movesRight})) = ${minMoves}</code> — used as the <b>number of iterations</b>.</li>
                <li><b>maxMoves</b> = <code>max(movesDown (${movesDown}), movesRight (${movesRight})) = ${maxMoves}</code> — used as the <b>starting factor</b> in the product (<code>maxMoves + i</code> each step).</li>
                </ul>
            </li>
            <li>We iterate only <b>minMoves (${minMoves})</b> times because in the combination formula 
                <code>C(n, k) = C(n, n - k)</code>, the result is symmetric — choosing the smaller of 
                <code>k</code> and <code>n - k</code> minimizes the number of multiplicative steps, 
                improving efficiency without changing the outcome.</li>
        </ul>
        Using this setup, we evaluate 
        <code>C(${totalMoves}, ${minMoves})</code> by iterating <code>i = 1..${minMoves}</code>, multiplying by 
        <code>(${maxMoves} + i)</code> and dividing by <code>i</code> at each step.
    `);
    
    for (let i = 1; i <= minMoves; i++) {
        startPartialBatch();
        notification(`
            🔄 <b>Step ${i}</b>:
            <ul>
                <li>Multiply by <code>maxMoves + ${i} = ${maxMoves + i}</code></li>
                <li>Then divide by <b>${i}</b></li>
            </ul>
            <code>result = (result × (${maxMoves + i})) / ${i}</code>
        `);

        result = (result * (maxMoves + i)) / i;
        endBatch();
    }

    notification(`
        🏁 <b>Finished!</b><br/>
        The total number of unique paths is <b>${result}</b>.
    `);

    return result;
}

Approach

Intuition

The problem can be viewed as moving from the top-left corner of an m × n grid to the bottom-right corner. Each move must go either down or right, which means every valid path always consists of (m - 1) downward moves and (n - 1) rightward moves.

Since the total number of moves is fixed to (m + n - 2), finding the number of unique paths becomes a combinatorial selection problem—we choose which moves are downward (or equivalently, which moves are rightward). This corresponds to the binomial coefficient:

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

Computation Strategy

Compute:
- movesDown = m - 1
- movesRight = n - 1
- totalMoves = movesDown + movesRight
To optimize computation:
- minMoves = min(movesDown, movesRight) → used as the number of iterations.
- maxMoves = max(movesDown, movesRight) → used as the starting factor in each multiplication (maxMoves + i).
We iterate only minMoves times because the combination formula C(n, k) = C(n, n - k) is symmetric. Choosing the smaller of k and n - k minimizes multiplications without affecting the result.

Step-by-Step Calculation

We iteratively compute C(totalMoves, minMoves):

Initialize result = 1.
For each i from 1 to minMoves:
- Multiply result by (maxMoves + i).
- Divide result by i.

Result

After the loop, result holds the number of unique paths in the grid. This iterative approach avoids factorials and large intermediate values, achieving an efficient O(min(m, n)) time and O(1) space solution.

Time Complexity

Let m be the number of rows and n be the number of columns in the grid. Then minMoves = min(m - 1, n - 1). The algorithm evaluates the binomial coefficient by looping i = 1..minMoves, performing constant work (O(1)) in each step. Therefore, the overall time complexity is O(min(m, n)).

Space Complexity

The algorithm runs in O(1) space, using only a few scalar variables.

Input-1

Unique Paths - Combinatorial JS Solution

Solution code

Solution explanation

Solution explanation

Approach

Intuition

Computation Strategy

Step-by-Step Calculation

Result

Time Complexity

Space Complexity