Grid — Max Path Sum — Dynamic Programming

Problem Statement :

Write a function, maxPathSum, that takes in a grid as an argument. The function should return the maximum sum possible by traveling a path from the top-left corner to the bottom-right corner. You may only travel through the grid by moving down or right.

You can assume that all numbers are non-negative.

E.g :

{ 
  { 1,3,12 },
  { 5,1, 1 }, 
  { 3,6, 1 }
};
Output = 18

This is similar to our previous grid problem — Grid Problem

First we need to check if we can visualize the problem in to a recursion tree.

The problem is similar to grid traveller problem except we need to calculate the maximum path sum from 0,0 to 2,2.

The formula can be derived as

currentNode value + max(leftSum,rightSum)

Java Program

public class Solution {
   public static void main(String args[]) {
      int[][] grid1 = { { 1, 3, 12 }, { 5, 1, 1 }, { 3, 6, 1 } };
      int[][] grid2 = { { 1, 2, 8, 1 }, { 3, 1, 12, 10 }, { 4, 0, 6, 3 } };
      int[][] grid3 = { { 1, 1, 3, 1, 1, 1, 1, 4, 1, 1, 1, 1, 1 }, { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
{ 1, 2, 1, 1, 6, 1, 1, 5, 1, 1, 0, 0, 1 }, { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
{ 1, 1, 1, 5, 1, 1, 1, 1, 0, 1, 1, 1, 1 }, { 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
{ 2, 1, 1, 1, 1, 8, 1, 1, 1, 1, 1, 1, 1 }, { 2, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }, { 1, 1, 1, 1, 1, 1, 1, 9, 1, 1, 1, 1, 1 },
{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }, { 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 8, 1, 1, 1 }, { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 } };
  
      //Test case 1
      Instant start = Instant.now();
      int maxPathSum = new Solution().maxPathSum(grid1);
      Instant finish = Instant.now();
      long timeElapsed = Duration.between(start, finish).toMillis();
      System.out.print("Maximum path sum = " + maxPathSum);
      System.out.print(",Total time taken = " + timeElapsed);
      System.out.println();
      //Test case 2
      start = Instant.now();
      maxPathSum = new Solution().maxPathSum(grid2);
      finish = Instant.now();
      timeElapsed = Duration.between(start, finish).toMillis();
      System.out.print("Maximum path sum = " + maxPathSum);
      System.out.print(",Total time taken = " + timeElapsed);
      System.out.println();
      
      //Test case 3
      start = Instant.now();
      maxPathSum = new Solution().maxPathSum(grid3);
      finish = Instant.now();
      timeElapsed = Duration.between(start, finish).toMillis();
      System.out.print("Maximum path sum = " + maxPathSum);
      System.out.print(",Total time taken = " + timeElapsed);
      System.out.println();
   }
   private int maxPathSum(int[][] grid) {
      return maxPathSum(0, 0, grid.length, grid[0].length, grid);
   }
   private int maxPathSum(int row, int column, int rowLength, int columnLength, int[][] grid) {
      if (row > rowLength - 1 || column > columnLength - 1) {
         return Integer.MIN_VALUE;
      }
      if (row == rowLength - 1 && column == columnLength - 1) {
         return grid[row][column];
      }
      int downMaxPathSum = maxPathSum(row + 1, column, rowLength, columnLength, grid);
      int rightMaxPathSum = maxPathSum(row, column + 1, rowLength, columnLength, grid);
      int result = grid[row][column] + Math.max(downMaxPathSum, rightMaxPathSum);
      return result;
   }
}

Output :

Maximum path sum = 18,Total time taken = 0
Maximum path sum = 36,Total time taken = 0
Maximum path sum = 56,Total time taken = 2481

Time Complexity — O(2^(m+n)) where m is the number of rows and n is the number of columns.

Space Complexity. — O(m+n)

Question : In recursive flow, do you see any repeating sub problems?

We can look at the tree again,

1. If we look at the tree, there are duplicate subproblems such as node (1,1)
2. We can cache the pathSum for each node using a hashing data structure

Enhanced Java Solution using Memoization

public class Solution {
    public static void main(String args[]) {
      int[][] grid1 = { { 1, 3, 12 }, { 5, 1, 1 }, { 3, 6, 1 } };
      int[][] grid2 = { { 1, 2, 8, 1 }, { 3, 1, 12, 10 }, { 4, 0, 6, 3 } };
      int[][] grid3 = { { 1, 1, 3, 1, 1, 1, 1, 4, 1, 1, 1, 1, 1 }, { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
{ 1, 2, 1, 1, 6, 1, 1, 5, 1, 1, 0, 0, 1 }, { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
{ 1, 1, 1, 5, 1, 1, 1, 1, 0, 1, 1, 1, 1 }, { 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
{ 2, 1, 1, 1, 1, 8, 1, 1, 1, 1, 1, 1, 1 }, { 2, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }, { 1, 1, 1, 1, 1, 1, 1, 9, 1, 1, 1, 1, 1 },
{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }, { 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 8, 1, 1, 1 }, { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 } };
  
      //Test case 1
      Instant start = Instant.now();
      int maxPathSum = new Solution().maxPathSum(grid1);
      Instant finish = Instant.now();
      long timeElapsed = Duration.between(start, finish).toMillis();
      System.out.print("Maximum path sum = " + maxPathSum);
      System.out.print(",Total time taken = " + timeElapsed);
      System.out.println();
      //Test case 2
      start = Instant.now();
      maxPathSum = new Solution().maxPathSum(grid2);
      finish = Instant.now();
      timeElapsed = Duration.between(start, finish).toMillis();
      System.out.print("Maximum path sum = " + maxPathSum);
      System.out.print(",Total time taken = " + timeElapsed);
      System.out.println();
      
      //Test case 3
      start = Instant.now();
      maxPathSum = new Solution().maxPathSum(grid3);
      finish = Instant.now();
      timeElapsed = Duration.between(start, finish).toMillis();
      System.out.print("Maximum path sum = " + maxPathSum);
      System.out.print(",Total time taken = " + timeElapsed);
      System.out.println();
   }
   private int maxPathSum(int[][] grid) {
      Map<String,Integer> memo = new HashMap<>();
      return maxPathSum(0, 0, grid.length, grid[0].length, grid,memo);
   }
private int maxPathSum(int row, int column, int rowLength, int columnLength, int[][] grid,Map<String,Integer> memo) {
      String key = row+","+column;
      if(memo.containsKey(key)){
         return memo.get(key);
      }
      if (row > rowLength - 1 || column > columnLength - 1) {
         return Integer.MIN_VALUE;
      }
      if (row == rowLength - 1 && column == columnLength - 1) {
         return grid[row][column];
      }
      int downMaxPathSum = maxPathSum(row + 1, column, rowLength, columnLength, grid,memo);
      int rightMaxPathSum = maxPathSum(row, column + 1, rowLength, columnLength, grid,memo);
      int result = grid[row][column] + Math.max(downMaxPathSum, rightMaxPathSum);
      memo.put(key,result);
      return result;
   }
}

Output :

Maximum path sum = 18,Total time taken = 0
Maximum path sum = 36,Total time taken = 0
Maximum path sum = 56,Total time taken = 1

Time Complexity: O(m*n)

Space Complexity:O(m*n)

How the time complexity changed to O(m*n) ?

Lets reconsider the recursion tree and apply memoization

If you consider the number nodes, we are reducing the number of execution to (rows*columns) times from O(2^(m+n))

Happy Coding

Enjoy!!!