Paint House II

Hard
0/120
Average time to solve is 45m
profile
Contributed by
15 upvotes
Asked in companies
AppleUrban Company (UrbanClap)

Problem statement

Ninja has started a painting business recently. He got a contract to paint ‘N’ houses in a city. Ninja has ‘K’ colors to choose from. But the client has a condition 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. 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.

Your task is to help Ninja to find the minimum cost required to paint houses according to this condition.

For Example : 
Let say N = 2 and K = 3 and costs = [ [1,5,3] , [2,9,4] ] 

In this case,
Ninja can paint house 0 into color 0, paint house 1 into color 2. Minimum cost: 1 + 4 = 5; 
Or paint house 0 into color 2, paint house 1 into color 0. Minimum cost: 3 + 2 = 5 .
Note : 
Assume 0 based indexing
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of input contains an integer ‘T’ denoting the number of test cases to run. Then the test case follows.

The first line of each test case contains two integers ‘N’ and ‘K’ representing the number of houses and the number of colors available respectively.

The next ‘N’ line contains ‘K’ integers denoting the cost of painting i-th house with j-th color where 0 <= i < n  & 0 <= j < k.
Output Format : 
For each test case print the minimum cost of painting the houses.

Print the output of each test case in a separate line.
Note : 
You do not need to print anything or take input. This already has been taken care of. Just implement the function.
Constraints : 
1 <= T <= 5
1 <= n, k <= 10^4
1 <= costs[i][j] <= 10^3

Time limit: 1 sec
Sample Input 1 :
2
2 3
1 5 3
2 9 4
3 3
1 4 5
2 3 5
6 7 8
Sample Output 1 :
5
10
Explanation Of Sample Input 1 :
Test Case 1 :

In this case, Ninja can paint house 0 into color 0, paint house 1 into color 2. Minimum cost: 1 + 4 = 5; 
Or paint house 0 into color 2, paint house 1 into color 0. Minimum cost: 3 + 2 = 5 .

Hence the minimum cost will be 5.

Test case 2 :

In this case, Ninja can paint house 0 into color 0, paint house 1 into color 1, paint house 2 in color 0. Minimum cost : 1 + 3 + 6 = 10.
Sample Input 2 :
2
2 3
1 2 3
10 11 12 
1 2
4 2
Sample output 2 :
12
2
Hint

Try to solve this using recursion

Approaches (3)
Brute Force Approach

For choosing a color for each house we have to keep two things in mind:

 

  1. Choosing the color having minimum cost.
  2. The chosen color is not chosen by the previous house.

 

We can solve this by a simple recursion in the following steps;

 

Algorithm

 

  • Make a function int recursion( int lastColor, int currentHouse, int costs[][])
  • The base case will be if the pointer to currentHouse == size of costs matrix then return 0.
  • Initialize a variable ans equal to the maximum value of int.
  • Iterate i from 0 to k.
    • if(i != lastChosen colour)
    • Then update ans  recursively as ans = min (ans, costs[currentHouse][i]+ recursion( i, currentHouse+1, costs).
  • Return ans.
Time Complexity

 O(N^K), where ‘N’ is the number of houses and ‘K’ is the number of colors.

 

For each house, we have K-1 options (except for the first house) so the complexity will be N^K.

Space Complexity

O(N*K), where ‘N’ is the number of houses and ‘K’ is the number of colors.

 

The space complexity due to the recursion stack will be O(N*K) 

Code Solution
(100% EXP penalty)
Paint House II
Full screen
Console