1473. Paint House III

HardArrayDynamic Programming
Leetcode Link

Problem Description

In this problem, we are given m houses lined up in a row, and each house needs to be painted with one of the n available colors. The uniqueness of this problem lies in the fact that some houses have already been painted in the last summer and should not be repainted.

The term "neighborhood" is used to represent a consecutive sequence of houses painted the same color. The goal of the problem is to paint the remaining unpainted houses such that there are exactly target neighborhoods, while minimizing the total painting cost.

We are provided with:

  • An array houses where houses[i] represents the color of the i-th house. A value of 0 indicates that the house has not been painted yet.
  • A 2D array cost where cost[i][j] signifies the cost of painting the i-th house with color j+1.
  • An integer target representing the desired number of neighborhoods after painting.

The challenge is to calculate the minimum cost to achieve the exact target number of neighborhoods. If it's not feasible to meet the target neighborhoods with the given conditions, we should return -1.

Intuition

The intuition behind the solution is to use dynamic programming to solve this problem iteratively. The state of the dynamic programming involves considering three main factors at each step:

  1. The current house being considered (i).
  2. The color being considered for the current house (j).
  3. The number of neighborhoods formed up to the current house (k).

So, f[i][j][k] represents the minimum cost to paint houses up to the i-th house, with the i-th house painted color j, forming exactly k neighborhoods.

We navigate through each house and decide whether to:

  • Maintain the same color as the previous house (extending the current neighborhood).
  • Change the color (forming a new neighborhood).

If we decide to change the color, we increase our neighborhood count by 1. If the house at index i is already painted, we do not have the option to change its color. Therefore, we only have to carry the costs forward from the previous steps, not adding any new cost. For houses not yet painted, we'll add the corresponding painting cost from the cost matrix.

At each step, we are trying to minimize the cost. If we find that maintaining a neighborhood or changing the color leads to the same count of neighborhoods, we choose the option with the lower cost.

After iterating through all houses, we can find the minimum cost to paint all the houses while forming exactly target neighborhoods. If our minimum cost exceeds inf (which we set as a large constant in the beginning to represent infinite cost), it means we couldn't achieve the target with the given conditions, and thus we return -1.

Learn more about Dynamic Programming patterns.

Solution Approach

The solution to this problem makes use of a 3D dynamic programming (DP) approach, which is quite common for problems that require considering multiple states to make optimal decisions at each step.

Dynamic Programming Array

The main data structure used is a 3D array f, with dimensions [m][n+1][target+1]. This array is initialized with inf (infinity) to indicate that initially, there are no costs associated with painting houses.

  • f[i][j][k] represents the minimum cost to paint up to the i-th house, such that the i-th house is painted with color j, and there are exactly k neighborhoods.

Initialization

Before iterating through all the houses, we initialize the DP array for the first house:

  • If the first house is not painted (houses[0] == 0), we can choose any color, and the cost is the painting cost of that color.
  • If the first house is already painted with some color (houses[0] != 0), the cost is 0 as no painting is needed.

Iterative DP Update

