Problem Statement: Triangle
Given a triangle represented as a 2D array of integers, where each row in the triangle contains one more number than the previous row, find the minimum path sum from the top to the bottom. Each step you may move to an adjacent number in the row directly below, i.e., from triangle[i][j] to triangle[i+1][j] or triangle[i+1][j+1].
For example:
2
3 4
6 5 7
4 1 8 3
The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).
Approach
This problem can be solved using Dynamic Programming. The key idea is to start from the bottom of the triangle and work upwards, updating each element in the triangle with the minimum path sum from that element to the bottom.
- Dynamic Programming Approach:
- We modify the triangle itself to store the minimum path sum at each position.
- Starting from the second-last row, for each element in the row, we calculate the minimum of the two adjacent elements in the row directly below and add the current element’s value.
- Continue this process until we reach the top of the triangle, and the element at the top will contain the minimum path sum.
- Time Complexity:
- O(n) where
nis the number of rows in the triangle because we are processing each element once.
- O(n) where
- Space Complexity:
- O(1) if we modify the triangle in place, or O(n) if we use extra space for storing results (which is not needed here).
Example
For the triangle:
2
3 4
6 5 7
4 1 8 3
We start from the bottom:
- Row 3:
[4, 1, 8, 3]- No change needed as this is the base row.
- Row 2:
[6, 5, 7]6 = 6 + min(4, 1) = 6 + 1 = 75 = 5 + min(1, 8) = 5 + 1 = 67 = 7 + min(8, 3) = 7 + 3 = 10
- Row 1:
[3, 4]3 = 3 + min(7, 6) = 3 + 6 = 94 = 4 + min(6, 10) = 4 + 6 = 10
- Row 0:
[2]2 = 2 + min(9, 10) = 2 + 9 = 11
Thus, the minimum path sum is 11.
Code Implementations
C:
#include <stdio.h>
int minimumTotal(int** triangle, int numRows) {
// Start from the second last row and work upwards
for (int row = numRows - 2; row >= 0; row--) {
for (int col = 0; col <= row; col++) {
// Update the current element by adding the minimum of the two adjacent elements below it
triangle[row][col] += (triangle[row + 1][col] < triangle[row + 1][col + 1]) ?
triangle[row + 1][col] : triangle[row + 1][col + 1];
}
}
// The top element now contains the minimum path sum
return triangle[0][0];
}
int main() {
int numRows = 4;
int triangle[4][4] = {
{2, 0, 0, 0},
{3, 4, 0, 0},
{6, 5, 7, 0},
{4, 1, 8, 3}
};
// Converting static 2D array to dynamic 2D array for passing to function
int* trianglePointers[4];
for (int i = 0; i < 4; i++) {
trianglePointers[i] = triangle[i];
}
printf("Minimum Total: %d\n", minimumTotal(trianglePointers, numRows)); // Output: 11
return 0;
}
C++:
#include <iostream>
#include <vector>
using namespace std;
int minimumTotal(vector<vector<int>>& triangle) {
int n = triangle.size();
// Start from the second last row and work upwards
for (int row = n - 2; row >= 0; row--) {
for (int col = 0; col <= row; col++) {
// Update the current element by adding the minimum of the two adjacent elements below it
triangle[row][col] += min(triangle[row + 1][col], triangle[row + 1][col + 1]);
}
}
// The top element now contains the minimum path sum
return triangle[0][0];
}
int main() {
vector<vector<int>> triangle = {
{2},
{3, 4},
{6, 5, 7},
{4, 1, 8, 3}
};
cout << "Minimum Total: " << minimumTotal(triangle) << endl; // Output: 11
return 0;
}
Java:
import java.util.List;
import java.util.ArrayList;
public class Triangle {
public static int minimumTotal(List<List<Integer>> triangle) {
int n = triangle.size();
// Start from the second last row and work upwards
for (int row = n - 2; row >= 0; row--) {
for (int col = 0; col <= row; col++) {
// Update the current element by adding the minimum of the two adjacent elements below it
int minPathSum = Math.min(triangle.get(row + 1).get(col), triangle.get(row + 1).get(col + 1));
triangle.get(row).set(col, triangle.get(row).get(col) + minPathSum);
}
}
// The top element now contains the minimum path sum
return triangle.get(0).get(0);
}
public static void main(String[] args) {
List<List<Integer>> triangle = new ArrayList<>();
triangle.add(List.of(2));
triangle.add(List.of(3, 4));
triangle.add(List.of(6, 5, 7));
triangle.add(List.of(4, 1, 8, 3));
System.out.println("Minimum Total: " + minimumTotal(triangle)); // Output: 11
}
}
Python:
def minimumTotal(triangle):
n = len(triangle)
# Start from the second last row and work upwards
for row in range(n - 2, -1, -1):
for col in range(row + 1):
# Update the current element by adding the minimum of the two adjacent elements below it
triangle[row][col] += min(triangle[row + 1][col], triangle[row + 1][col + 1])
# The top element now contains the minimum path sum
return triangle[0][0]
# Example usage
triangle = [
[2],
[3, 4],
[6, 5, 7],
[4, 1, 8, 3]
]
print("Minimum Total:", minimumTotal(triangle)) # Output: 11
C#:
using System;
using System.Collections.Generic;
class Triangle {
public static int MinimumTotal(List<List<int>> triangle) {
int n = triangle.Count;
// Start from the second last row and work upwards
for (int row = n - 2; row >= 0; row--) {
for (int col = 0; col <= row; col++) {
// Update the current element by adding the minimum of the two adjacent elements below it
int minPathSum = Math.Min(triangle[row + 1][col], triangle[row + 1][col + 1]);
triangle[row][col] += minPathSum;
}
}
// The top element now contains the minimum path sum
return triangle[0][0];
}
static void Main() {
var triangle = new List<List<int>> {
new List<int> { 2 },
new List<int> { 3, 4 },
new List<int> { 6, 5, 7 },
new List<int> { 4, 1, 8, 3 }
};
Console.WriteLine("Minimum Total: " + MinimumTotal(triangle)); // Output: 11
}
}
JavaScript:
function minimumTotal(triangle) {
const n = triangle.length;
// Start from the second last row and work upwards
for (let row = n - 2; row >= 0; row--) {
for (let col = 0; col <= row; col++) {
// Update the current element by adding the minimum of the two adjacent elements below it
triangle[row][col] += Math.min(triangle[row + 1][col], triangle[row + 1][col + 1]);
}
}
// The top element now contains the minimum path sum
return triangle[0][0];
}
// Example usage
const triangle = [
[2],
[3, 4],
[6, 5, 7],
[4, 1, 8, 3]
];
console.log("Minimum Total:", minimumTotal(triangle)); // Output: 11
Explanation:
- Step-by-step Explanation:
- Start from the second-to-last row.
- For each element, update it with the sum of itself and the smaller of the two adjacent elements in the row directly below.
- Continue this process upwards, and the top element will eventually contain the minimum path sum.
- Why Bottom-Up?
- By working from the bottom-up, we avoid recalculating the minimum path for each element multiple times, which makes the solution efficient.
Time Complexity:
- O(n) where
nis the number of rows in the triangle because each element is processed once.
Space Complexity:
- O(1) if we modify the triangle in place. If we use a separate array to store results, space complexity would be O(n).
Summary:
The problem of finding the minimum path sum in a triangle can be efficiently solved using dynamic programming with a bottom-up approach. This approach minimizes the space complexity by modifying the triangle in place.