[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.
You should realize two things: 1) For all but one color, we will use the same minimum color; 2) For that one color, we’ll use the second-lowest cost color. To make sure that we don’t repeat 2 colors back to back, we also have to track the last color we used (column index).
Therefore, if we tracked those values, we no longer have to worry about looping through our entire row.
Then, when looking at the value at each row, we only need to do the following:
Check if the index is the index of the lowest cost of the previous row. If it is, then we can't use this color -- we'll use the second-lowest-cost instead. Otherwise, use the lowest cost of the previous row
Calculate the minimum cost if we painted this house this particular color
Update our new lowest cost/index or second-lowest cost if appropriate
Now we'll always have our lowest cost in a variable, and once we've gone through the matrix we can just return that.
from math import inf
def build_houses(matrix):
lowest_cost, lowest_cost_index = 0, -1
second_lowest_cost = 0
for r, row in enumerate(matrix):
new_lowest_cost, new_lowest_cost_index = inf, -1
new_second_lowest_cost = inf
for c, val in enumerate(row):
prev_lowest_cost = second_lowest_cost if c == lowest_cost_index else lowest_cost
cost = prev_lowest_cost + val
if cost < new_lowest_cost:
new_second_lowest_cost = new_lowest_cost
new_lowest_cost, new_lowest_cost_index = cost, c
elif cost < new_second_lowest_cost:
new_second_lowest_cost = cost
lowest_cost = new_lowest_cost
lowest_cost_index = new_lowest_cost_index
second_lowest_cost = new_second_lowest_cost
return lowest_costNow we’re looping through the houses once and going throw each color for every house. This makes the time complexity O(N*K). The space complexity is O(1) since we only track 3 numerical variables.
Final: O(N*K) Time and O(1) space
Bonuses/Promotion (Get Free Stuff)
Have anything to say to me? Use the links below.
To learn how to interview better DM me. Let’s set up mock interviews and go over different interview techniques. In addition to focused questions, and a detailed personalized plan, we will go over the right questions to ask during your interviews.
For most of my students, mock interviews have been very helpful. Enough mock interview practice is the key between getting that job offer and rejection. If you can get three people to become paying subscribers to this newsletter, you win a free mock interview. This offer has no upper limit, so the more subs you can get, the more mock interviews you win.
To share interesting problems/solutions with me, reach out to me. Different social media of mine also have other content from me. Good problems and/or solutions receive a free shoutout + 2 months of the paid newsletter:
Reach out to me on:
Instagram: https://www.instagram.com/iseethings404/
Message me on Twitter: https://twitter.com/Machine01776819
My LinkedIn: https://www.linkedin.com/in/devansh-devansh-516004168/
My content:
Read my articles: https://rb.gy/zn1aiu
My YouTube: https://rb.gy/88iwdd
Get a free stock on Robinhood. No risk to you, so not using the link is losing free money: https://join.robinhood.com/fnud75