Jobs

Interviews

Discussions

Min Cost Climbing Stairs

Easy

Min Cost Climbing Stairs

Easy

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the values in the `cost` array be negative, zero, or only positive integers?
What is the minimum possible length of the `cost` array? Is it possible for the array to be empty or contain only one element?
If there are multiple paths with the same minimum cost, is any one of them acceptable?
Is the starting point (index 0 or 1) considered part of the total cost, or do we only start accumulating the cost from the chosen index?
Should I return the minimum cost as an integer, or is there any specific format I should adhere to for the output?

Brute Force Solution

Approach

The problem asks for the minimum cost to reach the top of the stairs, where you can climb one or two steps at a time. The brute force approach involves exploring every possible path you can take to reach the top. We check the cost of each path and choose the one with the lowest total cost.

Here's how the algorithm would work step-by-step:

Start at the bottom, considering both starting steps as potential beginning points.
From each starting point, explore taking one step and then explore taking two steps.
Continue this process, at each step branching out to explore taking one step and taking two steps from the current position.
Keep track of the total cost of each possible path you take to the top of the stairs.
Once you have explored all possible paths to the top, compare the total costs of each path.
Select the path with the lowest cost; this is the minimum cost to reach the top.

Code Implementation

def min_cost_climbing_stairs_brute_force(cost):
    def calculate_min_cost(current_index):
        # If we reach the top (or beyond), return 0 as no further cost is incurred.
        if current_index >= len(cost):
            return 0

        # Explore taking one step.
        one_step_cost = cost[current_index] + calculate_min_cost(current_index + 1)

        # Explore taking two steps.
        two_step_cost = cost[current_index] + calculate_min_cost(current_index + 2)

        # Choose the path with the minimum cost.
        return min(one_step_cost, two_step_cost)

    # Consider starting from the first and second step.
    start_from_first_step = calculate_min_cost(0)
    start_from_second_step = calculate_min_cost(1)

    # Return the overall minimum cost.
    return min(start_from_first_step, start_from_second_step)

Big(O) Analysis

Time Complexity

O(2^n) – The provided brute force solution explores all possible paths by taking one or two steps at a time from each step. This creates a branching structure where each step potentially doubles the number of paths. In the worst case, this leads to exploring all combinations of one and two-step moves to reach the top. Therefore, the number of paths to explore grows exponentially with the number of steps 'n', resulting in a time complexity of O(2^n).

Space Complexity

O(2^N) – The provided brute force approach explores every possible path to the top of the stairs using recursion. In the worst-case scenario, each step branches into two possibilities (taking one step or two steps), leading to a binary tree-like exploration. The maximum depth of this recursion can be N, where N is the number of stairs. Consequently, the recursion stack can grow up to a depth of N and at each level of recursion, a new stack frame is created, thus leading to 2^N possible paths stored on the stack in the worst case. Therefore, the space complexity is O(2^N).

Optimal Solution

Approach

The most efficient way to find the minimum cost to reach the top is to work backward from the top. We figure out the cheapest way to reach each step, one by one, until we know the cheapest way to reach the starting steps.

Here's how the algorithm would work step-by-step:

Imagine you're already at the top. To get there, you must have taken the last or second-to-last step.
Figure out the cost to reach the last step directly from the starting point (or the step before it).
Now, for each step moving backwards, ask: Is it cheaper to reach this step from the step after, or from two steps after?
Choose the cheaper of those two paths and add that cost to the cost of the current step.
Keep doing this for every step, going backwards until you get to the first or second step.
The minimum cost to reach the top is the smaller of the costs to reach the first and second steps (because you can start from either).
By working backward and remembering the best choice at each step, you find the overall best path without having to explore every single possibility.

Code Implementation

def min_cost_climbing_stairs(cost):
    number_of_steps = len(cost)
    minimum_cost = [0] * number_of_steps

    #The cost to reach the first two steps is defined.
    minimum_cost[0] = cost[0]
    minimum_cost[1] = cost[1]

    for i in range(2, number_of_steps):
        #Calculate the minimum cost to reach each step.
        minimum_cost[i] = cost[i] + min(minimum_cost[i - 1], minimum_cost[i - 2])

    #The top can be reached from the last or second to last step.
    return min(minimum_cost[number_of_steps - 1], minimum_cost[number_of_steps - 2])

Big(O) Analysis

Time Complexity

O(n) – The provided solution iterates backward through the input array 'cost' of size 'n' once. For each element, a constant number of operations (comparison and addition) are performed. Since the number of operations grows linearly with the input size 'n', the time complexity is O(n).

Space Complexity

O(1) – The plain English explanation describes a backward iteration where, at each step, we only need to remember the minimum cost to reach the next one or two steps. This can be implemented using a constant number of variables to store these minimum costs. Therefore, the algorithm's auxiliary space doesn't scale with the input size N (the number of steps in the staircase). The space used remains constant irrespective of N, resulting in O(1) space complexity.

