algoadvance

You are given an integer array cost where cost[i] is the cost of i-th step on a staircase. Once you pay the cost, you can either climb one or two steps. You need to find the minimum cost to reach the top of the floor. You can either start from the step with index 0, or the step with index 1.

Example:

Input: cost = [10, 15, 20]
Output: 15
Explanation: Start at index 1 and pay 15. Then climb two steps to reach the top.

Input: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
Output: 6
Explanation: Start at index 0. Pay 1 and climb two steps to reach index 2, then pay 1 and climb two steps to reach index 4, and so on. Reach the last index with cost 1.

Clarifying Questions

1. Can the cost array be empty?
   • No, the cost array always contains at least one element.
2. What is the maximum size of the cost array?
   • Generally, constraints go up to thousands or tens of thousands in size.
3. Can the cost array contain zero values?
   • Yes, it can, which means you can step on that step for free.

Strategy

To solve this problem, a dynamic programming approach works effectively. The idea is to use a dp array where dp[i] represents the minimum cost to reach step i.

• You can either come to step i from step i-1 or step i-2.
• Hence, the state transition relation:
  • dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])
• The base case is to start either from step 0 or step 1, in which case you pay the cost of that step.

Code

def minCostClimbingStairs(cost):
    n = len(cost)
    
    # Base cases. These correspond to the starting points
    first = cost[0]
    second = cost[1]
    
    # If there are only two steps
    if n == 2:
        return min(first, second)
    
    # Iterate over the cost array to fill dp values
    for i in range(2, n):
        current = cost[i] + min(first, second)
        first = second
        second = current
    
    # The minimum cost to reach the top can either be from the last step or the one before
    return min(first, second)

# Example usage:
cost = [10, 15, 20]
print(minCostClimbingStairs(cost))  # Output: 15

cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
print(minCostClimbingStairs(cost))  # Output: 6

Time Complexity

The time complexity is (O(n)) because we iterate through the cost array once.

Space Complexity

The space complexity is (O(1)) because we only use a fixed amount of extra space (variables to store the last two costs). By not maintaining a full dp array, we make the solution more space-efficient.

Try our interview co-pilot at AlgoAdvance.com

• 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?