# Java O(nk) 6ms solution with explanation

• 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;
}
}``````

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