InterviewBit Academy is now Scaler!
Learn Tech Skills from Scratch @ Scaler EDGE

Maximum Path in Triangle


Problem Description

Given a 2D integer array A of size N * N representing a triangle of numbers.

Find the maximum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

NOTE:

  • Adjacent cells to cell (i,j) are only (i+1,j) and (i+1,j+1)
  • Row i contains i integer and n-i zeroes for all i in [1,n] where zeroes represents empty cells.



Problem Constraints

0 <= N <= 1000

0 <= A[i][j] <= 1000



Input Format

First and only argument is an 2D integer array A of size N * N.



Output Format

Return a single integer denoting the maximum path sum from top to bottom in the triangle.



Example Input

Input 1:

 A = [
        [3, 0, 0, 0]
        [7, 4, 0, 0]
        [2, 4, 6, 0]
        [8, 5, 9, 3]
     ]

Input 2:

 A = [
        [8, 0, 0, 0]
        [4, 4, 0, 0]
        [2, 2, 6, 0]
        [1, 1, 1, 1]
     ]



Example Output

Output 1:

 23

Output 2:

 19



Example Explanation

Explanation 1:

 Given triangle looks like:  3
                             7 4
                             2 4 6
                             8 5 9 3
        So max path is (3 + 7 + 4 + 9) = 23

Explanation 1:

 Given triangle looks like:  8
                             4 4
                             2 2 6
                             1 1 1 1
        So max path is (8 + 4 + 6 + 1) = 19



NOTE: You only need to implement the given function. Do not read input, instead use the arguments to the function. Do not print the output, instead return values as specified. Still have a doubt? Checkout Sample Codes for more details.
Start solving Maximum Path in Triangle on Interview Code Editor
Hints
  • Hint 1
  • Solution Approach
  • Complete Solution
Asked In:

Discussion


Loading...
Click here to start solving coding interview questions