Minimum Triangle Sum – Java/Kotlin

Overview

In this article we will try to solve one of the problem mentioned in Perl Weekly Challenge in Java. The problem is called Triangle Sum. You are given triangle array. You need to find the minimum path sum from top to bottom. When you are on index i on the current row then you may move to either index i or index i + 1 on the next row.

Example 1

Input: Triangle = [ [1], [2,4], [6,4,9], [5,1,7,2] ]
Output: 8

Explanation: The given triangle

            1
           2 4
          6 4 9
         5 1 7 2

The minimum path sum from top to bottom:  1 + 2 + 4 + 1 = 8

             [1]
           [2]  4
           6 [4] 9
          5 [1] 7 2

Example 2

Input: Triangle = [ [3], [3,1], [5,2,3], [4,3,1,3] ]
Output: 7

Explanation: The given triangle

            3
           3 1
          5 2 3
         4 3 1 3

The minimum path sum from top to bottom: 3 + 1 + 2 + 1 = 7

             [3]
            3  [1]
           5 [2] 3
          4 3 [1] 3

Code

We will create a method which will take a list of list containing the numbers. We will iterate each row and find the minimum in the row. The value will be added to the sum

TriangleSum.java

public static int triangleSum(List<List<Integer>> list) {
    int sum = 0;
    for (List<Integer> row : list) {
        sum += Collections.min(row);
    }
    return sum;
}

TriangleSumKotlin.kt

fun triangleSum(list: List<List<Int>?>): Int {
    var sum = 0
    for (row in list) {
        sum += Collections.min(row)
    }
    return sum
}

Test

Below is a simple test for the above code:

@Test
public void triangleSum() {
    List<List<Integer>> list = List.of(List.of(1), List.of(2, 4), List.of(6, 4, 9), List.of(5, 1, 7, 2));
    assertEquals(8, TriangleSum.triangleSum(list));
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: