Paint House II

Hard

Asked by:

3 views

Topics:

Dynamic Programming

There are a row of n houses, each house can be painted with one of the k colors. 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 k cost matrix costs.

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

Return the minimum cost to paint all houses.

Example 1:

Input: costs = [[1,5,3],[2,9,4]]
Output: 5
Explanation:
You have to paint house 0. Firstly, paint it with color 0, cost 1. Then paint house 1 with color 2, cost 4.
Total cost: 1 + 4 = 5;
Or you can paint house 0 with color 2, cost 3. Then paint house 1 with color 0, cost 2.
Total cost: 3 + 2 = 5.

Example 2:

Input: costs = [[1,3],[2,4]]
Output: 5

Constraints:

costs.length == n
costs[i].length == k
1 <= n <= 100
1 <= k <= 20
0 <= costs[i][j] <= 1000

Paint House II

Hard

Asked by:

3 views

Topics:

Dynamic Programming

There are a row of n houses, each house can be painted with one of the k colors. 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 k cost matrix costs.

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

Return the minimum cost to paint all houses.

Example 1:

Input: costs = [[1,5,3],[2,9,4]]
Output: 5
Explanation:
You have to paint house 0. Firstly, paint it with color 0, cost 1. Then paint house 1 with color 2, cost 4.
Total cost: 1 + 4 = 5;
Or you can paint house 0 with color 2, cost 3. Then paint house 1 with color 0, cost 2.
Total cost: 3 + 2 = 5.

Example 2:

Input: costs = [[1,3],[2,4]]
Output: 5

Constraints:

costs.length == n
costs[i].length == k
1 <= n <= 100
1 <= k <= 20
0 <= costs[i][j] <= 1000

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 is the range for the cost of painting a house with a particular color?
Can the input array 'costs' be empty, or can either 'n' (number of houses) or 'k' (number of colors) be zero?
Are there any constraints on the number of houses (n) and the number of colors (k)?
Are the costs guaranteed to be non-negative integers?
If there are no houses, or no colors, what should I return?

Brute Force Solution

Approach

Imagine painting a row of houses with different colored paints, where each house has a cost for each color. The brute force way is to try every possible color combination for the houses. We want to find the cheapest combination.

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

For the first house, consider painting it each color, one color at a time.
For each color choice for the first house, consider all color choices for the second house.
Continue this process, considering all possible color choices for each house, making sure that neighboring houses never have the same color.
Calculate the total cost for each complete painting scheme (a color for every house).
Compare the total costs of all the valid painting schemes.
Choose the painting scheme with the lowest total cost. This is the cheapest way to paint the houses.

Code Implementation

def paint_house_two_brute_force(costs):
    number_of_houses = len(costs)
    if number_of_houses == 0:
        return 0
    number_of_colors = len(costs[0])
    minimum_cost = float('inf')

    def calculate_cost(house_index, current_painting_scheme, total_cost):
        nonlocal minimum_cost

        # Base case: all houses are painted
        if house_index == number_of_houses:
            minimum_cost = min(minimum_cost, total_cost)
            return

        # Try each color for the current house
        for color_index in range(number_of_colors):
            # Ensure different colors for adjacent houses
            if house_index > 0 and current_painting_scheme[house_index - 1] == color_index:
                continue

            # Recursively calculate cost with the current color
            current_painting_scheme[house_index] = color_index
            calculate_cost(house_index + 1, current_painting_scheme, total_cost + costs[house_index][color_index])

    # Initialize the painting scheme
    painting_scheme = [0] * number_of_houses
    
    # Start the recursive process
    calculate_cost(0, painting_scheme, 0)
    
    return minimum_cost

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(k^n) – The provided brute-force approach explores every possible coloring combination for n houses, where each house can be painted with one of k colors. In the worst-case scenario, it examines all k options for the first house, then k options for the second, and so on, ensuring no adjacent houses have the same color. This results in a branching factor of up to k for each house. Therefore, the time complexity is proportional to k multiplied by itself n times, which is O(k^n).

Space Complexity

