C++ O(1) space, O(mn) time 7 lines, EASY, STRAIGHT, and SIMPLE


  • 1
    T
    int minPathSum(vector<vector<int>>& grid) {
        if(grid.size() == 0 || grid[0].size() == 0) return 0;
        
        for(int v = 1; v < grid.size(); v++) grid[v][0] += grid[v-1][0];
        for(int h = 1; h < grid[0].size(); h++) grid[0][h] += grid[0][h-1];
        
        for(int v = 1; v < grid.size(); v++)
            for(int h = 1; h < grid[0].size(); h++)
                grid[v][h] += min(grid[v-1][h],grid[v][h-1]);
    
        return grid.back().back();
    }

Log in to reply
 

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