Unique Paths - 1D DP 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.

const UPDATED_CELL = 'updated_cell', UPDATED_CELL_COLOR = 'gold';

function visMainFunction(m, n) {
    initClassProperties();
    explanationAndColorSchemaNotifications();

    startPartialBatch();
    const dp = new VisArray(n).fill(1);
    let rowIndex = 1;
    makeVisVariable(rowIndex).options({label: 'rowIndex'}).createVis();
    makeVisVariable(m).options({label: 'm (Number of Rows)'}).createVis();

    notification(`
        🎯 <b>Initialization complete:</b>
        <ul>
            <li>Each cell in the <b>first row</b> can be reached through exactly <b>one unique path</b> — by moving only rightward from the starting cell.</li>
            <li>Accordingly, the initial DP array is filled with <b>1s</b>, representing the number of ways to reach each cell in the first row.</li>
            <li>We’ll begin our iteration from <b>rowIndex = 1</b> (the second row), since the first row’s paths are already known.</li>
            <li>In the upcoming loop, we’ll systematically update the DP array to reflect the number of ways to reach each cell in the current row, reusing and overwriting values as we move from left to right.</li>
        </ul>
    `);
    endBatch();

    while (rowIndex < m) {
        startPartialBatch();
        resetHighlights(dp);

        notification(`
            🔄 <b>Calculating the number of paths to reach each cell in row ${rowIndex}:</b>
            <ul>
                <li>Initially, the DP array contains the number of ways to reach each cell in the previous row.</li>
                <li>The first cell in each row (<b>col 0</b>) can be reached through exactly <b>1 path</b> (coming straight down).</li>
                <li>Because of that, we can skip recomputing <b>col 0</b> and start updates from <b>col 1</b> — 
                    <em><b>col 0</b> already stores the correct number of paths (1), since the first cell in every previous row could also be reached through exactly one path.</em>
                </li>
                <li>Cells highlighted with a <b>${makeColoredSpan(`${UPDATED_CELL_COLOR} background`, UPDATED_CELL_COLOR)}</b> indicate that their values have been updated for the current row. 
                    Non-highlighted cells still hold the previous row’s values.</li>
                <li>For each cell (<b>row ${rowIndex}, colIndex</b>), we calculate how many ways it can be <b>reached</b> — as the sum of:
                    <ol>
                    <li>The number of ways to reach the cell above (<b>row ${rowIndex - 1}, col ${'colIndex'}</b>), 
                        still stored in <code>dp[colIndex]</code> since it has not been overwritten yet.</li>
                    <li>The number of ways to reach the cell to the left (<b>row ${rowIndex}, col ${'colIndex - 1'}</b>), 
                        stored in <code>dp[colIndex - 1]</code>, which has already been updated for the current row.</li>
                    </ol>
                </li>
            </ul>
        `);

        endBatch();

        let colIndex = 1;

        while (colIndex < n) {
            startPartialBatch();

            notification(`
                📌 <b>Calculating the number of paths to reach the cell (<code>row ${rowIndex}, col ${colIndex}</code>):</b>
                <ul>
                    <li>To reach this cell, there are two possibilities:</li>
                    <ol>
                    <li><b>From above</b> (<code>row ${rowIndex - 1}, col ${colIndex}</code>), represented by <b>dp[${colIndex}]</b>.<br/>
                        <em>dp[${colIndex}] currently holds the value from the previous row, as it has not been overwritten yet.</em><br/>
                        Paths from above = <b>dp[${colIndex}] = ${dp[colIndex]}</b>.
                    </li>
                    <li><b>From the left</b> (<code>row ${rowIndex}, col ${colIndex - 1}</code>), represented by <b>dp[${colIndex - 1}]</b>.<br/>
                        <em>dp[${colIndex - 1}] has already been updated for the current row.</em><br/>
                        Paths from left = <b>dp[${colIndex - 1}] = ${dp[colIndex - 1]}</b>.
                    </li>
                    </ol>
                    <li>Therefore, the total number of paths to reach this cell is <b>${dp[colIndex]} (above) + ${dp[colIndex - 1]} (left) = ${dp[colIndex] + dp[colIndex - 1]}</b>.</li>
                    <li>Now we update <b>dp[${colIndex}]</b> with this calculated value.</li>
                </ul>
            `);

            dp[colIndex] += dp[colIndex - 1];

            highlightIndex(dp, colIndex);
            colIndex += 1;

            endBatch();
        }

        rowIndex += 1;
    }

    notification(`🏁 <b>Finished!</b> Total number of unique paths from <b>top-left</b> to <b>bottom-right</b> is <b>${dp[n - 1]}</b>.`);
    return dp[n - 1];
}