O(K^N) – The plain English explanation outlines a brute force approach that explores every possible color combination for N houses, where each house can be painted in one of K colors. This exhaustive search implicitly generates a call tree where each level corresponds to a house and each branch corresponds to a color choice. The algorithm effectively stores a call stack representing the path from the root to the current node in this tree. In the worst-case scenario, the space complexity grows exponentially with the number of houses, leading to a maximum space usage proportional to K^N, as each level could potentially store up to K branches at each of the N house decision points.

Optimal Solution

Approach

This problem is about finding the cheapest way to paint houses with different colors, making sure no two adjacent houses have the same color. The key idea is to build up the solution step-by-step, only remembering the best and second-best costs from the previous step, allowing us to make efficient decisions for each house.

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

For the first house, simply remember the cost of painting it each color.
For each subsequent house, consider each color option.
To calculate the cost of painting the current house a specific color, look at the costs from the previous house.
Find the cheapest color from the previous house that is DIFFERENT from the current color you are considering.
Add that cheapest previous color cost to the cost of painting the current house with its specific color. This gives you the total cost if you choose that color for the current house.
After checking all colors for the current house, update your records to remember just the two cheapest total costs for THIS house and the colors associated with them (best and second best).
Continue this process for all the houses.
After the last house, the smallest cost you have recorded will be the overall cheapest way to paint all the houses, without adjacent houses sharing a color.

Code Implementation

def paint_house_ii(costs):
    number_of_houses = len(costs)
    if number_of_houses == 0:
        return 0
    number_of_colors = len(costs[0])

    # Initialize best and second best costs
    minimum_cost = 0
    second_minimum_cost = 0
    minimum_cost_index = -1

    # Iterate through each house
    for house_index in range(number_of_houses):
        previous_minimum_cost = minimum_cost
        previous_second_minimum_cost = second_minimum_cost
        previous_minimum_cost_index = minimum_cost_index

        minimum_cost = float('inf')
        second_minimum_cost = float('inf')
        minimum_cost_index = -1

        # Iterate through each color
        for color_index in range(number_of_colors):
            # If current color is same as prev min,
            # use prev second min.
            if color_index == previous_minimum_cost_index:
                current_cost = costs[house_index][color_index] + previous_second_minimum_cost

            # Otherwise, use previous min.
            else:
                current_cost = costs[house_index][color_index] + previous_minimum_cost

            # Update min costs for the current house
            if current_cost < minimum_cost:
                second_minimum_cost = minimum_cost
                minimum_cost = current_cost
                minimum_cost_index = color_index
            elif current_cost < second_minimum_cost:
                second_minimum_cost = current_cost

    # The min cost after painting all houses.
    return minimum_cost

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n*k) – The algorithm iterates through each of the n houses. For each house, it iterates through all k possible colors. Inside the inner loop (color iteration), it finds the minimum cost from the previous house amongst k colors, which contributes to the cost of the current house. Therefore, the time complexity is determined by the nested loops, resulting in O(n*k) where n is the number of houses and k is the number of colors.

Space Complexity

O(K) – The algorithm stores the costs for the current house in an array of size K, where K is the number of colors. It also maintains the best and second-best costs from the *previous* house, which can be stored in variables, but the core space usage stems from the K-sized array needed to hold intermediate costs for each color for the current house being processed. Thus, the auxiliary space is directly proportional to the number of colors K, resulting in O(K) space complexity.

Edge Cases

Case	How to Handle
Null or empty costs array	Return 0 immediately as there are no houses to paint.
Zero houses (n=0)	Return 0 as there are no costs.
One house (n=1) and one color (k=1)	Return the cost of that single color for that single house.
One house (n=1) and multiple colors (k>1)	Return the minimum cost among all colors for the single house.
Multiple houses (n>1) and one color (k=1)	Return -1, because adjacent houses can't be the same color; an alternative is to throw an IllegalArgumentException.
Large input sizes (n and k very large) exceeding memory or time limits	Ensure the algorithm has optimal time complexity (O(n*k)) to prevent timeouts and uses memory efficiently to avoid exceeding available memory.
All costs are zero for some house	The algorithm should still correctly propagate the minimum cost, treating zero as the minimum.
Integer overflow when summing costs with large values	Use a larger data type (e.g., long) to store the intermediate and final cost values.