Paint House
You have been given ‘N’ houses, each house can be painted with any of three colours: green, red and yellow. You are also given a “cost” matrix of ‘N’ * 3 dimension which represents the cost of painting an i-th house (0-th based indexing) with j-th colour. The colour code is as follows: green - 0, red - 1 and yellow - 2. Now, you are supposed to find the minimum cost of painting all houses such that no adjacent houses are painted with the same colour.

Input Format :

The first line contains an integer ‘T’ denoting the number of test cases. Then each test case follows. The first input line of each test case contains an integer ‘N’ denoting the number of houses. Each of the next ‘N’ lines contains 3 space-separated integers denoting the cost of painting the i-th house with the green,red and yellow color respectively.

Output Format :

For each test case, print the minimum cost of painting all houses such that no adjacent houses are painted with the same colour. Print the output of each test case in a separate line.

Note :

You are not required to print the expected output; it has already been taken care of. Just implement the function.

Constraints :

1

Question

Paint House

You have been given ‘N’ houses, each house can be painted with any of three colours: green, red and yellow. You are also given a “cost” matrix of ‘N’ * 3 dimension which represents the cost of painting an i-th house (0-th based indexing) with j-th colour. The colour code is as follows: green - 0, red - 1 and yellow - 2. Now, you are supposed to find the minimum cost of painting all houses such that no adjacent houses are painted with the same colour.

Input Format :

The first line contains an integer ‘T’ denoting the number of test cases. Then each test case follows.

The first input line of each test case contains an integer ‘N’ denoting the number of houses.

Each of the next ‘N’ lines contains 3 space-separated integers denoting the cost of painting the i-th house with the green,red and yellow color respectively.

Output Format :

For each test case, print the minimum cost of painting all houses such that no adjacent houses are painted with the same colour.

Print the output of each test case in a separate line.

Note :

You are not required to print the expected output; it has already been taken care of. Just implement the function.

Constraints :

1 <= T <= 50
1 <= N <= 10000
0 <= cost[i][j] <= 100

Where cost[i][j] represents the cost of painting the i-th house with j-th colour.

Time limit: 1 sec

Accepted Answer

Recursive Approach

The basic idea of this approach is to break the original problem into sub-problems. We will try to check each valid way of painting the houses. And, then find the minimum cost.

Now, let us define a recursive function

