algoadvance

Leetcode 746. Min Cost Climbing Stairs

Problem Statement

You are given an integer array cost where cost[i] is the cost of ith step on a staircase. Once you pay the cost, you can either climb one or two steps. You can either start from the step with index 0 or the step with index 1.

Return the minimum cost to reach the top of the floor.

Example:

Input: cost = [10, 15, 20]
Output: 15
Explanation: You will start at index 1. Pay 15 and climb two steps to reach the top.

Input: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
Output: 6
Explanation: You will start at index 0.
             Pay 1 and climb two steps to reach index 2.
             Pay 1 and climb two steps to reach index 4.
             Pay 1 and climb two steps to reach index 6.
             Pay 1 and climb one step to reach index 7.
             Pay 1 and climb two steps to reach index 9.
             Pay 1 and climb one step to reach the top.

Constraints:

• 2 <= cost.length <= 1000
• 0 <= cost[i] <= 999

Clarifying Questions

1. Can I modify the input array?
   • Yes, modifying the input array is acceptable if necessary.
2. Where can I start from, exactly?
   • You can start from either index 0 or index 1.

Strategy

To solve this problem, we will use dynamic programming. The idea is to determine the minimum cost of reaching each step and use this to build up to the solution for reaching the top of the stairs.

1. Define the State:
   • Let dp[i] be the minimum cost to reach the ith step.
2. Initialization:
   • dp[0] = cost[0]
   • dp[1] = cost[1]
3. State Transition:
   • For each step from 2 to n, you can reach the ith step either from (i-1)th step or from (i-2)th step.
   • Thus, dp[i] = cost[i] + min(dp[i-1], dp[i-2]).
4. Result:
   • The result will be the minimum of the costs to step off the end of the staircase to the step past the last one: min(dp[n-1], dp[n-2]).

Code

#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int n = cost.size();
        vector<int> dp(n);
        
        dp[0] = cost[0];
        dp[1] = cost[1];
        
        for (int i = 2; i < n; ++i) {
            dp[i] = cost[i] + min(dp[i-1], dp[i-2]);
        }
        
        return min(dp[n-1], dp[n-2]);
    }
};

Time Complexity

• Time Complexity: O(n), where n is the length of the cost array. This is because we are iterating through the array once.

• Space Complexity: O(n), where n is the length of the cost array. This is due to the additional dp array used to store the minimum costs for each step.

We could further optimize the space complexity to O(1) by using only two variables to store the state of the last two steps instead of maintaining the entire dp array. Here is how the optimized solution would look:

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int n = cost.size();
        int first = cost[0];
        int second = cost[1];
        
        for (int i = 2; i < n; ++i) {
            int current = cost[i] + min(first, second);
            first = second;
            second = current;
        }
        
        return min(first, second);
    }
};

This optimized approach still has the same time complexity O(n) but improves space complexity to O(1).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?