Edge Cases

Case	How to Handle
Null or empty cost array	Return 0 since there are no costs to consider and we are effectively at the top.
Cost array with one element	Return that single element's cost, as we can directly reach the top from either index 0 or 1.
Cost array with two elements	Return the minimum of the two elements, as we choose the cheaper starting point.
Large cost values potentially leading to integer overflow	Use a data type with a larger range (e.g., long) to store the minimum costs to avoid overflow.
Cost array with all zero values	The algorithm should still correctly compute the minimum cost as 0, choosing the path with no cost.
Cost array with all very large values	The algorithm should still correctly compute the minimum cost, although it may be large, within the allowed data type range.
Very large input array size	The dynamic programming approach has O(n) space and time complexity, which scales linearly with the input size and should handle large arrays efficiently.
Negative cost values (if problem states costs are non-negative)	If negative costs are invalid, throw an exception or return an error code; otherwise, the algorithm should handle them correctly as it searches for the minimum cost path.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the values in the `cost` array be negative, zero, or only positive integers?
What is the minimum possible length of the `cost` array? Is it possible for the array to be empty or contain only one element?
If there are multiple paths with the same minimum cost, is any one of them acceptable?
Is the starting point (index 0 or 1) considered part of the total cost, or do we only start accumulating the cost from the chosen index?
Should I return the minimum cost as an integer, or is there any specific format I should adhere to for the output?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start at the bottom, considering both starting steps as potential beginning points.
From each starting point, explore taking one step and then explore taking two steps.
Continue this process, at each step branching out to explore taking one step and taking two steps from the current position.
Keep track of the total cost of each possible path you take to the top of the stairs.
Once you have explored all possible paths to the top, compare the total costs of each path.
Select the path with the lowest cost; this is the minimum cost to reach the top.

Code Implementation

def min_cost_climbing_stairs_brute_force(cost):
    def calculate_min_cost(current_index):
        # If we reach the top (or beyond), return 0 as no further cost is incurred.
        if current_index >= len(cost):
            return 0

        # Explore taking one step.
        one_step_cost = cost[current_index] + calculate_min_cost(current_index + 1)

        # Explore taking two steps.
        two_step_cost = cost[current_index] + calculate_min_cost(current_index + 2)

        # Choose the path with the minimum cost.
        return min(one_step_cost, two_step_cost)

    # Consider starting from the first and second step.
    start_from_first_step = calculate_min_cost(0)
    start_from_second_step = calculate_min_cost(1)

    # Return the overall minimum cost.
    return min(start_from_first_step, start_from_second_step)

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Imagine you're already at the top. To get there, you must have taken the last or second-to-last step.
Figure out the cost to reach the last step directly from the starting point (or the step before it).
Now, for each step moving backwards, ask: Is it cheaper to reach this step from the step after, or from two steps after?
Choose the cheaper of those two paths and add that cost to the cost of the current step.
Keep doing this for every step, going backwards until you get to the first or second step.
The minimum cost to reach the top is the smaller of the costs to reach the first and second steps (because you can start from either).
By working backward and remembering the best choice at each step, you find the overall best path without having to explore every single possibility.

Code Implementation

def min_cost_climbing_stairs(cost):
    number_of_steps = len(cost)
    minimum_cost = [0] * number_of_steps

    #The cost to reach the first two steps is defined.
    minimum_cost[0] = cost[0]
    minimum_cost[1] = cost[1]

    for i in range(2, number_of_steps):
        #Calculate the minimum cost to reach each step.
        minimum_cost[i] = cost[i] + min(minimum_cost[i - 1], minimum_cost[i - 2])

    #The top can be reached from the last or second to last step.
    return min(minimum_cost[number_of_steps - 1], minimum_cost[number_of_steps - 2])

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty cost array	Return 0 since there are no costs to consider and we are effectively at the top.
Cost array with one element	Return that single element's cost, as we can directly reach the top from either index 0 or 1.
Cost array with two elements	Return the minimum of the two elements, as we choose the cheaper starting point.
Large cost values potentially leading to integer overflow	Use a data type with a larger range (e.g., long) to store the minimum costs to avoid overflow.
Cost array with all zero values	The algorithm should still correctly compute the minimum cost as 0, choosing the path with no cost.
Cost array with all very large values	The algorithm should still correctly compute the minimum cost, although it may be large, within the allowed data type range.
Very large input array size	The dynamic programming approach has O(n) space and time complexity, which scales linearly with the input size and should handle large arrays efficiently.
Negative cost values (if problem states costs are non-negative)	If negative costs are invalid, throw an exception or return an error code; otherwise, the algorithm should handle them correctly as it searches for the minimum cost path.