O(nk) solution


  • 0
    A

    For every house we only need to maintain first and second minimum value and their colours and not value for every colour. For next house if value if equal to first minimum colour we use second minimum and if not we use first minimum value .

    class Solution {
    public:
        int n,m;
    
        int minCostII(vector<vector<int>>& costs) {
            
            n = costs.size();
            
            if(n == 0)return 0;
            
            m = costs[0].size();
    
            int ans = INT_MAX;
            
            int fval,find,sval,sind; //first and second minimums and their colors
            
            find = -1;
            fval = 0;
            for(int i = 0;i<n;i++){
                int cfval,cfind,csval,csind; //current first and second minimums and colors
                cfval = INT_MAX;
                csval = INT_MAX;
                for(int j = 0;j<m;j++){   
                    int curr;
                    if(j  == find){
                        curr = sval + costs[i][j];
                    } else {
                        curr = fval + costs[i][j];
                    }
                    
                    if( i == n-1)ans = min(ans,curr);
                    if(curr < cfval){
                        csval = cfval;
                        csind = cfind;
                        cfval = curr;
                        cfind = j;
                    } 
                    else if(curr < csval){
                        csval = curr;
                        csind = j;
                    }
                }
                fval = cfval;
                find = cfind;
                sval = csval;
                sind = csind;
            }
            
            return ans;
        }
    };
    

Log in to reply
 

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