Jobs

Interviews

Discussions

Paint House

Medium

Google

3 views

Topics:

Dynamic Programming

There is a row of n houses, where each house can be painted one of three colors: red, blue, or green. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.

The cost of painting each house with a certain color is represented by an n x 3 cost matrix costs.

For example, costs[0][0] is the cost of painting house 0 with the color red; costs[1][2] is the cost of painting house 1 with color green, and so on...

Return the minimum cost to paint all houses.

Example 1:

Input: costs = [[17,2,17],[16,16,5],[14,3,19]]
Output: 10
Explanation: Paint house 0 into blue, paint house 1 into green, paint house 2 into blue.
Minimum cost: 2 + 5 + 3 = 10.

Example 2:

Input: costs = [[7,6,2]]
Output: 2

Constraints:

costs.length == n
costs[i].length == 3
1 <= n <= 100
1 <= costs[i][j] <= 100

Paint House

Medium

Google

3 views

Topics:

Dynamic Programming

The cost of painting each house with a certain color is represented by an n x 3 cost matrix costs.

For example, costs[0][0] is the cost of painting house 0 with the color red; costs[1][2] is the cost of painting house 1 with color green, and so on...

Return the minimum cost to paint all houses.

Example 1:

Input: costs = [[17,2,17],[16,16,5],[14,3,19]]
Output: 10
Explanation: Paint house 0 into blue, paint house 1 into green, paint house 2 into blue.
Minimum cost: 2 + 5 + 3 = 10.

Example 2:

Input: costs = [[7,6,2]]
Output: 2

Constraints:

costs.length == n
costs[i].length == 3
1 <= n <= 100
1 <= costs[i][j] <= 100

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:

What are the dimensions and value ranges of the `costs` matrix? Could the matrix be empty, or could any cost values be negative?
Is it guaranteed that there will always be at least one possible coloring of all the houses given the constraints, or should I account for cases where no valid coloring exists?
If no valid coloring exists, what value should I return?
Are there any specific memory constraints I should be aware of given the possible size of the `costs` matrix?
For the available colors (red, blue, and green), are the colors fixed to only these three, or should I expect it to generalize to `k` colors?

Brute Force Solution

Approach

We need to find the cheapest way to paint a row of houses, where each house can be painted one of several colors, and each color has a different cost. The brute force approach explores every single possible color combination for all the houses. We then calculate the total cost for each combination and pick the cheapest one.

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

For the first house, try painting it each color one at a time.
For each color choice on the first house, try every color option for the second house.
Continue this pattern, trying every possible color for each house, building up every possible painting combination.
Once we have a complete color combination for all houses, calculate the total cost by adding up the cost of painting each house its chosen color.
Keep track of the lowest total cost found so far.
Repeat this process for all possible color combinations.
After trying all combinations, the lowest total cost we tracked is the answer.

Code Implementation

def paint_house_brute_force(costs):
    number_of_houses = len(costs)
    if number_of_houses == 0:
        return 0

    minimum_cost = float('inf')

    def calculate_total_cost(color_choices):
        total_cost = 0
        for house_index, color_index in enumerate(color_choices):
            total_cost += costs[house_index][color_index]
        return total_cost

    def find_minimum_cost(house_index, current_color_choices):
        nonlocal minimum_cost

        # Base case: all houses have been painted
        if house_index == number_of_houses:
            total_cost_for_choices = calculate_total_cost(current_color_choices)
            minimum_cost = min(minimum_cost, total_cost_for_choices)
            return

        # Try painting the current house each possible color
        number_of_colors = len(costs[house_index])
        for color_index in range(number_of_colors):
            # Recursively call function with added color
            find_minimum_cost(house_index + 1, current_color_choices + [color_index])

    # Start the recursion from the first house with empty color choices
    find_minimum_cost(0, [])

    return minimum_cost

Big(O) Analysis

Time Complexity

O(k^n) – The provided approach explores every possible color combination for all the houses. If there are n houses and each house can be painted in k colors, then the total number of possible combinations is k * k * ... * k (n times), which equals k^n. Since the algorithm has to explore each of these k^n combinations to find the minimum cost, the time complexity is directly proportional to the number of combinations. Therefore, the time complexity is O(k^n), where n is the number of houses and k is the number of colors.

Space Complexity

O(1) – The brute force approach, as described, essentially iterates through all possible color combinations for each house without storing intermediate combinations or results in auxiliary data structures beyond a few variables. The only space utilized beyond the input 'costs' array is for tracking the current minimum cost, and perhaps a loop counter or two. The number of houses and colors doesn't affect the space used by the auxiliary variables. Thus, the space complexity remains constant, regardless of the number of houses or color choices.

Optimal Solution

Approach

The core idea is to minimize the cost of painting each house by considering the costs of the previous houses. Instead of checking every possible color combination, we'll use past information to build up to the best solution one house at a time.

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

Start with the first house and its painting costs for each color.
For the second house, figure out the cheapest way to paint it each color by adding its cost to the minimum cost of painting the previous house a *different* color.
Keep going through each house, always calculating the minimum cost to paint it each color, based on the minimum costs of painting the previous house a *different* color.
When you get to the last house, simply choose the smallest cost among the three colors. That is the minimum total cost to paint all houses.

Code Implementation