getMinCost(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.

Algorithm

Base Case:
- If i == -1, then return 0. It denotes that we don’t have any house to paint so the cost will be 0.
Now, if we are choosing to paint the i-th house with j-th colour then we can’t paint the (i - 1)-th house with j-th colour. Create a variable “ans” which will store the answer to the current sub-problem and initialise it with a very large integer.
Start traversing through the possible colours using a variable ‘k’.
- If (j != k) then we can choose the k-th colour to paint the (i - 1)-th house. Therefore, ans = min(ans, cost[i][j] + getMinCost(i - 1, k))
Return the “ans”.

Space Complexity: O(n)Explanation:

O(N), where ‘N’ is the total number of houses.

Since we are using a recursive function to find the minimum cost and in the worst case, there may be N state in the call stack. So the overall space complexity will be O(N).

Time Complexity: O(2^n)Explanation:

O(2 ^ (N)), where ‘N’ is the total number of houses.

Since we are checking every valid way of painting the houses and there are will be 3 * 2 ^(N) such ways. So, the overall time complexity will be O(2 ^ (N)).

Accepted Answer

Memoization

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

After observing the tree, we’ll find that there are some redundant function calls which means that there are some overlapping subproblems. The repetition of such sub-problems suggests that we can use dynamic programming to optimize our approach.

The key idea behind a dynamic programming approach is to use memoization, i.e. we’ll save the result of our sub-problem in a matrix so that it can be used later on.

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.

Now, consider the following steps to implement the getMinCost(int i, int j) function along with memoization :

Base Case:
- If i == -1, then return 0. It denotes that we don’t have any house to paint so the cost will be 0.
Check if the answer for this sub-problem already exists in the “dp” matrix i.e. dp[i][j] is not equal to -1. If it exists, then return it right away.
Now, if we are choosing to paint the i-th house with j-th colour then we can’t paint the (i - 1)-th house with j-th colour. Create a variable “ans” which will store the answer to the current sub-problem and initialise it with a very large integer.
Start traversing through the possible colours using a variable ‘k’.
- If (j != k) then we can choose the k-th colour to paint the (i - 1)-th house. Therefore, ans = min(ans, cost[i][j] + getMinCost(i - 1, k))
Store the “ans” into dp[i][j] to avoid redundant function calls.
Return “ans”.

Space Complexity: O(n)Explanation:

O(N), where ‘N’ is the total number of houses.

The only extra space which is being used is the dynamic programming table dp[][] of (3*N) dimension. Thus, the overall space complexity will be O(N).

Time Complexity: O(n)Explanation:

O(N), where ‘N’ is the total number of houses.

There will be at max N*3 distinct recursion calls in recursion because we are saving the result so there will be no redundant calls. Thus, the overall time complexity will be O(N).

Python (3.5)

'''

    Time Complexity: O(N)

    Space Complexity: O(N)



    Where ‘N’ is the number of houses.

'''



#  A very large integer.

inf = 100000000



# 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.

def getMinCost(i, j, cost, dp):

    if (i == -1):



        # Base case.

        return 0

    elif (dp[i][j] != -1):



        # Answer already exists in the "dp" matrix.

        return dp[i][j]

    else:



        # To store the answer of current sub-problem.

        ans = inf



        for k in range(3):

            if (k != j):



                # Choose the kth colour to paint the (i-1)th house.

                ans = min(ans, getMinCost(i - 1, k, cost, dp) + cost[i][j])



        # Store the "ans" in "dp" matrix to avoid redudant function calls.

        dp[i][j] = ans



        return ans





def minCost(cost):

    n = len(cost)



    dp = [[-1 for j in range(3)] for i in range(n)]



    ans = inf



    for j in range(3):



        # Paint the (n-1)th house with jth colour.

        ans = min(ans, getMinCost(n - 1, j, cost, dp))



    return ans

C++ (g++ 5.4)

/*

    Time Complexity: O(N)

    Space Complexity: O(N)



    Where 'N' is the number of houses.

*/



# define INT_MAX 2147483647



/*

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.

*/

int getMinCost(int i, int j, vector> &cost, vector> &dp)

{

	if (i == -1)

	{

		// Base case.

		return 0;

	}

	else if (dp[i][j] != -1)

	{

		// Answer already exists in the "dp" matrix.

		return dp[i][j];

	}

	else

	{

		// To store the answer of current sub-problem.

		int ans = INT_MAX;



		for (int k = 0; k < 3; k++)

		{

			if (k != j)

			{

				// Choose the kth colour to paint the (i-1)th house.

				ans = min(ans, getMinCost(i - 1, k, cost, dp) + cost[i][j]);

			}

		}



		// Store the "ans" in "dp" matrix to avoid redudant function calls.

		return dp[i][j] = ans;

	}

}



int minCost(vector> &cost)

{



	int n = cost.size();



	// "dp" matrix to store the minimum cost.

	vector> dp(n, vector(3, -1));



	int ans = INT_MAX;



	for (int j = 0; j < 3; j++)

	{

		// Paint the (n-1)th house with jth colour.

		ans = min(ans, getMinCost(n - 1, j, cost, dp));

	}



	return ans;

}

Java (SE 1.8)

/*

    Time Complexity: O(N)

    Space Complexity: O(N)



    Where 'N' is the number of houses.

*/



import java.util.Arrays;



public class Solution

{

	/*

	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.

	*/

	public static int getMinCost(int i, int j, int[][] cost, int[][] dp)

	{

		if (i == -1)

		{

			// Base case.

			return 0;

		}



		else if (dp[i][j] != -1)

		{

			// Answer already exists in the "dp" matrix.

			return dp[i][j];

		}



		else

		{

			// To store the answer of current sub-problem.

			int ans = Integer.MAX_VALUE;



			for (int k = 0; k < 3; k++)

			{

				if (k != j)

				{

					// Choose the kth colour to paint the (i-1)th house.

					ans = Math.min(ans, getMinCost(i - 1, k, cost, dp) + cost[i][j]);

				}

			}



			// Store the "ans" in "dp" matrix to avoid redudant function calls.

			return dp[i][j] = ans;

		}

	}



	public static int minCost(int[][] cost)

	{

		int n = cost.length;



		// "dp" matrix to store the minimum cost.

		int[][] dp = new int[n][3];



		for (int i = 0; i < n; i++)

		{

			Arrays.fill(dp[i], -1);

		}



		int ans = Integer.MAX_VALUE;



		for (int j = 0; j < 3; j++)

		{

			// Paint the (n-1)th house with jth colour.

			ans = Math.min(ans, getMinCost(n - 1, j, cost, dp));

		}



		return ans;

	}

}

Accepted Answer

Dynamic Programming

The basic idea of this approach is to solve the problem iteratively.

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

Initialize the “dp” matrix for the first house i.e. dp[0][0] = cost[0][0], dp[0][1] = cost[0][1], dp[0][2] = cost[0][2]
Start traversing the houses using a variable ‘i’ such that 1 <= ‘i’ < N
Now, let’s see the possible options for painting the current house.
- If the chosen colour is 0, then the (i - 1)-the house should be painted with colour 1 or colour 2. Therefore, dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + cost[i][0]
- If the chosen colour is 1, then the (i - 1)-the house should be painted with colour 0 or colour 2. Therefore, dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + cost[i][1]
- If the chosen colour is 2, then the (i - 1)-the house should be painted with colour 0 or colour 1. Therefore, dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + cost[i][2]
Now, the minimum value among dp[N-1][0], dp[N-1][1], dp[N-1][2] will be the minimum cost to paint the ‘N’ houses while following the given constraints.

Space Complexity: O(n)Explanation:

O(N), where ‘N’ is the total number of houses.

The only extra space which is being used is the dynamic programming table dp[][] of (3*N) dimension. Thus, the overall space complexity will be O(N).

Time Complexity: O(n)Explanation:

O(N), where ‘N’ is the total number of houses.

Since we are filling a “dp” matrix of 3 * ‘N’ dimensions. So, the overall time complexity will be O(N).

C++ (g++ 5.4)

/*
    Time Complexity  : O(N)
    Space Complexity : O(N)

    Where 'N' is the number of houses.
*/

int minCost(vector> &cost)
{

    int n = cost.size();

    // "dp" matrix to store the minimum cost.
    vector> dp(n, vector(3, 0));

    // Initialize the 'N' matrix for the first house.
    dp[0][0] = cost[0][0];
    dp[0][1] = cost[0][1];
    dp[0][2] = cost[0][2];

    for (int i = 1; i < n; i++)
    {
        // Choose green to paint the current house.
        dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + cost[i][0];

        // Choose red to paint the current house.
        dp[i][1] = min(dp[i - 1][2], dp[i - 1][0]) + cost[i][1];

        // Choose yellow to paint the current house.
        dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + cost[i][2];
    }

    // Minimum value to paint the last house will be the answer.
    return min(dp[n - 1][0], min(dp[n - 1][1], dp[n - 1][2]));
}

Java (SE 1.8)

/*

    Time Complexity  : O(N)

    Space Complexity : O(N)



    Where 'N' is the number of houses.

*/



import java.util.Arrays;



public class Solution

{

	public static int minCost(int[][] cost)

	{

		int n = cost.length;



		// "dp" matrix to store the minimum cost.

		int[][] dp = new int[n][3];



		for (int i = 0; i < n; i++)

		{

			Arrays.fill(dp[i], 0);

		}



		// Initialize the 'dp' matrix for the first house.

		dp[0][0] = cost[0][0];

		dp[0][1] = cost[0][1];

		dp[0][2] = cost[0][2];



		for (int i = 1; i < n; i++)

		{

			// Choose green to paint the current house.

			dp[i][0] = Math.min(dp[i - 1][1], dp[i - 1][2]) + cost[i][0];



			// Choose red to paint the current house.

			dp[i][1] = Math.min(dp[i - 1][2], dp[i - 1][0]) + cost[i][1];



			// Choose yellow to paint the current house.

			dp[i][2] = Math.min(dp[i - 1][0], dp[i - 1][1]) + cost[i][2];

		}



		// Minimum value to paint the last house will be the answer.

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

	}

}

Python (3.5)

'''

    Time Complexity: O(N)

    Space Complexity: O(N)



    Where ‘N’ is the number of houses.

'''



def minCost(cost):

    n = len(cost)



    # "dp" matrix to store the minimum cost.

    dp = [[-1 for j in range(3)] for i in range(n)]



    # Initialize the “dp” matrix for the first house.

    dp[0][0] = cost[0][0]

    dp[0][1] = cost[0][1]

    dp[0][2] = cost[0][2]



    for i in range(1, n):



        # Choose green to paint the current house.

        dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + cost[i][0]



        # Choose red to paint the current house.

        dp[i][1] = min(dp[i - 1][2], dp[i - 1][0]) + cost[i][1]



        # Choose yellow to paint the current house.

        dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + cost[i][2]



    # Minimum value to paint the last house will be the answer.

    return min(dp[n - 1][0], dp[n - 1][1], dp[n - 1][2])

Accepted Answer

Dynamic Programming - Space Optimized

We can observe in approach 3 that the current state depends on one immediate previous house. This suggests we can use three variables to store the cost of painting the previous house with given colors.

Let “lastGreen”, “lastRed” and “lastYellow” be three variables that store the cost if the last house is painted with green, red and yellow color, respectively.

Algorithm

Initialize all the three variables for the first house i.e. lastGreen = cost[0][0], lastRed = cost[0][1], lastYellow = cost[0][2]
Start traversing the houses using a variable ‘i’ such that 1 <= ‘i’ < N
Let’s see the possible options of painting the current house.
- Let “curGreen”, “curRed” and “curYellow” be three variables which store the cost if the current house is painted with green, red and yellow, respectively.
- If the chosen colour is green, then the (i - 1)-the house should be painted with red or yellow. Therefore, curGreen = min(lastRed, lastYellow) + cost[i][0]
- If the chosen colour is red, then the (i - 1)-the house should be painted green or yellow. Therefore, curRed = min(lastGreen, lastYellow) + cost[i][1]
- If the chosen colour is yellow, then the (i - 1)-the house should be painted green or red. Therefore, curYellow = min(lastGreen, lastRed) + cost[i][2]
- Now, copy the current values into the last ones.
Now, the minimum value among “lastGreen”, “lastRed”, “lastYellow” will be the minimum cost to paint the ‘N’ houses while following the given constraints.

Space Complexity: O(1)Explanation:

O(1)

We are not using any extra space.

Time Complexity: O(n)Explanation:

O(N), where ‘N’ is the total number of houses.

Since we are iterating all the houses once. So, the overall time complexity will be O(N).

Java (SE 1.8)

/*

    Time Complexity  : O(N)

    Space Complexity : O(1)



    Where 'N' is the number of houses.

*/



public class Solution

{

	public static int minCost(int[][] cost)

	{

		// Initialize all the three variables for the first house.

		int lastGreen = cost[0][0];

		int lastRed = cost[0][1];

		int lastYellow = cost[0][2];



		for (int i = 1; i < cost.length; i++)

		{

			// Choose green to paint the current house.

			int curGreen = Math.min(lastRed, lastYellow) + cost[i][0];



			// Choose red to paint the current house.

			int curRed = Math.min(lastYellow, lastGreen) + cost[i][1];



			// Choose yellow to paint the current house.

			int curYellow = Math.min(lastGreen, lastRed) + cost[i][2];



			// Copy the current values into the last ones.

			lastGreen = curGreen;

			lastRed = curRed;

			lastYellow = curYellow;

		}



		// Minimum value among 'lastGreen', 'lastRed', 'lastYellow' will be the minimum cost.

		return Math.min(lastGreen, Math.min(lastRed, lastYellow));

	}

}

C++ (g++ 5.4)

/*

    Time Complexity  : O(N)

    Space Complexity : O(1)



    Where 'N' is the number of houses.

*/



int minCost(vector> &cost)

{

	// Initialize all the three variables for the first house.

	int lastGreen = cost[0][0];

	int lastRed = cost[0][1];

	int lastYellow = cost[0][2];



	for (int i = 1; i < cost.size(); i++)

	{

		// Choose green to paint the current house.

		int curGreen = min(lastRed, lastYellow) + cost[i][0];



		// Choose red to paint the current house.

		int curRed = min(lastYellow, lastGreen) + cost[i][1];



		// Choose yellow to paint the current house.

		int curYellow = min(lastGreen, lastRed) + cost[i][2];



		// Copy the current values into the last ones.

		lastGreen = curGreen;

		lastRed = curRed;

		lastYellow = curYellow;

	}



	// Minimum value among 'lastGreen', 'lastRed', 'lastYellow' will be the minimum cost.

	return min(lastGreen, min(lastRed, lastYellow));

}

Python (3.5)

'''

    Time Complexity: O(N)

    Space Complexity: O(1)



    Where ‘N’ is the number of houses.

'''



def minCost(cost):



    # Initialize all the three variables for the first house.

    lastGreen = cost[0][0]

    lastRed = cost[0][1]

    lastYellow = cost[0][2]



    for i in range(1, len(cost)):



        # Choose green to paint the current house.

        curGreen = min(lastRed, lastYellow) + cost[i][0]



        # Choose red to paint the current house.

        curRed = min(lastYellow, lastGreen) + cost[i][1]



        # Choose yellow to paint the current house.

        curYellow = min(lastGreen, lastRed) + cost[i][2]



        # Copy the current values into the last ones.

        lastGreen = curGreen

        lastRed = curRed

        lastYellow = curYellow



    # Minimum value among “lastGreen”, “lastRed”, “lastYellow” will be the minimum cost.

    return min(lastYellow, lastRed, lastGreen)

Input Format :

Output Format :

Note :

Constraints :

Top Springworks Software Developer Intern interview questions & answers

Popular interview questions of Software Developer Intern

Top HR questions asked in Springworks Software Developer Intern