Java O(nk) 6ms solution with explanation


  • 0

    In Paint House I, my solution was O(n3^2) since I memorized all the cost for 3 colors. For this problem, it will
    be O(nk^2). But the fact is we do not need memorize the cost for all different colors. Since 2 adjacent houses cannot be painted in the same color, the lowest cost and the second lowest cost to the last house should be memorized and that is O(2nk) = O(nk).

    public class Solution {
    public int minCostII(int[][] costs) {
        if(costs.length==0){
            return 0;
        }
        if(costs.length>1&&costs[0].length==1)return 0;
        int smallest = Integer.MAX_VALUE;
        int secsmall = Integer.MAX_VALUE;
        int index_smallest = -1;
        int index_secsmall = -1;
        int k = costs[0].length;
        for(int i = costs.length-1;i>=0;i--){
            if(i == costs.length-1){
                for(int j = 0;j<k;j++){
                    if(costs[i][j]<smallest){
                        secsmall = smallest;
                        smallest = costs[i][j];
                        index_smallest = j;
                    }
                    else{
                        if(costs[i][j]<secsmall){
                            secsmall = costs[i][j];
                            index_secsmall = j;
                        }
                    }
                }
                continue;
            }
            int last_small = smallest;
            int last_small_index = index_smallest;
            int last_secsm = secsmall;
            int last_secsm_index = index_secsmall;
            smallest = Integer.MAX_VALUE;
            secsmall = Integer.MAX_VALUE;
            for(int j = 0;j<k;j++){
                int temp = costs[i][j];
                if(j!=last_small_index){
                    costs[i][j] = temp + last_small;
                }
                else{
                    costs[i][j] = temp + last_secsm;
                }
                if(costs[i][j]<smallest){
                    secsmall = smallest;
                    smallest = costs[i][j];
                    index_smallest = j;
                }   
                else{
                    if(costs[i][j]<secsmall){
                        secsmall = costs[i][j];
                        index_secsmall = j;
                    }
                }
            }
        }
        int mini = Integer.MAX_VALUE;
        for(int i = 0;i<k;i++){
            if(costs[0][i]<mini){
                mini = costs[0][i];
            }
        }
        return mini;    
    }
    }

Log in to reply
 

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