AC Java solution without extra space


  • 94

    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];
    }

  • 0
    I

    Why do you need last1 and last2 variables?


  • 1
    L

    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.


  • 0
    E
    This post is deleted!

  • 15

    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).


  • 0
    N

    said in AC Java solution without extra space:

    // 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.


  • 2
    Y

    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.


  • 5
    N

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


  • 0
    G

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


  • 0
    X

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


  • 2

    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.


  • 8

    Java n * k * k 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 n * k 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]; 
    
     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(last1 == -1) dp[i][j] = costs[i][j];  
         else if(j == last1) dp[i][j] = dp[i - 1][last2] + costs[i][j];
         else dp[i][j] = dp[i - 1][last1] + costs[i][j];
         
         if(min1 == -1 || dp[i][j] < dp[i][min1]){
           min2 = min1;
           min1 = j;
         } else if(min2 == -1 || dp[i][j] < dp[i][min2]){
           min2 = j;     
         }
       }
     }
     
     return dp[n - 1][min1];
    }

  • 0
    C

    @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


  • 0

    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];
    }

  • 0

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

  • 0
    B

    @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;

Log in to reply
 

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