C++_Accepted_16ms_Time: O(n*k) without extra space


  • 1

    /What I mean without extra space does not include costs this vector./

    The idea is the same as Pain House I, but we can reduce the time complexity from O(nk^2) to O(nk).
    We can see that each time we add some value to costs[i][j] from costs[i-1][j], we traverse costs[i-1][j], but we can just find the smallest and second smallest value in costs[i-1][j] by using O(n) time, and then if costs[i-1][j] != min1(the smallest number), we can just directly add it to cost[i][j], else we just add the second smallest number to cost[i][j]. Also at each loop, we also use two integer to record the smallest and second smallest number in our current vector, and then update min1 and min2 and go to the next row.

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

    0_1478995644962_79B49B57-2E62-400D-AD1C-0B565525E1EB.png


Log in to reply
 

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