Simple, fast, short, O(1) space, java solution with explanation - Beats 99.60% solutions


  • 0
    A

    This technique uses a recursive algorithm, much like the one used to find a path between 2 points in a two dimensional array.
    Basically, you recursively select the path that has the shorter sum at each step (which is stored in right and down). The first base case just returns the value in the bottom right spot when we reach there. The second base case will return Integer.MAX_VALUE when we go out of the grid so that we do not select this invalid path.

    Dynamic Programming
    Well, the above algorithm works, but without DP it's really slow. If you recursively think about it and imagine that you are at some spot (i, j) in the grid, you have already computed the path with the shortest sum till there. Instead of using another two dimensional array, I multiply the value in the original grid at (i, j) with -1. While recursively traversing, if I come across a value that is negative, I know that I have already computed the shortest path to this spot, which is simply -1 * value_at_spot

    Code

    public int minPathSum(int[][] grid) {
            return solve(grid, 0, 0);
    }
        
        private int solve(int[][] grid, int i, int j) {
            if (i == grid.length-1 && j == grid[0].length-1) 
                // base case 1
                return grid[i][j];
            if (i == grid.length || j == grid[0].length) { 
                // base case 2 (invalid spot)
                return Integer.MAX_VALUE;
            }
            if (grid[i][j] < 0)
                return -1*grid[i][j]; // DP - already have lowest sum path
            int right = solve(grid, i, j+1);
            int down = solve(grid, i+1, j);
            
            if (right < down) {
                grid[i][j] = -1* (grid[i][j] + right);
            }
            else {
                grid[i][j] = -1* (grid[i][j] + down);
            }
            return -1 * grid[i][j];
        }
    

Log in to reply
 

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