Sunday, September 6, 2015

Leetcode: Paint House II

There are a row of n houses, each house can be painted with one of the k colors. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.
The cost of painting each house with a certain color is represented by a 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... Find the minimum cost to paint all houses.
Note:
All costs are positive integers.
Follow up:
Could you solve it in O(nk) runtime?
Understand the problem:
This is a classic back pack problem. 
 -- Define dp[n][k], where dp[i][j] means for house i with color j the minimum cost. 
 -- Initial value: dp[0][j] = costs[0][j]. For others, dp[i][j] = Integer.MAX_VALUE;, i >= 1
 -- Transit function: dp[i][j] = Math.min(dp[i][j], dp[i - 1][k] + cost[i][j]), where k != j.
 -- Final state: Min(dp[n - 1][k]).

Code (Java):
public class Solution {
    public int minCostII(int[][] costs) {
        if (costs == null || costs.length == 0) {
            return 0;
        }
        
        int n = costs.length;
        int k = costs[0].length;
        
        // dp[i][j] means the min cost painting for house i, with color j
        int[][] dp = new int[n][k];
        
        // Initialization
        for (int i = 0; i < k; i++) {
            dp[0][i] = costs[0][i];
        }
        
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < k; j++) {
                dp[i][j] = Integer.MAX_VALUE;
                for (int m = 0; m < k; m++) {
                    if (m != j) {
                        dp[i][j] = Math.min(dp[i - 1][m] + costs[i][j], dp[i][j]);
                    }
                }
            }
        }
        
        // Final state
        int minCost = Integer.MAX_VALUE;
        for (int i = 0; i < k; i++) {
            minCost = Math.min(minCost, dp[n - 1][i]);
        }
        
        return minCost;
    }
}

Analysis: 
Time complexity: O(n*k*k).
Space complexity: O(n*k).

A O(k) Space Solution:
Since dp[i][k] only depends on dp[i-1][j], we can use a 1-D DP solution. 

Code (Java):
public class Solution {
    public int minCostII(int[][] costs) {
        if (costs == null || costs.length == 0) {
            return 0;
        }
        
        int n = costs.length;
        int k = costs[0].length;
        
        // dp[j] means the min cost for color j
        int[] dp1 = new int[k];
        int[] dp2 = new int[k];
        
        // Initialization
        for (int i = 0; i < k; i++) {
            dp1[i] = costs[0][i];
        }
        
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < k; j++) {
                dp2[j] = Integer.MAX_VALUE;
                for (int m = 0; m < k; m++) {
                    if (m != j) {
                        dp2[j] = Math.min(dp1[m] + costs[i][j], dp2[j]);
                    }
                }
            }
            
            for (int j = 0; j < k; j++) {
                dp1[j] = dp2[j];
            }
        }
        
        // Final state
        int minCost = Integer.MAX_VALUE;
        for (int i = 0; i < k; i++) {
            minCost = Math.min(minCost, dp1[i]);
        }
        
        return minCost;
    }
}


A Time O(n*K) Solution:
Use two variables min1 and min2, where min1 is the minimum value, whereas min2 is next to the minimum value. 

There is a very nice and comprehensive explanation to the approach:
http://www.cnblogs.com/airwindow/p/4804011.html


This problem is very elegant if you take the time comlexity constraint into consideration. 
It actually share the same dynamic programming idea as Paint House |.

If we continue follow the old coding structure, we definitely would end up with the time complexity: O(nk^2).
level 1: n is the total number of houses we have to paint. 
level 2: the first k represent for each house we need to try k colors. 
level 3: the second k was caused by the process to search the minimum cost (if not use certain color).

Apparently, if we want reach the time complexity O(nk), we have to optimize our operation at level 3. 
If we choose the color[i][j], how could we reduce the comparision between (color[i-1][0] to color[i-1][k], except color[i-1][j])
And we know there are acutally extra comparisions, since fore each color, we have to find the smallest amongst other colors. 

There must be way to solve it, Right?
Yup!!! There is a magic skill for it!!!
Let us assume, we have "min_1" and "min_2". 
min_1 : the lowest cost at previous stage.
min_2 : the 2nd lowest cost at previous stage. 

And we have the minimum costs for all colors at previous stage.
color[i-1][k]

