FastPrepTriangle Minimum Path Sum
Problems/Triangle Minimum Path Sum

Triangle Minimum Path Sum

Expedia logoExpedia● MediumNEW GRADONSITE INTERVIEW

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: The report's goal of the smallest path sum through a triangle is kept. We chose that moves go to adjacent items in the next row, the limits, and that values can be negative. Our version is about 95% the same as the reported question.

Starting at the top of triangle, move to the next row at the same column or one column to the right. Return the smallest possible sum from the top through the last row, including both endpoints.

Row r has r+1 entries, with rows and columns indexed from 0. Values may be negative.

Function

minimumTrianglePath(triangle: int[][]) → int

Examples

Example 1

triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]return = 11

The path 2→3→5→1 has sum 11.

Example 2

triangle = [[-10]]return = -10

The only entry is the entire path.

Constraints

  • 1 <= triangle.length <= 100.
  • -1000 <= triangle[r][c] <= 1000.
  • Row r has exactly r+1 entries.

More Expedia Onsite Interview questions

  • Scramble StringONSITE INTERVIEW · Seen Sep 2026
  • Smallest Sufficient TeamONSITE INTERVIEW · Seen Sep 2026
  • Check Anagram Pairs Index by IndexONSITE INTERVIEW · Seen Oct 2025
  • Fresh Oranges Left After Rotting StopsONSITE INTERVIEW · Seen Oct 2025
  • Longest Increasing SubsequenceONSITE INTERVIEW · Seen Oct 2025
  • Lowest Common Ancestor with Repeated and Missing ValuesONSITE INTERVIEW · Seen Oct 2025
  • Shortest Substring with Exactly K OnesONSITE INTERVIEW · Seen Oct 2025
  • Middle Element of a Linked ListONSITE INTERVIEW · Seen Nov 2024
  • Minimum in a Rotated Sorted ArrayONSITE INTERVIEW · Seen Sep 2024
  • Mirror Image Binary TreesONSITE INTERVIEW · Seen Sep 2024

Similar questions at other companies

  • Count Subsets With a Target SumSafe Security · ONSITE INTERVIEW
  • 0/1 Knapsack with Weight and Volume LimitsGoogle · ONSITE INTERVIEWGoogle interview questions
  • Maximum Subarray Sum with One DeletionOracle · ONSITE INTERVIEWOracle interview questions
  • Best Time to Buy and Sell Stock IIKotak Mahindra Bank · ONSITE INTERVIEWKotak Mahindra Bank interview questions
  • Coin ChangeMicrosoft · ONSITE INTERVIEWMicrosoft interview questions
  • Word BreakAmazon · PHONE SCREEN · ONSITE INTERVIEW
  • Maximum SubarrayUpstart · ONSITE INTERVIEWUpstart interview questions
  • Maximum Product SubarrayHartford Financial Services · ONSITE INTERVIEWHartford Financial Services interview questions
  • Word BreakMoveworks · ONSITE INTERVIEWMoveworks interview questions
  • Maximum Value from Circular HousesDigitalOcean · ONSITE INTERVIEWDigitalOcean interview questions

Interview reports that mention this question

  • Expedia New Grad SDE Interviews: 20 Experiences (Part 1 of 3)

Expedia interview experiences

  • Expedia Intern Final Round in 2021: 28 Experiences (Part 4 of 6)
  • Expedia Intern Finals Before 2020: 14 Experiences (Part 6 of 6)
  • Expedia Intern Final Round in 2020: 24 Experiences (Part 5 of 6)
  • Expedia Intern Final Round in 2022: 15 Experiences (Part 3 of 6)
  • Expedia Intern Final Round in 2023: 17 Experiences (Part 2 of 6)
All Expedia interview questionsSee Expedia hiring insights
Saved
class Solution {
    public int minimumTrianglePath(int[][] triangle) {
        // Write your code here.
    }

}
Checking account…