Paint House

Hard
0/120
Average time to solve is 20m
profile
Contributed by
24 upvotes
Asked in companies
AppleAmazonSamsung

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
2
2 3 2
1 4 1
1
1 2 3
Sample output 1 :
3
1
Explanation Of Sample Output 1 :
For the first test case, in the optimal case, we can paint house 0 (0-th based indexing) with colour 0 (0-th based indexing) and house 1 with colour 2. The cost will be 2 + 1 = 3.

For the second test case, we can choose the colour 0 to paint the house. And the cost will be 1.
Sample Input 2 :
2
3
14 2 11
11 14 5
14 3 10
2
1 2 3
1 4 6
Sample output 2 :
10
3
Explanation Of Sample Output 2 :
For the first test case, in the optimal case, we can paint house 0 (0-th based indexing) with colour 1 (0-th based indexing), house 1 with colour 2  and house 2 with colour 1. The cost will be 2 + 5 + 3 = 10.

For the second test case, the minimum cost will be 3.
Hint

Can you think of breaking the problem into sub-problems?

Approaches (4)
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”.
Time Complexity

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

Space Complexity

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

Video Solution
Unlock at level 3
(75% EXP penalty)
Code Solution
(100% EXP penalty)
Paint House
Full screen
Console