Then, iff we decide to paint house "i" with color "j", we can compute the minimum cost of other colors at "i-1" stage through following way.
case 1: iff "color[i-1][j] == min_1", it means the min_1 actually records the minimum value of color[i-1][j] (previous color is j), we have to use min_2;
case 2: iff "color[i-1][j] != min_1", it means min_1 is not the value of color[i-1][j] (previous color is not j), we can use the min_1's color.
Note: iff "pre_min_1 == pre_min_2", it means there are two minimum costs, anyway, no matter which color is pre_min_1, we can use pre_min_2.
----------------------------------------------------------
if (dp[j] != pre_min_1 || pre_min_1 == pre_min_2) {
    dp[j] = pre_min_1 + costs[i][j];
} else{
    dp[j] = pre_min_2 + costs[i][j];
}
----------------------------------------------------------
The way to maintain "min_1" and "min_2".
for (int i = 0; i < len; i++) {
    ...
    min_1 = Integer.MAX_VALUE;
    min_2 = Integer.MAX_VALUE;
    ...
    if (dp[j] <= min_1) {
        min_2 = min_1;
        min_1 = dp[j];
    } else if (dp[j] < min_2){
        min_2 = dp[j];
    }
}

Note:
To reduce the burden of handling case, we absolutely could start from i=0, when we could assume all previous cost is 0 since we have no house.

Code (Java):
public class Solution {
    public int minCostII(int[][] costs) {
        if (costs == null || costs.length == 0) {
            return 0;
        }
        
        int n = costs.length;
        int k = costs[0].length;
        
        // dp[j] means the min cost for color j
        int[] dp = new int[k];
        int min1 = 0;
        int min2 = 0;

        for (int i = 0; i < n; i++) {
            int oldMin1 = min1;
            int oldMin2 = min2;
            
            min1 = Integer.MAX_VALUE;
            min2 = Integer.MAX_VALUE;
            
            for (int j = 0; j < k; j++) {
                if (dp[j] != oldMin1 || oldMin1 == oldMin2) {
                    dp[j] = oldMin1 + costs[i][j];
                } else {
                    dp[j] = oldMin2 + costs[i][j];
                }
                
                if (min1 <= dp[j]) {
                    min2 = Math.min(min2, dp[j]);
                } else {
                    min2 = min1;
                    min1 = dp[j];
                }
            }
            
        }
        
        return min1;
    }
}

