[Solution]Problem 17: Minimum cost of painting N houses up to K different colors.[Facebook]
Minimization, Matrix Traversal, Cost Calculations
Problem
This problem was asked by Facebook.
A builder is looking to build a row of N houses that can be of K different colors. He has a goal of minimizing cost while ensuring that no two neighboring houses are of the same color.
Given an N by K matrix where the nth row and kth column represents the cost to build the nth house with kth color, return the minimum cost which achieves this goal.
Step 1: Brute Force
For the brute force solution, we create every combination and filter out any invalid one (two houses next to each other have the same color). We take the min cost of the ones remaining.
We will not waste any time coding it up since you will not want to present it in your interview (The time complexity is O(N^K)). But it can be helpful in providing a few hints.
Notice that we are wasting a lot of computations on a few things. First off we are generating lots of invalid sequences. Secondly, we also have to waste a lot of time calculating the costs of any color configuration. Take for example two combinations RBR (Red, Blue, Red) and RBG (Red, Blue, Green). Both these have the same cost in the RB portion. So going over every string individually is wasting a lot of this. For longer/more common sequences, this is going to add lots of costs.
Step 2: Enter Dynamic Programming
When we have plenty of repeating subsequences, DP can be a very useful tool. We can maintain a matrix cache where every entry [i][j] represents the minimum cost of painting house i the color j, as well as painting every house < i. We can calculate this by looking at the minimum cost of painting each house < i - 1, and painting house i - 1 any color except j, since that would break our constraint.
How do we handle the calculations? If we already have the costs calculated for painting upto i-1 houses, we can just add the minimum cost in the ith row to find minimum cost upto (and including) i houses. We just have to be careful to not violate the color constraint.
We'll initialize the cost row with zeroes to start. Then we go through our row. Every value in that row represents the cost to paint our house a particular color. So we just have to go through the row, and add the minimum cost of color per row. We just check to avoid color overlap.
By doing so, we both handle the color constraint, while working to minimize the costs.
def build_houses(matrix):
k = len(matrix[0])
soln_row = [0] * k
for r, row in enumerate(matrix):
#every value in row i is the cost of painting the house i 1 color
new_row = []
for c, val in enumerate(row):
#new row
new_row.append(min(soln_row[i] for i in range(k) if i != c) + val)
soln_row = new_row
return min(soln_row)
We are looping through the matrix N times (for every house). For every house, we also have to go through every color to update our row to update the costs up to the ith house. And finally, we have to check the minimum cost in the final row. Thus our time complexity is O(N* K^2). Since we track the row costs, our space complexity is O(K).
How can we optimize this? There is a very simple mathematical optimization that our approach is overlooking. Look over the code we have solved, and trace the run. You might be able to identify it. Once you’ve figured it out (or given up), proceed.
Step 4: Removing Needless Looping
Look at the part where we append new values to our solution row.
Keep reading with a 7-day free trial
Subscribe to Technology Made Simple to keep reading this post and get 7 days of free access to the full post archives.