def paint_house(costs):
    if not costs:
        return 0

    number_of_houses = len(costs)

    # Iterate through houses, updating costs based on min from prev
    for i in range(1, number_of_houses):
        # Update cost for red. We're finding the min cost so far.
        costs[i][0] += min(costs[i - 1][1], costs[i - 1][2])

        # Update cost for blue
        costs[i][1] += min(costs[i - 1][0], costs[i - 1][2])

        # Update cost for green
        costs[i][2] += min(costs[i - 1][0], costs[i - 1][1])

    # The minimum cost will be the smallest of the costs for the last house.
    return min(costs[number_of_houses - 1][0], costs[number_of_houses - 1][1], costs[number_of_houses - 1][2])

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through each of the n houses (where n is the number of houses). For each house, it calculates the minimum cost to paint it each color based on the previous house's costs. This calculation involves a constant amount of work (finding the minimum of three values for each color), so the work done for each house is O(1). Since we perform O(1) work for each of the n houses, the overall time complexity is O(n).

Space Complexity

O(1) – The provided plain English explanation describes an iterative process where we update the costs in place. We only need to keep track of the current minimum costs for each color of the current house which can be stored in a fixed number of variables (one for each color), independent of the number of houses. No auxiliary data structures that scale with the input size (N, where N is the number of houses) are used. Thus, the auxiliary space used is constant.

Edge Cases

Case	How to Handle
Null or empty costs array	Return 0 since there are no houses to paint.
Costs array with zero rows (zero houses)	Return 0 since no painting is needed.
Costs array with one row (one house)	Return the minimum cost among the three colors for that single house.
Costs array with all colors for a house having the same cost	The algorithm should still correctly find the minimum total cost, potentially requiring tie-breaking logic.
Large costs that could potentially lead to integer overflow when summing	Use a larger integer data type (e.g., long) to store intermediate and final results.
Costs array with extremely large dimensions (many houses)	The dynamic programming approach should have O(n) space complexity where n is the number of houses, so it should scale adequately.
Costs array contains negative costs	The problem statement doesn't define negative costs, so the code should either throw an error or assume the absolute values are intended.
Only 1 color available	If the costs array has only 1 column, it means only one color is available; then just sum all the color values.

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:

What are the dimensions and value ranges of the `costs` matrix? Could the matrix be empty, or could any cost values be negative?
Is it guaranteed that there will always be at least one possible coloring of all the houses given the constraints, or should I account for cases where no valid coloring exists?
If no valid coloring exists, what value should I return?
Are there any specific memory constraints I should be aware of given the possible size of the `costs` matrix?
For the available colors (red, blue, and green), are the colors fixed to only these three, or should I expect it to generalize to `k` colors?

Brute Force Solution

Approach

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

For the first house, try painting it each color one at a time.
For each color choice on the first house, try every color option for the second house.
Continue this pattern, trying every possible color for each house, building up every possible painting combination.
Once we have a complete color combination for all houses, calculate the total cost by adding up the cost of painting each house its chosen color.
Keep track of the lowest total cost found so far.
Repeat this process for all possible color combinations.
After trying all combinations, the lowest total cost we tracked is the answer.

Code Implementation

def paint_house_brute_force(costs):
    number_of_houses = len(costs)
    if number_of_houses == 0:
        return 0

    minimum_cost = float('inf')

    def calculate_total_cost(color_choices):
        total_cost = 0
        for house_index, color_index in enumerate(color_choices):
            total_cost += costs[house_index][color_index]
        return total_cost

    def find_minimum_cost(house_index, current_color_choices):
        nonlocal minimum_cost

        # Base case: all houses have been painted
        if house_index == number_of_houses:
            total_cost_for_choices = calculate_total_cost(current_color_choices)
            minimum_cost = min(minimum_cost, total_cost_for_choices)
            return

        # Try painting the current house each possible color
        number_of_colors = len(costs[house_index])
        for color_index in range(number_of_colors):
            # Recursively call function with added color
            find_minimum_cost(house_index + 1, current_color_choices + [color_index])

    # Start the recursion from the first house with empty color choices
    find_minimum_cost(0, [])

    return minimum_cost

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Start with the first house and its painting costs for each color.
For the second house, figure out the cheapest way to paint it each color by adding its cost to the minimum cost of painting the previous house a *different* color.
Keep going through each house, always calculating the minimum cost to paint it each color, based on the minimum costs of painting the previous house a *different* color.
When you get to the last house, simply choose the smallest cost among the three colors. That is the minimum total cost to paint all houses.

Code Implementation

def paint_house(costs):
    if not costs:
        return 0

    number_of_houses = len(costs)

    # Iterate through houses, updating costs based on min from prev
    for i in range(1, number_of_houses):
        # Update cost for red. We're finding the min cost so far.
        costs[i][0] += min(costs[i - 1][1], costs[i - 1][2])

        # Update cost for blue
        costs[i][1] += min(costs[i - 1][0], costs[i - 1][2])

        # Update cost for green
        costs[i][2] += min(costs[i - 1][0], costs[i - 1][1])

    # The minimum cost will be the smallest of the costs for the last house.
    return min(costs[number_of_houses - 1][0], costs[number_of_houses - 1][1], costs[number_of_houses - 1][2])

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty costs array	Return 0 since there are no houses to paint.
Costs array with zero rows (zero houses)	Return 0 since no painting is needed.
Costs array with one row (one house)	Return the minimum cost among the three colors for that single house.
Costs array with all colors for a house having the same cost	The algorithm should still correctly find the minimum total cost, potentially requiring tie-breaking logic.
Large costs that could potentially lead to integer overflow when summing	Use a larger integer data type (e.g., long) to store intermediate and final results.
Costs array with extremely large dimensions (many houses)	The dynamic programming approach should have O(n) space complexity where n is the number of houses, so it should scale adequately.
Costs array contains negative costs	The problem statement doesn't define negative costs, so the code should either throw an error or assume the absolute values are intended.
Only 1 color available	If the costs array has only 1 column, it means only one color is available; then just sum all the color values.