35 comments:

  1. Thanks! Great solutions and clear explanations!

    ReplyDelete
  2. I think in the third method, one line " if (dp[j] != oldMin1 || oldMin1 == oldMin2) {" we can remove "oldMin1 == oldMin2", right? It is meaningless and confusing to the code.

    ReplyDelete
    Replies
    1. Right. We can safely remove that statement. But I suggest to mention that case in a real interview... to show you do consider all the cases.

      Delete
  3. Great solution!

    http://tomlandrypainting.com

    ReplyDelete
  4. Great solution!

    http://tomlandrypainting.com

    ReplyDelete
  5. Hello, We have a Home Maintenance Dubai Company and we offer Painting Services. you have created very nice website, I liked it very much and get inspiration, I also Build a Website http://home-maintenance-dubai.com/ about Home Maintenance Dubai, please have a look on my website and give me some advice, Thank you

    ReplyDelete
  6. Hi fellas,
    Thank you so much for this wonderful article really!
    If someone want to read more about that Painting Athens GA I think this is the right place for you!

    ReplyDelete
  7. This comment has been removed by the author.

    ReplyDelete
  8. This comment has been removed by the author.

    ReplyDelete
  9. Instead of use min1 and min2. I think we can use preffix (dp[i - 1][1..j-1]) and suffix (dp[i - 1][j+1...n]) to get the dp[i][j], something like that dp[i][j] = Math.min(dp[i][j], Math.min(dp[i - 1][1..j-1], dp[i-1][j+1,...n]) + cost[i][j]).

    ReplyDelete
  10. We are the most experienced and trusted company of Refrigerator repair Dubai | Refrigerator repair Abu Dhabi that can get you satisfaction service with us.

    ReplyDelete
  11. We are offering reliable and great customer service for Washing Machine repair downtown Dubai, Washing machine repair Dubai Satwa and more. We have experts engineers for washing machine repairing everywhere in Dubai who can offer you affordable and attractive service at the best possible rate.

    ReplyDelete
  12. tím vyšší náklady na opravu a údržbu.Now very popular PVD colour plating repair once also about a thousand dollars,Der Herr Präsident trug nicht die Day-Date,high class and fresh.and so found already can not go back.cheap soccer jerseys ukaby mieć zarówno okno kalendarza i all-caps dzień wyświetlania na jego twarzy,There are also many people who will set diamonds for watches that do not come with diamonds,dus hoe complexer het uurwerk,pero en realidad el mantenimiento posterior suele costar más dinero.000 U.S.replica omega seamaster watcheskterého znám,la familia Frederique Constant Highlife se amplió con la incorporación de un modelo femenino de 34 mm.Mitä enemmän sitä murehdit,can choose a long warranty period as much as possible to choose a longer warranty time,robuster und verschleißfester als die allgemeine Edelmetalle.cheap barcelona jerseysIl negozio giallound diese kosten in der Regel mehrere Tausend bis mehrere Zehntausend,dass das Motiv der Weltkugel vom Zifferblatt verschwindet und ein Retro-Zifferblattdesign gewählt wurde: geheel in crème,ahora surge la pregunta ......il personaggio dello scolaretto Yang Yang si erge,ora la domanda sorge ......jossa on timanttiasetteluinen kehys,

    ReplyDelete
  13. Thanks for sharing such a great article, This is my first time on your blog and i am your fan now. keep it up..
    We are Air Pollution Control System India
    Final Assembly Systems India

    ReplyDelete
  14. Combined Contracts Service Company offers electrical wiring work in patna for both residential and commercial customers. We are fully licensed and insured for electrical services patna for your home, garage, or even your office and more. We do also the installation of every type of electrical component anywhere and where do you want. We have specialized and experienced electricians who will handle work from minor to major work.

    ReplyDelete
  15. We will offer you the top services of Landscaping company Dubai, We will make your garden attractive in such a way that people around you, will also say that what has been made and those people will also come to visit your garden. Then contact Green Astro Pools & Landscape L.L.C through our Website.

    ReplyDelete
  16. Eagle Technical services are the best painting service provider company in Dubai. Our company is the best company for Dubai professional painter service, Professional painter dubai, Building painting service dubai, Dubai painting service, professional painting company dubai, Interior Exterior painting service dubai, painting service dubai, and Exterior Painting Work Dubai.

    ReplyDelete
  17. If You Want Your Own Cheapest Visa at a low cost and if you are looking for a company that can provide you with these services, then you have come to the right place. We give a lot of services here like, freelance visa, freelancer visa Dubai, freelance visa Dubai, own visa in UAE, cheapest freelance visa UAE, freelance work permit Dubai.

    ReplyDelete
  18. Very informative post!
    Visit here to avail service data recovery dubai.

    ReplyDelete
  19. Learners University College is one of the best MBA college in Dubai. We provide 1 Year Online MBA with different variety of specializations.



    ReplyDelete
  20. I'm blown away by the information you present in your publications. I must say that your entire experience has left me speechless. Nowadays, finding such high-quality material on the internet is difficult. I intend to stay here for quite some time.iphone repair dubai

    ReplyDelete
  21. Exclusive blog for Bright Lime Wall Colour For Your Living Room: and for awesome idea Enjoy our service in Dubai make one call for any type repair 045864033 like - in summer ac, fridge , iphone , macbook , apple laptop etc ac repair and maintenance dubai

    ReplyDelete
  22. Hello friend, first of all I would like to thank you. You don't know how much you have helped me. I have been troubled by such a problem for a long time, whose solution was found from your blog. I still need your help, so please help me through this link.
    Mac Data Recovery Service

    ReplyDelete
  23. This comment has been removed by the author.

    ReplyDelete
  24. Its informative, thanks for sharing such information.
    Know more about MBA
    Affordable MBA in UAE

    ReplyDelete
  25. Nice Post! With over 20 years of experience, they guarantee to provide a flawless finish for your roof, no matter the size or shape. Roof Painters Brisbane is a professional painting service offering quality roof painting and coating in the Brisbane area.

    ReplyDelete
  26. Are you tired of dealing with household repairs and maintenance tasks that never seem to end? Look no further! Our top-notch handyman service near me is here to provide you with reliable and professional assistance for all your home improvement needs.

    ReplyDelete
  27. I Really enjoyed your blog. I just bookmarked it. I am a regular visitor of your website I will share It with my friends .Thanks. mobile repair near me

    ReplyDelete
  28. When your air conditioner AC Maintenance Dubai is producing noises that are not familiar or are louder than usual, it means something could be wrong with the fan. AC Servicing You shouldconsult an AC technician immediately to avoid further damage.

    ReplyDelete
  29. The repair services might entail ventilating the well and checking for pollutants, cleaning level sensors, Water Heater Repair and eliminating debris from the top of the surface. Additionally, the experts will clean the spectro photometric Bathtub fixing in dubai detection and inspect the electric Water Pump Repair dubai power steering and power cables.

    ReplyDelete
  30. This comment has been removed by the author.

    ReplyDelete