Minimum Cost to Paint all Houses with No Adjacent Houses have Same Color

Problem statement: There are N houses. The amount to color each house with Red, Green, Blue colors is given. Write a program to find the minimum amount to paint all houses such that no 2 adjacent houses have the same color.

This coding question was asked in the coding round of the Amazon interview for the SDE-2 role.

The difficulty level of this problem is moderate.

Example

Input:

N = 3
Red = [6, 5, 3]
Green = [3, 1, 6]
Blue =  [9, 4, 2]

Output:

9

Explanation

We get the minimum cost of painting all houses when we paint the first house with the color Red (6), the second house with the color Green (1), and the third house with the color Blue (2). So the total minimum cost to paint all houses is 9 (6+1+2).

You can use any programming langauge of your choice like C/C++, Java, Python, etc.

Python Solution

To solve this problem, we are going to use recursion and dynamic programming. The rest of the code is self-explanatory.

Prerequisite:

• if-else statement in Python
• Python list

Python Code:

def colorHouse(N, red, green, blue, latest_color=None, count=0):
    if count == N:
        return 0

    if latest_color==None:
        return min(
            red[count] + colorHouse(N, red, green, blue, 'r', count+1 ), 
            green[count] + colorHouse(N, red, green, blue, 'g', count+1), 
            blue[count] + colorHouse(N, red, green, blue, 'b', count+1) 
        )
    elif latest_color=='r':
        return min(
            green[count] + colorHouse(N, red, green, blue, 'g', count+1), 
            blue[count] + colorHouse(N, red, green, blue, 'b', count+1) 
        )
    elif latest_color=='g':
        return min(
            red[count] + colorHouse(N, red, green, blue, 'r', count+1 ), 
            blue[count] + colorHouse(N, red, green, blue, 'b', count+1) 
        )
    else:
        return min(
            red[count] + colorHouse(N, red, green, blue, 'r', count+1 ), 
            green[count] + colorHouse(N, red, green, blue, 'g', count+1) 
        )


N = 3
Red = [6, 5, 3]
Green = [3, 1, 6]
Blue =  [9, 4, 2]
out = colorHouse(N, Red, Green, Blue)
print("Minimum cost to paint houses: ", out)

Output:

Minimum cost to paint houses:  9

You can try executing this program with different input values.

If you have any doubt or if you have a better solution for finding minimum cost to paint all houses, let’s discuss in the comment.