Passed c++ code, only need O(n) extra space and don't change the original data

  • 7
    int minPathSum(vector<vector<int> > &grid) {
        int rows = grid.size();
        if (rows==0) return 0;
        int cols = grid[0].size();
        vector<int> vi(cols, INT_MAX);
        int i, j;
        vi[0] = 0;
        for (i=0; i<rows; i++) {
            vi[0] += grid[i][0];
            for (j=1; j<cols; j++) {
                vi[j] = min(vi[j-1], vi[j])+grid[i][j];
        return vi[cols-1];

  • 0

    How can we modify this code if we are allowed to move in diagonal direction also ?

Log in to reply

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