Triangle

                                            
class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int n = triangle.size();
        
        for (int i = n - 2; i >= 0; i--) {
            for (int j = 0; j < triangle[i].size(); j++) {
                triangle[i][j] += min(triangle[i + 1][j], triangle[i + 1][j + 1]);
            }
        }
        
        return triangle[0][0];
    }
};

                                            
class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        for (int i = triangle.size() - 2; i >= 0; i--) {
            for (int j = 0; j < triangle.get(i).size(); j++) {
                int current = triangle.get(i).get(j) + Math.min(triangle.get(i + 1).get(j), triangle.get(i + 1).get(j + 1));
                triangle.get(i).set(j, current);
            }
        }
        return triangle.get(0).get(0);
    }
}

                                            
class Solution(object):
    def minimumTotal(self, triangle):
        """
        :type triangle: List[List[int]]
        :rtype: int
        """
        if not triangle:
            return 0
        
        dp = triangle[-1]
        
        for i in range(len(triangle) - 2, -1, -1):
            for j in range(len(triangle[i])):
                dp[j] = triangle[i][j] + min(dp[j], dp[j + 1])
        
        return dp[0]

                                            
int minimumTotal(int** triangle, int triangleSize, int* triangleColSize) {
    for (int i = triangleSize - 2; i >= 0; i--) {
        for (int j = 0; j < triangleColSize[i]; j++) {
            triangle[i][j] += fmin(triangle[i + 1][j], triangle[i + 1][j + 1]);
        }
    }
    return triangle[0][0];
}

                                            
public class Solution {
    public int MinimumTotal(IList<IList<int>> triangle) {
        for (int i = triangle.Count - 2; i >= 0; i--) {
            for (int j = 0; j < triangle[i].Count; j++) {
                triangle[i][j] += Math.Min(triangle[i + 1][j], triangle[i + 1][j + 1]);
            }
        }
        return triangle[0][0];
    }
}

                                            
/**
 * @param {number[][]} triangle
 * @return {number}
 */
