Start learning free

LESSON 328 OF 348 · DYNAMIC PROGRAMMING

Min Cost Climbing Stairs in TypeScript: One Pass, In-Place DP

Practice O(n) Read the full explanation

On a staircase, the i-th step has some non-negative cost cost[i] assigned (0 indexed).

Once you pay the cost, you can either climb one or two steps. You need to find minimum cost to reach the top floor, given that you can either start from the step with index 0 or the step with index 1. 

                             ___________
                        ___ | Final Step
                   ___ | 20
             ___ | 15
__________ | 10
First Step

Example 1:

Input: cost = [10, 15, 20]
Output: 15
Explanation: Cheapest is start on cost[1], pay that cost and go to the top.

Example 2:

Input: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
Output: 6
Explanation: Cheapest is start on cost[0], and only step on 1s, skipping cost[3].

Note:

  1. cost will have a length in the range [2, 1000].
  2. Every cost[i] will be an integer in the range [0, 999].

STEP 1 OF 3
    Ctrl + Enter to check

    TYPESCRIPT · DYNAMIC PROGRAMMING

    Min Cost Climbing Stairs in TypeScript, explained

    Problem overview

    The method minCostClimbingStairs(cost) receives an array where cost[i] is the price of standing on step i. After paying a step's price you may climb one or two steps. You can start on step 0 or on step 1, and the goal is the top of the staircase, which is one position past the last step. The method returns the cheapest total price to get there.

    For cost = [10, 15, 20] the answer is 15: start on step 1, pay 15, and jump two steps to the top. For cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] the answer is 6. Start on step 0 and use only the cheap steps, skipping the 100s by taking two-step jumps.

    Approach: the cheapest way to each step

    Trying every sequence of one-step and two-step moves means a number of paths that grows like the Fibonacci numbers. Dynamic programming avoids repeating work by asking one question per step: what is the cheapest total price to arrive on step i and pay for it?

    You can only get to step i from step i - 1 or step i - 2, so the answer is the step's own price plus the cheaper of those two totals. Steps 0 and 1 are free starting points, so their totals are just their own prices.

    The top is reached from either of the last two steps, without paying for anything beyond them. The result is therefore the smaller of the final two totals.

    The lesson stores the totals in cost itself. Each entry is read two steps later and then no longer needed in its original form, so no second array is required. For [10, 15, 20], step 2 becomes 20 + min(15, 10) = 30. The last two totals are 15 and 30, and the answer is 15.

    Step by step

    1. Loop from index 2. The first two entries already hold the right totals, so the loop begins at the third step.
    2. Add the cheaper predecessor. For each index, add Math.min(cost[i - 1], cost[i - 2]) to cost[i]. Afterward the entry means "cheapest total to stand on this step", not the step's own price.
    3. Take the smaller of the last two totals. Return Math.min(cost[cost.length - 1], cost[cost.length - 2]).

    The solution in TypeScript

    class Solution {

    minCostClimbingStairs(cost: number[]): number {
        for (let i = 2; i < cost.length; ++i) {
            cost[i] += Math.min(cost[i - 1], cost[i - 2]);
        }
        return Math.min(cost[cost.length - 1], cost[cost.length - 2]);
    }
}

    Some TypeScript details:

    • The input array is changed. Arrays are passed by reference, so the caller's array holds totals afterward. Running the method on [10, 15, 20] leaves that array as [10, 15, 30]. If you need the original prices, copy first with [...cost].
    • += with Math.min. cost[i] += x means cost[i] = cost[i] + x. Math.min accepts any number of arguments and returns a number.
    • Index reads outside the array. Reading cost[-1] or cost[cost.length] doesn't throw; it gives undefined, and Math.min of that is NaN. The code avoids this by starting at index 2 and relying on the length of at least 2 that the notes promise.
    • Numbers are doubles. The largest total here is about 1000 * 999, far below any limit, so there is no overflow.

    Complexity

    Time: O(n). One pass, constant work per step.

    Space: O(1) extra. The totals reuse the input array, so nothing new is allocated. If the input must stay unchanged, a copy brings this back to O(n).

    Edge cases and common mistakes

    • Two steps. The loop doesn't run and the answer is the smaller price. [5, 3] returns 3 and [0, 0] returns 0.
    • Returning only the last total. The top can be reached from the second-to-last step, so [10, 15, 20] would give 30 instead of 15.
    • Starting the loop at 0 or 1. Then cost[i - 2] is outside the array. The result turns into NaN rather than a crash.
    • Forgetting the step's own price. Replacing += with = would throw away the price you pay on each step.

    Testing

    • [10, 15, 20] gives 15.
    • [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] gives 6.
    • [5, 3] gives 3.
    • [0, 0, 0, 1] gives 0.
    Keep going with TypeScriptAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free