How do I find the maximum path sum with path indication?

Question

I have to find the maximum path sum starting from top right to bottom left of the matrix.

Therefore this is what I was asked to do:

• Given an mxn grid filled with numbers, find a path from top left to bottom right, which maximizes the sum of all numbers along its path, also i can only move either down or right.

So I had this on a coding interview recently and I passed it, but in the middle of the interview the guy asked me to also show the path along with the result

Example:

grid = [[1,10]
       ,[2,3]]

output: 14, right,down

So I came up with a solution:

    function matrix(grid) {
    var m = grid.length;
    var n = grid[0].length;

    if(!m || !n) return grid;

    for (let i = 0; i < m; i++){
        for (let j = 0; j < n; j++){
            // grid[0][0] itself contains the min path sum
            if (i === 0 && j === 0) continue;
            // first row: grid[i][j] = previous grid(left) + current value
            if (i === 0) grid[i][j] += grid[i][j-1];
            // first column: grid[i][j] = previous grid(top) + current value
            else if (j === 0) grid[i][j] += grid[i-1][j];
            // grid[i][j] = get the min of previous grid(top/left) + current value
            else grid[i][j] += Math.max(grid[i][j - 1], grid[i - 1][j]);
        }
    };
    return grid[n - 1][m - 1];
};

const grid = [[1,10],[2,3]];           

console.log(matrix(grid));

What I tried during the interview was to add the given grid and the result of the maximum numbers on each step on a variable each and then try to subtract the numbers that was calculated in the la line on my 2nd for loop compare it with the number in the original grid and if it match then push 'down' or 'right' to an empty array and then simply return the result and the array.

Example:

grid = [[1,10]
       ,[2,3]]

oldGrid = grid

arr == []

loop
on each iteration

grid[1] - oldGrid[1] = oldgrid[0]
                                   {for rows}
add "right" to arr

or 

grid[2] - oldgrid[2] = oldgrid[0]
                                   {for cols}
add "down" to arr

return result and arr

so this is what i've come up with

    function matrix(grid) {
    var m = grid.length;
    var n = grid[0].length;
    var showDir = [];

    if(!m || !n) return grid;

    for (let i = 0; i < m; i++){
        for (let j = 0; j < n; j++){
            // grid[0][0] itself contains the min path sum
            if (i === 0 && j === 0) continue;
            // first row: grid[i][j] = previous grid(left) + current value
            if (i === 0) grid[i][j] += grid[i][j-1];
            // first column: grid[i][j] = previous grid(top) + current value
            else if (j === 0) grid[i][j] += grid[i-1][j];
            // grid[i][j] = get the min of previous grid(top/left) + current value
            else{
                let direction, max;
                if(grid[i][j-1]>grid[i-1][j]){
                    direction = "R"
                    max = grid[i][j-1]
                    showDir.push(direction)
                }
                else{
                    direction = "D"
                    max = grid[i-1][j]
                    showDir.push(direction)
                }
                grid[i][j] += max;
            } 
        };
    };
    return grid[n - 1][m - 1], showDir
};

    const grid = [[1,10],[2,3]];           

    console.log(matrix(grid));

the thing is with this it only output showDir not the grid and i don't know why

I'm new to Javascript so please go easy on me

Answer 1

You could iterate the diagonals and take the maximum value of either the upper item or the right one.

The final result is in bottom left item.

To get a path, you start from the end and choose the item with the next larger sum and take this position for the result set and get the next larger item's position until you reach the start item.

const
    exist = (i, j) => i >= 0 && i < size[0] && j >= 0 && j < size[1],
    array = [[1, 3, 4, 2, 5], [2, 4, 1, 7, 6], [9, 4, 1, 2, 1], [3, 5, 1, 1, 2], [3, 3, 7, 1, 4]],
    size = [array.length, array[0].length],
    sums = [],
    path = [];

// get sums
for (let k = 0, l = size[0] + size[1] - 1; k < l; k++) {
    let i = Math.min(k, size[0] - 1),
        j = k - i;

    while (exist(i, j)) {
        sums[i] ??= [];
        sums[i][j] = array[i][j] + Math.max(sums[i - 1]?.[j] || 0, sums[i][j - 1] || 0);
        i--; j++;
    }
}

// get path from max to start value
let i = size[0] - 1,
    j = size[1] - 1;

path.push([i, j]);
while (i || j) {
    if (!exist(i - 1, j) || exist(i, j - 1) && sums[i - 1][j] < sums[i][j - 1]) j--;
    else i--;
    path.unshift([i, j]);
}

path.forEach(([i, j]) => console.log(i, j, '->', sums[i][j]));
console.log('');
sums.forEach(a => console.log(...a.map(v => v.toString().padStart(3, ' '))));

.as-console-wrapper { max-height: 100% !important; top: 0; }

Answer 2

My approach is to build up a new grid with values such as {value: 56, path:["right", "down", "right", "down"]}, by iterating over the rows and columns and calculating each according to the one above it and the one to the left of it, if they exist, turning this:

[
  [1, 10, 7],
  [2, 30, 9],
  [25, 2, 6]
]

into something like this:

[
  [{value: 1,  path: []},   {value: 11, path: [?]},   {value: 18, path: [??]}]
  [{value: 3,  path: [?]},  {value: 41, path: [??]},  {value: 50, path: [???]}]
  [{value: 28, path: [??]}, {value: 43, path: [???]}, {value: 56, path: [????]}]
]

(with the strings "right" and "down" replaced by arrows for simpler display) and then simply reading off the bottom-right value.

Here is some code doing that with a double-reduce to iterate the rows and then the cells within those rows:

const maxPath = (grid) => grid .reduce ((rs, r, j) => [...rs, r .reduce ((cs, c, i, _, 
  above = j > 0 && rs [j - 1] [i],
  left = i > 0 && cs [i - 1]
) => [
  ... cs, 
  above && (!left || above .value > left .value)
    ? {value: above .value + c, path: [... above .path, 'down']}
  : left && (!above || left .value >= above .value)
    ? {value: left .value + c, path: [... left .path, 'right']}
  : {value: c, path: []}
], [])], []) [grid .length - 1] [grid [0] .length - 1]

console .log (maxPath ([
  [1, 10, 7],
  [2, 30, 9],
  [25, 2, 6]
]))

The conditions in that version are a little complex. I started with this version:

const maxPath = (grid) => grid .reduce ((rs, r, j) => [...rs, r .reduce ((cs, c, i, _, 
  above = j > 0 && rs [j - 1] [i],
  left = i > 0 && cs [i - 1]
) => [
  ... cs, 
  above && left 
    ? above .value > left .value
      ? {value: above .value + c, path: [... above .path, 'down']}
      : {value: left .value + c, path: [... left .path, 'right']}
  : above
    ? {value: above .value + c, path: [... above .path, 'down']}
  : left
    ? {value: left .value + c, path: [... left .path, 'right']}
  : {value: c, path: []}
], [])], []) [grid .length - 1] [grid [0] .length - 1]

and then combined those conditions which led to the same result.