Paint House 1 - N houses with 3 colors with no two adjacent houses with same color

Problem

There are a row of n houses, each house can be painted with one of the 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, and you need to cost the least. Return the minimum cost.

The cost of painting each house with a certain color is represented by a n x 3 cost matrix. For example, costs[0][0] is the cost of painting house 0 with color red; costs[1][2] is the cost of painting house 1 with color green, and so on… Find the minimum cost to paint all houses.

Examples

Example 1:

Input:[[14,2,11],[11,14,5],[14,3,10]]
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:[[1,2,3],[1,4,6]]
Output: 3

Solution

Method 1 - Recursion

Let’s define the color indices: 0 for red, 1 for blue, and 2 for green.

paintHouse(int i, int j)

Which returns the minimum cost to paint the first ‘i’ houses (0-th based indexing) such that the last house (i-th house) is painted with j-th colour.

The recurse relation is:

 Cost(i, RED) = costs[i][RED] + min(Cost(i+1, BLUE), Cost(i+1, GREEN))
 Cost(i, BLUE) = costs[i][BLUE] + min(Cost(i+1, RED), Cost(i+1, GREEN))
 Cost(i, GREEN) = costs[i][GREEN] + min(Cost(i+1, RED), Cost(i+1, BLUE))

Code

Java

public class Solution {

	// Color indices
	private static final int RED = 0;
	private static final int BLUE = 1;

	private static final int GREEN = 2;

	public int minCost(int[][] costs) {
		if (costs == null || costs.length == 0) {
			return 0;
		}

		// Call the recursive function for each color starting on the first house
		int costRed = paintHouse(0, RED, costs);
		int costBlue = paintHouse(0, BLUE, costs);
		int costGreen = paintHouse(0, GREEN, costs);

		// Find the minimum of the three starting colors
		return Math.min(costRed, Math.min(costBlue, costGreen));
	}

	private int paintHouse(int houseIndex, int color, int[][] costs) {
		// Base case: If there are no more houses left to paint
		if (houseIndex == costs.length) {
			return 0;
		}

		// Total cost of painting the current house with 'color'
		int totalCost = costs[houseIndex][color];

		// Calculate the cost of painting the next house, ensuring we do not paint
		// the same color as the current house.
		if (color == RED) {
			totalCost += Math.min(
				paintHouse(houseIndex + 1, BLUE, costs),
				paintHouse(houseIndex + 1, GREEN, costs));
		} else if (color == BLUE) {
			totalCost += Math.min(
				paintHouse(houseIndex + 1, RED, costs),
				paintHouse(houseIndex + 1, GREEN, costs));
		} else { // color == GREEN
			totalCost += Math.min(
				paintHouse(houseIndex + 1, RED, costs),
				paintHouse(houseIndex + 1, BLUE, costs));
		}

		return totalCost;
	}
}

Complexity

⏰ Time complexity: O(2^n). We know that for house 0, we have 3 choices of color. After that house [1..n] have 2 choices of color. So time complexity is O(2^n).
🧺 Space complexity: O(n)

Method 2 - Top Down DP

Let us observe the recursion tree for the first test case of sample test 2.

paint-house-1-recursion-tree.excalidraw

The root nodes are the possible colors for the first house, Cost(0, R), Cost(0, B), and Cost(0, G).
The next level nodes represent the costs of the second house given the color of the first house. For example, if the first house is painted red (Cost(0, R)), the second house can be painted either blue or green (Cost(1, B) or Cost(1, G)).
The tree continues in this manner, and each possible color decision for the current house leads to two more recursive calls for the next house, with the color options that don’t match the color selected for the current house.

The overlapping subproblems become evident when you notice that for calculating Cost(1, B), you need Cost(2, R) and Cost(2, G), and for Cost(1, G), you also need Cost(2, R) and Cost(2, G). Thus, subproblems like Cost(2, R) and Cost(2, G) are computed multiple times.

To avoid this redundancy, a typical DP solution would store the results of Cost(2, R) and Cost(2, G) after the first computation and then reuse these stored results, which is known as memoization. This technique significantly reduces the amount of computation needed to solve the problem, transforming it from exponential to linear time complexity.

Code

Java

class Solution {

	private static final int RED = 0;

	private static final int BLUE = 1;

	private static final int GREEN = 2;

