# AC Java solution without extra space

• The idea is similar to the problem Paint House I, for each house and each color, the minimum cost of painting the house with that color should be the minimum cost of painting previous houses, and make sure the previous house doesn't paint with the same color.

We can use min1 and min2 to track the indices of the 1st and 2nd smallest cost till previous house, if the current color's index is same as min1, then we have to go with min2, otherwise we can safely go with min1.

The code below modifies the value of costs[][] so we don't need extra space.

``````public int minCostII(int[][] costs) {
if (costs == null || costs.length == 0) return 0;

int n = costs.length, k = costs[0].length;
// min1 is the index of the 1st-smallest cost till previous house
// min2 is the index of the 2nd-smallest cost till previous house
int min1 = -1, min2 = -1;

for (int i = 0; i < n; i++) {
int last1 = min1, last2 = min2;
min1 = -1; min2 = -1;

for (int j = 0; j < k; j++) {
if (j != last1) {
// current color j is different to last min1
costs[i][j] += last1 < 0 ? 0 : costs[i - 1][last1];
} else {
costs[i][j] += last2 < 0 ? 0 : costs[i - 1][last2];
}

// find the indices of 1st and 2nd smallest cost of painting current house i
if (min1 < 0 || costs[i][j] < costs[i][min1]) {
min2 = min1; min1 = j;
} else if (min2 < 0 || costs[i][j] < costs[i][min2]) {
min2 = j;
}
}
}

return costs[n - 1][min1];
}``````

• Why do you need last1 and last2 variables?

• For each row, you need last1 and last2 to keep track of the least and second least costs of previous row, while min1 min2 to get the least and second least values of current row.

• This post is deleted!

• You are directly changing the `costs` matrix in place. That usually is not a good idea. It's better to use a new matrix (the new matrix only need two rows in this case).

• // find the indices of 1st and 2nd smallest cost of painting current house i
if (min1 < 0 || costs[i][j] < costs[i][min1]) {
min2 = min1; min1 = j;
} else if (min2 < 0 || costs[i][j] < costs[i][min2]) {
min2 = j;
}

This logic to find the subMIN and MIN is really good, I used a heap to achieve this which is not better than this but it's easier to think.

• I think intently modified parameter is very very bad idea regarding to OOD and professional development. You shouldn't do this within your professional work.

• Just let you that, modify the parameter is a very very bad practice. An experienced programmer won't do that.

• If not particularly specify that the input can be modified, I think taking advantages of the input can be considered as using extra space.

• When last and current are in same color. why do you go for last2+min1 without checking last1+min2?

• Here is what I thought.

1. Each iteration, we store the `min` value and the `second min` value at each round.
2. When comes to the `ith` house, we pick the `last min` value from `i - 1th` hosue and add `all` the new color cost `except` the `same` color with `i - 1th min`. We can also think reverse, for all the new color cost, we want add the `min` from previous to them so that we can get new min. The same color one's optimal is also `min` but sadly we couldn't choose.
3. For that `same` color one, the `best` we can get is to pick the `last second min` value from `i - 1th` house.
4. So in this way, we have `all new k potential costs` for `ith` house then we store the `min` and the `second min` and go to the `next i + 1th` house. which is back to step 1.

Because at `each` house we choose the min value, so at the end, we have the `total` min value. Original problem optimized solution is based the sub problems optimized solutions. The value is updated after each house. Some simple examples will eliminate some concerns.

• Java O(n * k * k) time, O(n * k) space solution:

``````public int minCostII(int[][] costs) {
if(costs.length == 0) return 0;
int n = costs.length, k = costs[0].length;
int[][] dp = new int[n][k];
for(int i = 0; i < k; i++){
dp[0][i] = costs[0][i];
}

for(int i = 1; i < n; i++){
for(int j = 0; j < k; j++){
dp[i][j] = Integer.MAX_VALUE;
for(int s = 0; s < k; s++){
if(s == j) continue;
dp[i][j] = Math.min(dp[i][j], dp[i - 1][s] + costs[i][j]);
}
}
}

int res = Integer.MAX_VALUE;
for(int i = 0; i < k; i++){
res = Math.min(res, dp[n - 1][i]);
}
return res;
}

