C++ concise code, O(nk) time and O(1) space


  • 1
    class Solution {
    public:
        int minCostII(vector<vector<int>>& costs) {
            if(!costs.size() || !costs[0].size()) return 0;
            int min1 = 0, min2 = 0, arr_size = costs.size(), k = costs[0].size();
            for(int i = 0; i < arr_size; i++){
                int nm1 = INT_MAX, nm2 = INT_MAX;
                for(int j = 0; j < k; j++){
                    if (!i || costs[i-1][j] != min1) costs[i][j] += min1;
                    else costs[i][j] += min2;
                    
                    if(costs[i][j] < nm1) {nm2 = nm1; nm1 = costs[i][j];}
                    else if(costs[i][j] < nm2) nm2 = costs[i][j];
                }
                min1 = nm1, min2 = nm2;
            }
            return min1;
        }
    };
    

  • 0

    BTW, nm1, nm2 means new_minimum.


Log in to reply
 

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