const minimumTotal = (triangle) => {
    const n = triangle.length;
    const dp = [...triangle[n - 1]];
    
    for (let i = n - 2; i >= 0; i--) {
        for (let j = 0; j <= i; j++) {
            dp[j] = triangle[i][j] + Math.min(dp[j], dp[j + 1]);
        }
    }
    
    return dp[0];
};

                                            
function minimumTotal(triangle: number[][]): number {
    for (let i = triangle.length - 2; i >= 0; i--) {
        for (let j = 0; j < triangle[i].length; j++) {
            triangle[i][j] += Math.min(triangle[i + 1][j], triangle[i + 1][j + 1]);
        }
    }
    
    return triangle[0][0];
};

                                            
class Solution {
    /**
     * @param Integer[][] $triangle
     */
    function minimumTotal($triangle) {
        $n = count($triangle);
        $dp = $triangle[$n - 1];
        
        for ($i = $n - 2; $i >= 0; $i--) {
            for ($j = 0; $j <= $i; $j++) {
                $dp[$j] = $triangle[$i][$j] + min($dp[$j], $dp[$j + 1]);
            }
        }
        
        return $dp[0];
    }
}

                                            
class Solution {
    func minimumTotal(_ triangle: [[Int]]) -> Int {
        var dp = triangle.last!

        for row in (0..<triangle.count-1).reversed() {
            for i in 0..<triangle[row].count {
                dp[i] = triangle[row][i] + min(dp[i], dp[i+1])
            }
        }

        return dp[0]
    }
}

                                            
class Solution {
    fun minimumTotal(triangle: List<List<Int>>): Int {
        val n = triangle.size
        val dp = IntArray(n) { triangle[n-1][it] }
        
        for (i in n-2 downTo 0) {
            for (j in 0..i) {
                dp[j] = triangle[i][j] + minOf(dp[j], dp[j+1])
            }
        }
        
        return dp[0]
    }
}

                                            
class Solution {
  int minimumTotal(List<List<int>> triangle) {
    for (int i = triangle.length - 2; i >= 0; i--) {
      for (int j = 0; j < triangle[i].length; j++) {
        triangle[i][j] += 
          triangle[i + 1][j] < triangle[i + 1][j + 1] ? triangle[i + 1][j] : triangle[i + 1][j + 1];
      }
    }
    return triangle[0][0];
  }
}

                                            
func minimumTotal(triangle [][]int) int {
    n := len(triangle)
    dp := make([]int, n)

    for i := range triangle[n-1] {
        dp[i] = triangle[n-1][i]
    }

    for i := n - 2; i >= 0; i-- {
        for j := 0; j <= i; j++ {
            dp[j] = min(dp[j], dp[j+1]) + triangle[i][j]
        }
    }

    return dp[0]
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

                                            
# @param {Integer[][]} triangle
# @return {Integer}
def minimum_total(triangle)
    (triangle.length - 2).downto(0) do |i|
        (0..triangle[i].length - 1).each do |j|
            triangle[i][j] += [triangle[i + 1][j], triangle[i + 1][j + 1]].min
        end
    end
    triangle[0][0]
end

                                            
object Solution {
    def minimumTotal(triangle: List[List[Int]]): Int = {
        val n = triangle.length
        val dp = Array.ofDim[Int](n + 1)

        for (i <- n - 1 to 0 by -1) {
            for (j <- 0 until triangle(i).length) {
                dp(j) = triangle(i)(j) + dp(j).min(dp(j + 1))
            }
        }
        dp(0)
    }
}

                                            
impl Solution {
    pub fn minimum_total(triangle: Vec<Vec<i32>>) -> i32 {
        let mut dp = triangle.last().unwrap().clone();
        
        for i in (0..triangle.len()-1).rev() {
            for j in 0..triangle[i].len() {
                dp[j] = triangle[i][j] + dp[j].min(dp[j+1]);
            }
        }
        
        dp[0]
    }
}

To solve this coding challenge, we need to find the minimum path sum from top to bottom in a given triangle array. The key point here is that you can only move to an adjacent number on the row immediately below from your current position. To achieve this, we will use dynamic programming. In this approach, we will start from the bottom of the triangle and move upwards, updating the path sums.

Explanation

Here's a step-by-step explanation to solve the problem:

Initialization Check : First, we check if the given triangle array is empty. If it is empty, we return 0, as there are no elements to sum.
Bottom-Up Calculation : We begin our calculations from the bottom of the triangle:

We use the last row of the triangle as our starting point. This row will serve as our initial state for dynamic programming.

Dynamic Programming Update : For each row, starting from the second last row up to the top row (indexed from
len(triangle) - 2

to
0

):

We iterate over each element in the current row.
For each element, we determine the minimum path sum by adding the current element’s value to the smaller of the two adjacent values in the row directly below it.

Final Result : After updating all rows, the top element of our dynamic programming array will contain the minimum path sum from top to bottom.

Detailed Steps in Pseudocode

                                            
# Given triangle array
triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]

# Check if the triangle is empty. If empty, return 0.
if triangle is empty:
return 0

# Initialize dp with the last row of the triangle
dp = copy the last row of the triangle

# Traverse the triangle from second last row to the first row
for each row_index from length of triangle - 2 to 0:

# Traverse each element in the current row
for each element_index in current row:

# Update dp at current index to the minimum path sum
dp[element_index] = triangle[row_index][element_index] 
+ minimum(dp[element_index], dp[element_index + 1])

# The top element of dp now contains the minimum path sum
return dp[0]

Explanation of Pseudocode

Initialization :

We copy the last row of the triangle into our dynamic programming array
dp

. This array will be used to store the minimum path sums as we move up the triangle.

Outer Loop :

The outer loop starts from the second last row of the triangle (
length of triangle - 2

) and moves up to the first row (
0

). This is because our dynamic programming approach works by updating from the bottom of the triangle to the top.

Inner Loop :

The inner loop iterates over each element in the current row indexed by
row_index

.
For each
element_index

:

dp[element_index]

is updated to the value of the current element in the triangle plus the minimum of the two adjacent values from the row below. This effectively keeps track of the minimum path sum that can be achieved up to that point.

Final Output :

After updating all rows,
dp[0]

will contain the minimum path sum from the top of the triangle to the bottom.

This method ensures that we only use O(n) extra space, where n is the number of rows in the triangle, making it both space and time efficient.