	private Integer[][] memo; // The memoization table
	public int minCost(int[][] costs) {
		if (costs == null || costs.length == 0) {
			return 0;
		}

		int n = costs.length;
		memo = new Integer[n][3]; // Initialize the memo table

		// Start the recursion from the first house and try each color
		int costRed = paintHouse(0, RED, costs);
		int costBlue = paintHouse(0, BLUE, costs);
		int costGreen = paintHouse(0, GREEN, costs);

		// Return the minimum cost among three starting colors
		return Math.min(Math.min(costRed, costBlue), costGreen);
	}

	private int paintHouse(int houseIndex, int color, int[][] costs) {
		if (houseIndex == costs.length) {
			return 0; // Reached the end of houses
		}

		// Check if the result is already computed and stored in memo table
		if (memo[houseIndex][color] != null) {
			return memo[houseIndex][color];
		}

		int totalCost = costs[houseIndex][color]; // Current painting cost

		// Recursive calls for next house and different colors, excluding the current color
		int nextCost = Integer.MAX_VALUE;

		for (int nextColor = 0; nextColor < 3; nextColor++) {
			if (nextColor != color) {
				nextCost = Math.min(nextCost, paintHouse(houseIndex + 1, nextColor, costs));
			}
		}

		// Add current cost to next cost and store result in memo table
		totalCost += nextCost;
		memo[houseIndex][color] = totalCost;

		return memo[houseIndex][color];
	}

}

Method 3 - DP Bottom UP

Let dp[i][j] be our dynamic programming matrix of N * 3 dimensions to store the minimum cost to paint first ‘i’ houses such that the i-th house is painted with j-th colour.

Algorithm

In this bottom-up approach:

The dp array is used to store the minimum cost to paint up to the i-th house, ending with each of the three colors.
We start by initializing the dp array with the costs of painting the first house with each of the three available colors.
The algorithm then iteratively computes the minimum cost of painting each house in sequence, updating the dp table with the minimum cost that accounts for the constraint of not painting the same color as the previous house.
Finally, the lowest cost of painting the last house (with any color) will be the solution to the problem—that is, the total minimum cost to paint all houses while satisfying the no-color-repeat constraint.

Code

Java

public class HousePainting {

	public int minCost(int[][] costs) {
		if (costs == null || costs.length == 0) {
			return 0;
		}

		int n = costs.length;
		
		int[][] dp = new int[n][3];

		// Initialize the first row of DP table with the costs of the first house for each color
		for (int color = 0; color < 3; color++) {
			dp[0][color] = costs[0][color];
		}

		for (int i = 1; i < n; i++) {
			dp[i][0] = costs[i][0] + Math.min(dp[i - 1][1], dp[i - 1][2]); // If we paint current house Red
			dp[i][1] = costs[i][1] + Math.min(dp[i - 1][0], dp[i - 1][2]); // If we paint current house Blue
			dp[i][2] = costs[i][2] + Math.min(dp[i - 1][0], dp[i - 1][1]); // If we paint current house Green
		}

		return Math.min(Math.min(dp[n - 1][0], dp[n - 1][1]), dp[n - 1][2]);
	}

}

Complexity

⏰ Time complexity: O(n)
🧺 Space complexity: O(n)

Method 4 - Space efficient DP with costs array modification

Code

Java

Code if we change our array, but spoace complexity - O(1)

public int minCost(int[][] costs) {
	if (costs == null || costs.length == 0) {
		return 0;
	}
	int n = costs.length;
	for (int i = 1; i< n; i++) {
		costs[i][0] += Math.min(costs[i - 1][1], costs[i - 1][2]);
		costs[i][1] += Math.min(costs[i - 1][0], costs[i - 1][2]);
		costs[i][2] += Math.min(costs[i - 1][0], costs[i - 1][1]);
	}

	return Math.min(Math.min(costs[n - 1][0], costs[ n - 1][1]), costs[n - 1][2]);
}

Complexity

⏰ Time complexity: O(n)
🧺 Space complexity: O(1)

Problem#

Examples#

Solution#

Method 1 - Recursion#

Code#

Java#

Complexity#

Method 2 - Top Down DP#

Code#

Java#

Method 3 - DP Bottom UP#

Algorithm#

Code#

Java#

Complexity#

Method 4 - Space efficient DP with costs array modification#

Code#

Java#

Complexity#

Problem

Examples

Solution

Method 1 - Recursion

Code

Java

Complexity

Method 2 - Top Down DP

Code

Java

Method 3 - DP Bottom UP

Algorithm

Code

Java

Complexity

Method 4 - Space efficient DP with costs array modification

Code

Java

Complexity