Easiest O(1) space JAVA solution


  • 31

    To solve this DP problem:

    • If there's no constraint, we choose min cost for each house.
    • Since house[i] and house[i - 1] cannot have the same color j, we should choose 2nd min color for house[i - 1].
    • If we choose the 3rd min color for house[i - 1], we might miss potential min cost.
    • min(i) = min(cost[i][j] + 1st min / 2nd min), 0 < j < n.
    • Since current row only relies on last row for getting mins and avoiding same color, O(1) space is enough.

    public int minCostII(int[][] costs) {
        if (costs.length == 0) {
            return 0;
        }
        int min1 = 0, min2 = 0, index1 = -1;
        
        for (int i = 0; i < costs.length; i++) {
            int m1 = Integer.MAX_VALUE, m2 = Integer.MAX_VALUE, idx1 = -1;
            
            for (int j = 0; j < costs[0].length; j++) {
                int cost = costs[i][j] + (j != index1 ? min1 : min2);
    
                 if (cost < m1) {           // cost < m1 < m2
                    m2 = m1; m1 = cost; idx1 = j; 
                
                } else if (cost < m2) {    // m1 < cost < m2
                    m2 = cost;
                }
            }
            
            min1 = m1; min2 = m2; index1 = idx1;
        }
        return min1;
    }

  • 0
    K

    Great Answer.
    It is more like a greedy algorithm than a DP.


  • 0
    A

    How do you know that you can select 2nd min cost color for the current house? I am not able to understand how greedy works here. I believe you should also consider the case where you choose the second min cost for previous house since it might cost lesser than choosing min1 for previous and min2 for current house.

    Thanks in advance.


  • 0
    O

    Awesome answer!

    This is a DP solution. It has a greedy method to calculate state transfer.

    Previously I used an additional n*k array to maintain the min value of painting i except color j. It's O(nk) but 100+ times slower than this solution:

    public class Solution {
        // yavinci's 3ms 98%
        public int minCostII(int[][] costs) {
            if (costs.length < 1) return 0;
            int n = costs.length, k = costs[0].length, min = 0, iMin = 0, min2nd = 0;
            for (int i = 0; i < n; i++) {
                int m1 = Integer.MAX_VALUE, m2 = m1, im1 = -1;
                for (int j = 0; j < k; j++) {
                    int cost = costs[i][j] + (j == iMin ? min2nd : min);
                    if (cost < m1) {
                        m2 = m1; m1 = cost; im1 = j;
                    } else
                    if (cost < m2)
                        m2 = cost;
                }
                min = m1; iMin = im1; min2nd = m2;
            }
            return min;
        }
    
    /* Old solution: 500ms, 0.21%
        public int minCostII(int[][] costs) {
            if (costs.length < 1) return 0;
            int n = costs.length, m = costs[0].length;
            int[][] opt = new int[n + 1][m], minFor = new int[n + 1][m];
            // minFor[i][j] if the min of opt[i] elements except opt[i][j];
            
            for (int i = 1; i <= n; i++) {
                for(int j = 0; j < m; j++) {
                    opt[i][j] = minFor[i - 1][j] + costs[i - 1][j]; System.out.println(opt[i][j]);}
                update(opt[i], minFor[i], m);
            }
            return Math.min(opt[n][0], minFor[n][0]);
        }
        
        private void update(int[] a, int[] minEcpt, int m) {
            for (int i = 1, min = a[0]; i < m; min = Math.min(min, a[i++]))  
                minEcpt[i] = min;
            minEcpt[0] = Integer.MAX_VALUE;
            for (int i = m - 2, min = a[m - 1]; i >= 0; min = Math.min(min, a[i--])) 
                minEcpt[i] = Math.min(min, minEcpt[i]);
        }
        */
    }

  • 0

    Very clear! I still have difficulty in telling the DP and greedy...


  • 1
    C

    Nice solution!, I was having hard time to figure out how to handle situation when min for two adjacent house has same color index. Looking at your solution have me idea how to resolve it! Basically if we store the second min for each house we can solve the same color index issue.

    Thanks again


  • 0
    B

    @ofLucas old solution is slow because there is a system println...


  • 0
    X

    @am-shashank same here, i think we have to check Math.min(previousMin+current2ndMin, previous2ndMin+currentMin)..


  • 0
    O

    This one is awesome.


  • 0

    Great way to keep track of the min-most and second-min element!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.