Java Solution using Greedy Approach


  • 0
    C
        // This problem takes a greedy approach with memorization logic
        public int minCostII(int[][] costs) {
            int prevColor = -1, prevMin1 = 0, prevMin2 = 0;
            for(int i=0; i<costs.length; i++){
                int curColor = -1, curMin1 = -1, curMin2 = -1;
                
                for(int j=0; j<costs[i].length; j++){
                    // takes care when there is a min cost color index conflict
                    int cost = costs[i][j] + ((j != prevColor) ? prevMin1 : prevMin2);
                    
                    if(curMin1 < 0 || curMin1 > cost){
                        curMin2 = curMin1;
                        curMin1 = cost;
                        curColor = j;
                    }
                    else if(curMin2 < 0 || curMin2 > cost){
                        curMin2 = cost;
                    }
                }
                
                prevMin1 = curMin1;
                prevMin2 = curMin2;
                prevColor = curColor;
            }
            
            return prevMin1;
        }
    

Log in to reply
 

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