Home » Technical Interview Questions » Dynamic Programming Interview Questions » Maximum path sum in a triangle

Maximum path sum in a triangle


Reading Time - 5 mins


Difficulty Level Easy

Problem Statement

The problem “Maximum path sum in a triangle” states that you are given some integers. These integers are arranged in the form of a triangle. You are starting from the top of the triangle and need to reach the bottom row. For doing this, you move to the adjacent cells in the next row. So when you are moving down the triangle in the defined manner, what is the maximum sum you can achieve?

Example

Maximum path sum in a triangle

  1
 2 3
5 8 1
12

Explanation
You can simply move down the path in the following manner. 1-> 3-> 8, this path will make you attain a maximum sum that is 12.

Approach

So how do we solve the Maximum path sum in a triangle? Until now, we are pretty much familiar with these kinds of problems. Whenever we are provided with these kinds of problems. The brute force approach always is to first generate all the possible ways to reach your destination. And then keep on updating the answer for the optimal result, by calculating the sum for each path. But this approach is highly inefficient as this approach requires us to generate the paths. And we know that path generation is a task that has exponential time complexity which is not good.

So, to solve this we need to think of another approach. Then dynamic programming comes to our rescue. Because instead of generating the paths, if we could know somehow that what is the maximum that can be achieved from a cell to reach the bottom row. That way we can get the result for the cell which is adjacent to it but in the row above it. So, we use DP to solve the smaller subproblems. Then combining the results for those subproblems we find answers for the original problem.

READ  Binomial Coefficient

First, we fill the answer for the cells in the last row. We know that the maximum sum that can be achieved if we start from the cells at the bottom row is the number itself. After that, we move to the row above the bottom row. For each cell in the current row, we can choose the DP values of the cells which are adjacent to it in the row just below it. This way we keep on going in an upward direction. As we reach the top row, we are done with the problem.

C++ code to find Maximum path sum in a triangle

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){
  #include<bits/stdc++.h>
using namespace std;

int maximumPathSumInTriangle(vector<vector<int>> &input)
{
    int n = input.size();
    // start from row above bottom row
    // since the bottom row cells are the answers themselves
  for(int i=n-2;i>=0;i--)
  {
      // start from left to right in column
    for(int j=0;j<=i;j++)
    {
      if(input[i+1][j] > input[i+1][j+1])
        input[i][j] += input[i+1][j];
      else
        input[i][j] += input[i+1][j+1];
    }
  }
  return input[0][0];
}

int main()
{
    int n;cin>>n; // number of rows
    vector<vector<int>> input(n, vector<int>(n, 0));
    for(int i=0;i<n;i++){
        for(int j=0;j<=i;j++)
            cin>>input[i][j];
    }
    cout<<maximumPathSumInTriangle(input);
}

}
3
1
2 3
5 8 1
12

Java code to find Maximum path sum in a triangle

import java.util.*;

class Main{
  static int maximumPathSumInTriangle(int input[][], int n)
  {
      // start from row above bottom row
      // since the bottom row cells are the answers themselves
    for(int i=n-2;i>=0;i--)
    {
        // start from left to right in column
      for(int j=0;j<=i;j++)
      {
        if(input[i+1][j] > input[i+1][j+1])
          input[i][j] += input[i+1][j];
        else
          input[i][j] += input[i+1][j+1];
      }
    }
    return input[0][0];
  }

  public static void main(String[] args)
  {
    Scanner sc = new Scanner(System.in);
      int n = sc.nextInt(); // number of rows
      int input[][] = new int[n][n];
      for(int i=0;i<n;i++){
          for(int j=0;j<=i;j++)
              input[i][j] = sc.nextInt();
      }
      int answer = maximumPathSumInTriangle(input, n);
      System.out.print(answer);
  }
}
3
1
2 3
5 8 1
12

Complexity Analysis

Time Complexity

O(N^2), as we moved across each row and each column. In the process, we traveled to each cell. And since there were O(N^2) cells in the triangle and the transition for DP took only O(1) operation. Thus, the time complexity is also polynomial.

READ  How to print maximum number of A’s using given four keys

Space Complexity

O(N^2) since we created a 2D DP array. Thus the space complexity is also polynomial.

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions