Finding the optimal path in a grid

Question

Background I had an interview today and I was asked the following question.

You are given a grid.

  int [][] grid =
                {
                {0,0,0,2,5},
                {0,0,0,1,5},
                {0,1,1,1,1},
                {2,0,0,0,0}
                };

You start from the bottom left off the grid. You can only go up and right. The idea is to get to the TOP right corner. You are to take the path that will get you the most Value.

The output for the above would be 16

My solution

public static int getPathMaxSum(int [][] grid){
    int row = grid.length-1;
    int col = 0;
    int currentSum = grid[row][col];
    return getMax(grid,currentSum,row,col);
}

public static int getMax(int [][] grid,int sum,int row,int col){
    if((isTopRight(grid,row,col)) || (!isValid(grid,row,col))){
        return sum;
    }else{
        sum = sum + grid[row][col];
        return Math.max(getMax(grid,sum,row-1,col),getMax(grid,sum,row,col+1));
    }
}

public static boolean isTopRight(int [][] grid, int row, int col){
    return row == 0 && col == grid[row].length-1;
}

public static boolean isValid(int [][] grid, int row, int col){
    return (row >= 0 &&  row < grid.length) && (col >= 0 && col < grid[row].length);
}

I am trying to solve this recursively. I figure that i have 2 possible choices to make at every position and i want to get the max of the two choices but for some reason I am not able to get the correct output.

I have two helper functions that check if my position is valid meaning inside the grid and also if i have hit the top right and if i have then i hit my base case.

I would love inputs to see where i went wrong.

Answer 1

You don't need a sum parameter in your method.

I assume you already understand how recursion-topdown approach for this problem. But again just for the sake of completeness, the basic formula is:

You start with a cell at row, col get its value and then either you look to UP (row-1, col) or RIGHT (row, col+1).

So the result is going to be:

grid[row][col] + Math.max( getMax( row-1, col, grid ), getMax( row, col+1, grid ) )

Base conditions:

a) If it is top right i.e. the destination, you don't need to recurse you just return the value at that cell.

b) If it is an invalid cell like you have written in your isValid method, you need to return Integer.MIN_VALUE because you could have a negative value in your other cells and you want them to be maximum.

So your getMax function needs to be:

public static int getMax(int [][] grid,int row,int col){
    if (isTopRight(grid,row,col)) {
       return grid[row][col];
    } else if (!isValid(grid,row,col)){
        return Integer.MIN_VALUE;
    } else {
        return grid[row][col] + Math.max(getMax(grid,row-1,col),getMax(grid,row,col+1));
    }
}

You can see working example here

Answer 2

EDIT: Answer to the edited version of your code

Issues with your new solution:

1. int currentSum = grid[row][col]; and sum = sum + grid[row][col];

   The sum is initialized with the value in the bottom left corner and in the initial call of getMax() the same value is added again. This is not what it should be like. Just start the sum with 0, adding will be done by getMax().

2. if((isTopRight(grid,row,col)) || (!isValid(grid,row,col))) then return sum;

   For invalid positions this will work (see restrictions below my code), but not for the top right corner (since we haven't added the value of the corner yet). Thus pull the two conditions apart and only return directly on invalid positions. On any other position first add the value and then, if you reached the "goal", return the sum. Otherwise return the maximum of "going right" and "going up" (the recursive call is correct now).

Fixing these issues and implementing your example, I derived the following code:

public class Pathfinder {

    public static void main(String... args) {
        int [][] grid = {
            {0,0,0,2,5},
            {0,0,0,1,5},
            {0,1,1,1,1},
            {2,0,0,0,0}
        };
        
        System.out.println(getPathMaxSum(grid));
    }

    public static int getPathMaxSum(int[][] grid) {
        int row = grid.length - 1;
        int col = 0;
        
        return getMax(grid, 0, row, col);
    }

    public static int getMax(int[][] grid, int sum, int row, int col) {
        if(!isValid(grid, row, col))
            return sum;
        
        sum = sum + grid[row][col];
        
        if(isTopRight(grid, row, col))
            return sum;
        
        return Math.max(getMax(grid, sum, row - 1, col), getMax(grid, sum, row, col + 1));
    }

    public static boolean isTopRight(int[][] grid, int row, int col) {
        return row == 0 && col == grid[row].length - 1;
    }

    public static boolean isValid(int[][] grid, int row, int col) {
        return (row >= 0 &&  row < grid.length) && (col >= 0 && col < grid[row].length);
    }
}

Note, that this version will work for any grid (as long as the stack is big enough and we are not dealing with too large numbers, e.g. we won't get any integer overflow) if all entries are non-negative. Anyways, a grid with negative entries can be manipulated in such a way, that the best path will be found by this algorithm and the solution can be easily "translated" back to the original grid (just subtract the smallest value from every entry).

ANSWER TO THE ORIGINAL CODE

I see multiple issues with your code:

1. isValid(grid,row+1,col) and sum1 = grid[row+1][col];

   You are trying to add 1 to the row, but you started (correctly) with int row = grid.length-1;. Adding 1 will give you an invalid position, thus the first branch will never be executed. Instead, you will need to subtract 1 from the row to "go up".

2. sum = sum + Math.max(sum1,sum2);

   This changes sum, but you cannot see, in which direction you moved. And directly afterwards ...

3. getMax(grid,sum,row+1,col); and getMax(grid,sum,row,col+1);

   ... you do the recursive calls with the new, maximum sum, but from both spots. To get a correct solution, you should call them with the value, their direction represents. Note also, that row+1 needs to be replaced by row-1 here as well.

4. return sum;

   You now return this maximum sum, but completely ignoring the returns of your recursive calls. You should instead compare their returns and return yourself the higher value of both.

5. Bactracking vs. Dynamic Programming

   Your algorithm should work in general and is sufficient for small instances of the problem, but not for bigger ones (since it will make 2 recursive calls for every step and you have 2*(n-1) steps.. resulting in exponential runtime). An alternative approach with quadratic runtime would be to go backwards through the field and choose the best way by looking just one field right or up and adding the value of the current field to the maximum of this. Just start in the top right corner and go left, row by row from right to left.