We then iterate over each house starting from the second house (index 1) and consider each possible color (j) and each possible neighborhood count (k). For each state (i, j, k), we perform the following steps:

  1. If the current house i is not painted (houses[i] == 0), we consider painting it with every possible color j and calculate the cost of doing so. We check two scenarios:

    • If we paint it the same color as the previous house (maintaining the current neighborhood), we add the cost of painting cost[i][j-1] to the previously calculated minimum cost for that color and neighborhood count, keeping k the same.
    • If we paint it a different color from the previous house (forming a new neighborhood), we add the painting cost to the cost of the last house painted with any other color j0, but with one fewer neighborhood (k-1).

  2. If the current house i is already painted with color j, we only carry the costs forward from the previous house:

    • If the previous house is of the same color, we maintain the neighborhood count k and carry forward the cost.
    • If the previous house is of a different color, we increment the neighborhood count by 1 (as we're forming a new neighborhood) and carry forward the cost from the previous best k-1 neighborhoods with any other color j0.

Final Calculation

After completing the dynamic programming table, we find the minimum cost that allows us to have exactly target neighborhoods from the last row of our DP table. If this cost is greater than or equal to inf, it means it is impossible to achieve target neighborhoods with the given constraints, and in such cases, we return -1. Otherwise, we return the minimum cost found.

By encapsulating the complexity of our decision-making process in a dynamic programming paradigm, we can efficiently and effectively arrive at the minimum cost to paint the houses while fulfilling the neighborhood requirement.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's illustrate the solution approach using a smaller example:

Suppose we have 3 houses, and 2 possible colors. The target number of neighborhoods is 2. Therefore, m = 3, n = 2, and target = 2.

The houses array is [0, 2, 0], indicating the first and third houses are not painted yet, and the second house is painted with color 2.

The cost matrix is:

[
  [5, 10],
  [0, 0],   // already painted, no cost associated
  [1, 7]
]

Initialization

Using the dynamic programming array f with dimensions [3][3][3] to capture m houses, n+1 colors (including the unpainted state), and target+1 neighborhoods, we start with the first house:

  • Since the first house is not yet painted (houses[0] == 0), we initialize f[0][1][1] with the cost[0][0] which is 5 and f[0][2][1] with cost[0][1] which is 10.

Iterative DP Update

We move on to the second house. The state f[1][2][1] is 0 because the second house is already painted with color 2. However, if we had to change the color (we cannot since it's already painted), we would have also looked at f[1][1][2], but this isn't required here.

For the third house:

  1. If we choose color 1, since the previous house is color 2, we are forming a new neighborhood. Thus, we look at f[1][2][1] (since this represents coloring the second house color 2 and having 1 neighborhood) and add the cost for coloring the third house color 1. So, f[2][1][2] = f[1][2][1] + cost[2][0] = 0 + 1 = 1.
  2. If we choose color 2, we maintain the neighborhood. So, f[2][2][1] = f[1][2][1] + cost[2][1] = 0 + 7 = 7. However, since we need 2 neighborhoods in total and we already are at a state with 1 neighborhood and we're maintaining it, this state does not help us achieve our target, so it is discarded.

Final Calculation

Looking at the last row of our DP table, we need to find the cost to form exactly 2 neighborhoods. The relevant entries are f[2][1][2] and f[2][2][2].

The lowest cost to achieve this is found in f[2][1][2], which is 1.

Since this value is not inf, it's achievable and thus, the minimum cost to paint all houses while forming exactly 2 neighborhoods is 1. If the minimum in the last row corresponding to target neighborhoods were inf, we would return -1, indicating it's not possible to achieve the target number of neighborhoods given the constraints.

But since it is possible in this example, the answer is 1.

Solution Implementation

1class Solution:
2    def minCost(self, houses: List[int], cost: List[List[int]], num_houses: int, num_colors: int, target: int) -> int:
3        # Initialize a 3D array with infinity to store the minimum painting cost
4        # for painting the first i houses with j-th color and having k neighborhoods.
5        dp = [[[float('inf')] * (target + 1) for _ in range(num_colors + 1)] for _ in range(num_houses)]
6      
7        # Initialize the first row of dp where the first house is being painted
8        if houses[0] == 0:
9            for color_idx, painting_cost in enumerate(cost[0], start=1):
10                dp[0][color_idx][1] = painting_cost
11        else:
12            dp[0][houses[0]][1] = 0
13      
14        # Fill the dp array
15        for house_idx in range(1, num_houses):
16            if houses[house_idx] == 0:
17                for color in range(1, num_colors + 1):
18                    for neighborhoods in range(1, min(target + 1, house_idx + 2)):
19                        for prev_color in range(1, num_colors + 1):
20                            if color == prev_color:  # If the color is the same as the previous house
21                                dp[house_idx][color][neighborhoods] = min(
22                                    dp[house_idx][color][neighborhoods], dp[house_idx - 1][prev_color][neighborhoods] + cost[house_idx][color - 1]
23                                )
24                            else:  # Color changed, hence a new neighborhood is created
25                                dp[house_idx][color][neighborhoods] = min(
26                                    dp[house_idx][color][neighborhoods], dp[house_idx - 1][prev_color][neighborhoods - 1] + cost[house_idx][color - 1]
27                                )
28            else:
29                color = houses[house_idx]
30                for neighborhoods in range(1, min(target + 1, house_idx + 2)):
31                    for prev_color in range(1, num_colors + 1):
32                        if color == prev_color:
33                            dp[house_idx][color][neighborhoods] = min(dp[house_idx][color][neighborhoods], dp[house_idx - 1][color][neighborhoods])
34                        else:
35                            dp[house_idx][color][neighborhoods] = min(dp[house_idx][color][neighborhoods], dp[house_idx - 1][prev_color][neighborhoods - 1])
36
37        # Find the minimum cost from the last house with the target number of neighborhoods
38        min_cost = min(dp[-1][color][target] for color in range(1, num_colors + 1))
39        # Return -1 if the minimum cost is infinity (which means the target is not achievable)
40        return -1 if min_cost == float('inf') else min_cost
41
1class Solution {
2    public int minCost(int[] houses, int[][] cost, int m, int n, int target) {
3        int[][][] dp = new int[m][n + 1][target + 1]; // 3D array for dynamic programming
4        final int INF = Integer.MAX_VALUE / 2; // Define infinity as a large number to avoid overflow
5
6        // Initialize the dp array with infinity
7        for (int[][] neighbourhood : dp) {
8            for (int[] houseCost : neighbourhood) {
9                Arrays.fill(houseCost, INF);
10            }
11        }
12
13        // For the first house
14        if (houses[0] == 0) { // If the first house is not painted
15            for (int color = 1; color <= n; ++color) {
16                dp[0][color][1] = cost[0][color - 1]; // Cost of painting the first house with a certain color
17            }
18        } else { // If the first house is already painted
19            dp[0][houses[0]][1] = 0; // No cost, as the house is already painted
20        }
21
22        // For each subsequent house
23        for (int i = 1; i < m; ++i) {
24            if (houses[i] == 0) { // If the current house is not painted
25                for (int color = 1; color <= n; ++color) {
26                    for (int neighbourhoods = 1; neighbourhoods <= Math.min(target, i + 1); ++neighbourhoods) {
27                        for (int prevColor = 1; prevColor <= n; ++prevColor) {
28                            if (color == prevColor) { // Same color as previous house
29                                dp[i][color][neighbourhoods] = Math.min(dp[i][color][neighbourhoods], dp[i - 1][color][neighbourhoods] + cost[i][color - 1]);
30                            } else { // Different color, new neighborhood
31                                dp[i][color][neighbourhoods] = Math.min(dp[i][color][neighbourhoods], dp[i - 1][prevColor][neighbourhoods - 1] + cost[i][color - 1]);
32                            }
33                        }
34                    }
35                }
36            } else { // If the current house is already painted
37                int color = houses[i];
38                for (int neighbourhoods = 1; neighbourhoods <= Math.min(target, i + 1); ++neighbourhoods) {
39                    for (int prevColor = 1; prevColor <= n; ++prevColor) {
40                        if (color == prevColor) { // Same color as previous house
41                            dp[i][color][neighbourhoods] = Math.min(dp[i][color][neighbourhoods], dp[i - 1][color][neighbourhoods]);
42                        } else { // Different color, new neighborhood
43                            dp[i][color][neighbourhoods] = Math.min(dp[i][color][neighbourhoods], dp[i - 1][prevColor][neighbourhoods - 1]);
44                        }
45                    }
46                }
47            }
48        }
49
50        // Find the minimum cost from the last house
51        int answer = INF;
52        for (int color = 1; color <= n; ++color) {
53            answer = Math.min(answer, dp[m - 1][color][target]);
54        }
55
56        // If the answer is still infinity, it means it is not possible to form the target neighborhoods
57        return answer >= INF ? -1 : answer;
58    }
59}
60
1class Solution {
2public:
3    int minCost(vector<int>& houses, vector<vector<int>>& cost, int m, int n, int target) {
4        // f[i][j][k] represents the minimum cost to paint first i houses with k neighborhoods
5        // and the i-th house painted with color j
6        int f[m][n + 1][target + 1];
7      
8        // Initialize the dp array with a high value to represent the minimum function later
9        memset(f, 0x3f, sizeof(f));
10
11        // Base case for the first house
12        if (houses[0] == 0) { // If the first house is not yet painted
13            for (int color = 1; color <= n; ++color) {
14                // The cost will be the cost of painting with the respective color
15                f[0][color][1] = cost[0][color - 1];
16            }
17        } else { // If the first house is already painted
18            // The cost of painting the house with its own color is zero
19            f[0][houses[0]][1] = 0;
20        }
21
22        // Fill the dp array for the rest of the houses
23        for (int i = 1; i < m; ++i) {
24            if (houses[i] == 0) { // If the i-th house is not yet painted
25                for (int color = 1; color <= n; ++color) {
26                    for (int neighborhoods = 1; neighborhoods <= min(target, i + 1); ++neighborhoods) {
27                        for (int prev_color = 1; prev_color <= n; ++prev_color) {
28                            // If the color remains the same, we stay in the current neighborhood count
29                            if (color == prev_color) {
30                                f[i][color][neighborhoods] = min(f[i][color][neighborhoods], f[i - 1][color][neighborhoods] + cost[i][color - 1]);
31                            } else { // If the color changes, it forms a new neighborhood
32                                f[i][color][neighborhoods] = min(f[i][color][neighborhoods], f[i - 1][prev_color][neighborhoods - 1] + cost[i][color - 1]);
33                            }
34                        }
35                    }
36                }
37            } else { // If the i-th house is already painted
38                int color = houses[i];
39                for (int neighborhoods = 1; neighborhoods <= min(target, i + 1); ++neighborhoods) {
40                    for (int prev_color = 1; prev_color <= n; ++prev_color) {
41                        // Similar conditions as above, but cost[][] is not added since the house is already painted
42                        if (color == prev_color) {
43                            f[i][color][neighborhoods] = min(f[i][color][neighborhoods], f[i - 1][color][neighborhoods]);
44                        } else {
45                            f[i][color][neighborhoods] = min(f[i][color][neighborhoods], f[i - 1][prev_color][neighborhoods - 1]);
46                        }
47                    }
48                }
49            }
50        }
51
52        // Search for the minimum cost to paint all houses with exactly target neighborhoods
53        int answer = 0x3f3f3f3f; // Initialize with a high value
54        for (int color = 1; color <= n; ++color) {
55            answer = min(answer, f[m - 1][color][target]);
56        }
57
58        // If answer has not changed, it means it's not possible to paint the houses to meet the condition, return -1
59        return answer == 0x3f3f3f3f ? -1 : answer;
60    }
61};
62
1// TypeScript function to find the minimum cost of painting houses
2// with certain constraints on neighborhood formation.
3function minCost(houses: number[], cost: number[][], m: number, n: number, target: number): number {
4    // Define a number much larger than any possible cost to represent infinity.
5    const INFINITY = 1 << 30;
6
7    // Initialize the dynamic programming table where
8    // dp[i][j][k] will represent the minimum cost to paint the first i houses,
9    // with the i-th house being color j and having k neighborhoods.
10    const dp: number[][][] = new Array(m)
11        .fill(0)
12        .map(() => new Array(n + 1).fill(0).map(() => new Array(target + 1).fill(INFINITY)));
13
14    // Base case initialization: if the first house is not painted already,
15    // fill the cost to paint it with each color, otherwise set it to 0.
16    if (houses[0] === 0) {
17        for (let color = 1; color <= n; ++color) {
18            dp[0][color][1] = cost[0][color - 1];
19        }
20    } else {
21        dp[0][houses[0]][1] = 0;
22    }
23
24    // Iterate over each house.
25    for (let i = 1; i < m; ++i) {
26        if (houses[i] === 0) {
27            // If the current house is not painted already,
28            // try each color combination for this house and its neighboring houses.
29            for (let color = 1; color <= n; ++color) {
30                for (let neighborhoods = 1; neighborhoods <= Math.min(target, i + 1); ++neighborhoods) {
31                    for (let prevColor = 1; prevColor <= n; ++prevColor) {
32                        if (prevColor === color) {
33                            dp[i][color][neighborhoods] = Math.min(dp[i][color][neighborhoods], dp[i - 1][color][neighborhoods] + cost[i][color - 1]);
34                        } else {
35                            dp[i][color][neighborhoods] = Math.min(dp[i][color][neighborhoods], dp[i - 1][prevColor][neighborhoods - 1] + cost[i][color - 1]);
36                        }
37                    }
38                }
39            }
40        } else {
41            // If the current house is already painted,
42            // simply calculate the cost for the given color.
43            const color = houses[i];
44            for (let neighborhoods = 1; neighborhoods <= Math.min(target, i + 1); ++neighborhoods) {
45                for (let prevColor = 1; prevColor <= n; ++prevColor) {
46                    if (prevColor === color) {
47                        dp[i][color][neighborhoods] = Math.min(dp[i][color][neighborhoods], dp[i - 1][color][neighborhoods]);
48                    } else {
49                        dp[i][color][neighborhoods] = Math.min(dp[i][color][neighborhoods], dp[i - 1][prevColor][neighborhoods - 1]);
50                    }
51                }
52            }
53        }
54    }
55  
56    // Find the minimum cost to paint all houses with exactly target neighborhoods.
57    let minCost = INFINITY;
58    for (let color = 1; color <= n; ++color) {
59        minCost = Math.min(minCost, dp[m - 1][color][target]);
60    }
61
62    // If the minimum cost is still infinity, it's impossible to paint houses as required,
63    // so return -1, otherwise return the minimum cost.
64    return minCost >= INFINITY ? -1 : minCost;
65}
66

Time and Space Complexity

Time Complexity

The given Python code implements a dynamic programming solution. Let's analyze its time complexity:

  • The initialization of the f array is O(m * n * target), as it sets up a 3-dimensional array of size m x n x (target + 1).

  • The main loop iterates over the houses, with m iterations.

  • Inside the main loop, when houses[i] == 0, it iterates over n possible colors and min(target + 1, i + 2) possible neighborhood counts (due to the definition of the problem). For each of these combinations, it iterates again over n possible previous colors. Therefore, the complexity for this segment is O(m * n * target * n).

  • In the case when houses[i] != 0, there is no inner loop over n colors, but it still iterates over min(target + 1, i + 2) neighborhood counts and over n possible previous colors. The complexity for this part is O(m * n * target).

  • Finally, computing the answer involves a loop over n colors and taking the minimum, resulting in O(n) complexity.

As O(m * n * target * n) dominates the other parts, the overall time complexity is O(m * n^2 * target).

Space Complexity

The space complexity primarily comes from the f 3D array which is used to store the dynamic programming states:

  • As f has dimensions m x (n + 1) x (target + 1), the space complexity is O(m * n * target).

Therefore, the final space complexity is O(m * n * target).

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

What's the output of running the following function using the following tree as input? 

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12
1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18
1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

Recommended Readings

Dynamic Programming Introduction and Patterns

What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution

LeetCode Patterns: The Smart, Data-Driven Way to Prepare for Tech Interviews

LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Want a Structured Path to Master System Design Too? Don’t Miss This!