``````

Java O(n * k) time, O(1) space, without modify `costs` array solution.
We record the `min1 value` and `min1 index`, if `j == min1index` use `min2`.

``````//There are a row of n houses, each house can be painted with one of the k colors

class Solution {
public int minCostII(int[][] costs) {
int n = costs.length;
if(n == 0) return 0;
int k = costs[0].length;
int min1 = Integer.MAX_VALUE, min2 = Integer.MAX_VALUE;
int min1index = -1;
for(int i = 0;  i < k; i++){
if(costs[0][i] < min1 ){
min1index = i;
min2 = min1;
min1 = costs[0][i];
} else if(costs[0][i] < min2) {
min2 = costs[0][i];
}
}

for(int i = 1; i < n; i++){
int temp1 = min1, temp2 = min2, tempindex = min1index;
min1 = Integer.MAX_VALUE;
min2 = Integer.MAX_VALUE;

for(int j = 0; j < k; j++){
int val = 0;
if(j != tempindex){
val = temp1 + costs[i][j];
} else {
val = temp2 + costs[i][j];
}

if(val < min1){
min1index = j;
min2 = min1;
min1 = val;
} else if(val < min2){
min2 = val;
}
}
}

return min1;
}
}``````

• @Yunwei_Qiu To be honest, do not be picky. It is an algorithm interview question, not a design question, the interviewer will care about design when asking an OO design question

• Same idea：

``````public int minCostII(int[][] costs) {
if(costs.length==0) return 0;
int min1Color = -1,min2Color = -1;
for(int i = 0; i<costs.length; i++){
int lastmin1Color = min1Color, lastmin2Color = min2Color;
int min1 = Integer.MAX_VALUE, min2 = Integer.MAX_VALUE;
for(int color = 0; color < costs[0].length; color++){
//Update costs[i][color] using the previous min cost: lastmin1Color or lastmin2Color
if(color!=lastmin1Color) costs[i][color] += lastmin1Color==-1?0:costs[i-1][lastmin1Color];
else costs[i][color] += lastmin2Color==-1?0:costs[i-1][lastmin2Color];
//Find the firt 2 minimum cost to paint house i, which are costs[i][min1Color] and costs[i][min2Color]
if(costs[i][color]<=min1){
min2=min1;
min2Color = min1Color;
min1=costs[i][color];
min1Color=color;
}
else if(costs[i][color]<=min2){
min2=costs[i][color];
min2Color = color;
}
}
}
return costs[costs.length - 1][min1Color];
}``````

• I think OP's solution is awesome and pretty clear to understand.
To avoid modifying the given parameter, we can apply greedy algorithm. That is, instead of recording min cost for painting each house on the given matrix, we can use two variables to record so far the total minimal cost `min1`, and the second total minimal cost `min2`.
For each house, we get the total cost and then immediately compare it with `curMin1` and `curMin2`, which are the variables representing temporary minimal cost in painting current house.
Then after trying all possible colors for the current house, we update our `min1` and `min2`.
Here is the code also inspird by the @yavinci post https://discuss.leetcode.com/topic/30659/easiest-o-1-space-java-solution

``````public int minCostII(int[][] costs) {
if (costs == null || costs.length == 0) return 0;
int n = costs.length, k = costs[0].length;
int min1 = 0, min2 = 0, minIndex = -1;
for (int i = 0; i < n; i++) {
int curMin1 = Integer.MAX_VALUE, curMin2 = Integer.MAX_VALUE, curMinIndex = 0;
for (int j = 0; j < k; j++) {
int cost = costs[i][j] + (j == minIndex ? min2 : min1);
if (cost < curMin1) {
curMin2 = curMin1;
curMin1 = cost;
curMinIndex = j;
}
else if (cost < curMin2) curMin2 = cost;
}
min1 = curMin1;
min2 = curMin2;
minIndex = curMinIndex;
}
return min1;
}
``````

• @Jerry why set the third line -1? what't the purpose of it?

• for(int i = 0; i < n; i++){
int last1 = min1, last2 = min2;
min1 = -1; min2 = -1;

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