Java solution using Greedy approach


  • 0
    C
        // idea is to make a greedy approach for each new house and then add memorization for first and second min value
        public int minCost(int[][] costs) {
            int minCost1 = 0, minCost2 = 0, prevColor = -1;
            
            for(int i=0; i<costs.length; i++){
                int curColor=0, curMin1 = -1, curMin2 = -1; 
                for(int j=0; j<3; j++){
                    // handling usecase where there is min color index conflict with adjacent house
                    int cost = costs[i][j] + ((j != prevColor) ? minCost1 : minCost2);
                    
                    // storing the first and second min for each house 
                    if(curMin1 < 0 || curMin1 > cost){
                        curMin2 = curMin1;
                        curMin1 = cost;
                        curColor = j;
                    }
                    else if(curMin2 < 0 || curMin2 > cost){
                        curMin2 = cost;
                    }
                }
                
                minCost1 = curMin1;
                minCost2 = curMin2;
                prevColor = curColor;
            }
            
            return minCost1;
        }
    

Log in to reply
 

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