C++ 8ms solution, O(nk) time, O(k) space


  • 0
    H
    int minCostII(vector<vector<int>>& costs) {
        int n = costs.size();
        if (n == 0)
            return 0;
        int k = costs[0].size(); // num of colors
        vector<int> c(k, 0);
        int min1_c = INT_MAX, min2_c = INT_MAX;
    
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < k; j++) {
                if(c[j] == min1_c)
                    c[j] = (i == 0) ? costs[0][j] : min2_c + costs[i][j];
                else
                    c[j] = (i == 0) ? costs[0][j] : min1_c + costs[i][j];
            }
            min1_c = INT_MAX, min2_c = INT_MAX;
            for(auto t : c) {
                if(t < min1_c) {
                    min2_c = min1_c;
                    min1_c = t;
                } else if (t < min2_c) {
                    min2_c = t;
                }
            }
        }
        
        return min1_c;
    }

Log in to reply
 

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