function highlightIndex(arr, index) {
    arr.makeVisManagerForIndex(index).addClass(UPDATED_CELL);
}

function resetHighlights(arr) {
    startBatch();
    highlightIndex(arr, 0); // Highlight first cell as it's always valid
    for (let index = 1; index < arr.length; index++) {
        arr.makeVisManagerForIndex(index).removeClass(UPDATED_CELL);
    }
    endBatch();
}

function explanationAndColorSchemaNotifications() {
    explanationNotification();

    notification(`
        🎨 <b>Color Schema</b>:
        <ul>
            <li>
            <span style="background-color:${UPDATED_CELL_COLOR}; padding:2px 6px; border-radius:4px;">&nbsp;</span>
            — highlights cells in the DP array whose values have been <b>updated</b> for the current row.
            </li>
            <li>
            Non-highlighted cells still show the number of ways to reach their positions from the <b>previous row</b>.
            </li>
        </ul>
        This color distinction helps visualize which DP cells have just been recalculated
        and which ones are still carrying over values from the previous iteration.
    `);
}

function initClassProperties() {
    setClassProperties(UPDATED_CELL, {
        backgroundColor: UPDATED_CELL_COLOR
    });
}

Approach

We calculate the number of unique paths in an m × n grid from the top-left cell to the bottom-right cell using an optimized DP with O(n) space. The central idea is that to reach any cell, you can only come from the cell above it or the cell to its left — since movement is allowed only downward or rightward. Therefore, the total number of ways to reach a cell equals the sum of the ways to reach those two neighboring cells.

Because each cell depends on both its left neighbor (already updated for the current row) and its above neighbor (still stored from the previous row), the timing of updates aligns perfectly to allow using a single 1D array. As we move left to right, dp[col - 1] always contains the current row’s latest value, while dp[col] still represents the previous row’s value. This makes it possible to reuse one array without losing needed information.

State definition:
Maintain a one-dimensional array dp of length n. dp[col] stores the number of ways to reach the cell in the current row at column col from the start cell (top-left).
Initialization:
Set every entry of dp to 1. Each cell in the first row can be reached through exactly one unique path (moving only rightward), so the DP array starts as all ones.
Row processing (for each row rowIndex = 1 .. m-1):
- The first cell (col = 0) can be reached through exactly 1 path (coming straight down), and this was also true for every previous row. Therefore, we skip recomputing col 0 and start updates from col 1.
- For each column col = 1 .. n-1, we compute how many ways the cell can be reached:
  - From above — still stored in dp[col], since it hasn’t been overwritten yet for this row.
  - From the left — stored in dp[col - 1], which has already been updated for the current row.
  Then we update: dp[col] = dp[col] /* from above */ + dp[col - 1] /* from left */
Result:
After all rows are processed, dp[n - 1] holds the total number of unique paths from top-left to bottom-right.

Time Complexity

The algorithm iterates through all m × n cells in the grid once, updating the DP array for each cell. Each update involves only constant-time operations, so the overall running time is O(m × n).

Space Complexity

The algorithm maintains a 1D DP array of size n and only a few scalar constants alongside it, which do not increase the overall space complexity. Therefore, the space complexity is O(n).

Input-1

Unique Paths - 1D DP JS Solution

Solution code

Solution explanation

Solution explanation

Approach

Time Complexity

Space Complexity