6
\$\begingroup\$

I am studying for interviews for various companies. I wrote a solution to this problem, but if an experience programmer looks at it I am sure there are certain areas the code can be made in to a more beautiful code.

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle

[
     [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).

My DP solution:

public class Solution {
public static int minimumTotal(List<List<Integer>> triangle) {
        if(triangle==null){
            return -1;
        }
        int [][] dp=new int[triangle.size()][triangle.size()];
        for(int i=0;i<triangle.size();i++){
            Arrays.fill(dp[i],0);

        }
        getMin(triangle,0,0,dp);
        return dp[0][0];
    }


    public static int getMin(List<List<Integer>> tri, int level, int index, int [][]dp){
        if((level+1)==tri.size()){
            dp[level][index]=tri.get(level).get(index);
            return dp[level][index];
        }else{
            int left=-1;
            int right=-1;
            if(dp[level+1][index]!=0){
                left=dp[level+1][index];
            }else{
                left=getMin(tri, level+1, index,dp);
            }
            if(dp[level+1][index+1]!=0){
                right=dp[level+1][index+1];
            }else{
                right=getMin(tri, level+1, index+1,dp);
            }
            dp[level][index]=tri.get(level).get(index)+Math.min(left,right);

            return dp[level][index];
        }
    }
}
\$\endgroup\$
5
\$\begingroup\$

Variable Names

Good variable names are important, because they make the code readable. Many of your names are good, but dp and tri could be a lot better.

Formatting

  • you should use more spaces (around =, ==, +, etc), and before { and after } (just paste your code in an IDE, it can fix this for you).
  • arrays are commonly declared like this int[][] name.

Misc

  • don't assign a value if it is never used (left = -1).
  • if (something != somethingElse) { doThing(); } else { doOtherThing(); } is commonly written the other way around (ask if (something == somethingElse) and switch the calls).
  • return early: as you are returning in your if clause, you don't need an else, thus you can save one level of nesting

Use ternary operator

In most situations, the ternary operator is not a good choice. But when conditionally assigning a value, it sometimes does make sense and simplifies the code:

        int left = (dp[level + 1][index] == 0) ? getMin(tri, level + 1, index, dp) : dp[level + 1][index];
        int right = (dp[level + 1][index + 1] == 0) ? getMin(tri, level + 1, index + 1, dp) : dp[level + 1][index + 1];

If you save dp[level + 1][index] and dp[level + 1][index + 1] in local variables instead of accessing them repeatedly, it would also look a lot better.

If you don't want to use the ternary operator, your if statements can be simplified like this:

        int left = dp[level + 1][index];
        if (left == 0) {
            left = getMin(tri, level + 1, index, dp);
        }

Final Code

If you do these things, your code might look something like this:

public static int getMin(List<List<Integer>> triangle, int level, int index, int[][] dp) {
    if (level == triangle.size() - 1) {
        dp[level][index] = triangle.get(level).get(index);
        return dp[level][index];
    }

    int left = dp[level + 1][index];
    if (left == 0) {
        left = getMin(triangle, level + 1, index, dp);
    }

    int right = dp[level + 1][index + 1];
    if (right == 0) {
        right = getMin(triangle, level + 1, index + 1, dp);
    }

    dp[level][index] = triangle.get(level).get(index) + Math.min(left, right);
    return dp[level][index];
}
\$\endgroup\$
5
\$\begingroup\$

Code Style

Although not the most important aspect of programming, I'd recommend using a bit more spaces in your code.

Just a few random example lines:

dp[level][index]=tri.get(level).get(index);
if(dp[level+1][index+1]!=0){
    right=dp[level+1][index+1];
dp[level][index]=tri.get(level).get(index)+Math.min(left,right);

(Note that these four lines do not belong together in the original code)

These would look better as:

dp[level][index] = tri.get(level).get(index);
if (dp[level + 1][index + 1] != 0) {
    right = dp[level + 1][index + 1];
dp[level][index] = tri.get(level).get(index) + Math.min(left, right);

This does improve readability quite a bit, and is the Java conventions.

Exceptions for exceptional cases

if(triangle==null){
    return -1;
}

Instead of returning the special value -1 here, which could be a valid output if your input contained some negative numbers, it is better to throw an exception.

if (triangle == null) {
    throw new NullPointerException("triangle cannot be null");
}

Or, using a Java method call as of Java 7:

Objects.requireNonNull(triangle, "triangle cannot be null");

Last index

When checking if an index is the last index in a list:

if((level+1)==tri.size()){

Then it is more common to compare the actual index, rather than the size:

if (level == tri.size() - 1) {

And as you see, you can remove one set of parameters as well.

Initialization

As all int-arrays are initialized to zero by default, this code does absolutely nothing:

for (int i = 0; i < triangle.size(); i++) {
    Arrays.fill(dp[i], 0);
}

Working backwards

Sometimes when faced with a challenge, it can be a good idea to think: What if I work backwards? Sometimes working from the other direction can be a big advantage. A different approach to this problem would be to work backwards.

     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]

Start at the bottom row. On this row, we can find that the 8 is irrelevant as it is right in the middle of two much smaller numbers that can be reached instead, from the same parents that can reach the 8. The same way, we can see that the 4 is a much worse choice than the 1. So the information we want from that row is [*, 1, *, 3].

Now on to the next row! [6, 5, 7]. We find out that the 6 is totally irrelevant as the 5 can also be reached from the same parent (the 3 above). Additionally, the only child of 5 is 1, but the child of 7 is 3. As 1 + 5 < 3 + 7, 1 + 5 does seem like a better route so far. But to be safe, I would store the sum for each of the current 'nodes'. So for the 5, store 1 + 5 = 6. For the 7, store 3 + 7 = 10.

On to the next row! [3, 4]. Here we can find out that the 3 is much better, as the only way the 4 is relevant is because 3 + 7 = 10. But as 1 + 5 + 3 = 9 is smaller than 3 + 7 + 4 = 14, and the 3 and 4 are neighbors, we can totally forget about the 3 + 7 + 4 = 14 path, as it is now irrelevant thanks to our superior 1 + 5 + 3 = 9 path.

Last row, [2]. Here we don't have any choice, so we just add the 2 to our current 1 + 7 + 3 = 9 path and we end up with 11.

Edit: after some debugging of your code, your approach is actually quite fast and very similar to what I started doing here. We just don't use the same order when iterating over the triangle. But if you want to see what I ended up with, take a look at my question.

The fact that I thought your code was slower than it actually was might be an indication about the readability of your code. I think that by getting rid of the recursion the way I did the actual algorithm used is more apparent, and thus it is more clear that the time complexity is not \$O(2^n)\$ which it looks like at first glance.

\$\endgroup\$
3
\$\begingroup\$

Just for the record, here's an alternative, elegant but inefficient algorithm:

public static int solution(List<List<Integer>> triangle) {
    assert !triangle.isEmpty();
    assert !triangle.get(0).isEmpty();
    return getMin(triangle, 0, 0, 0);
}

public static int getMin(List<List<Integer>> triangle, int level, int index, int accum) {
    if (level == triangle.size()) {
        return accum;
    }
    int newAccum = accum + triangle.get(level).get(index);
    return Math.min(
            getMin(triangle, level + 1, index, newAccum),
            getMin(triangle, level + 1, index + 1, newAccum)
            );
}

No helper matrix, no mutations, no side effects.

Unfortunately, it's also inefficient. Maybe you already knew this, and that's why you're using a different algorithm and a helper matrix. The reason is that many paths are explored twice, for example in a triangle like this:

   q
  x y
 x z y
x z z y

Notice the overlapping section marked with z under the sub-triangles with x and y at the top.


To verify that your implementation works, it's good to have some unit tests around, for example:

@Test
public void test1Level() {
    assertEquals(5, solution(Arrays.asList(Arrays.asList(5))));
}

@Test
public void test2Levels() {
    assertEquals(5, solution(Arrays.asList(Arrays.asList(2), Arrays.asList(3, 4))));
}

@Test
public void test3Levels() {
    assertEquals(10, solution(Arrays.asList(Arrays.asList(2), Arrays.asList(3, 4),
            Arrays.asList(6, 5, 7))));
}

@Test
public void test4Levels() {
    assertEquals(11, solution(Arrays.asList(Arrays.asList(2), Arrays.asList(3, 4),
            Arrays.asList(6, 5, 7), Arrays.asList(4, 1, 8, 3))));
}

@Test
public void test4Levels_2() {
    assertEquals(15, solution(Arrays.asList(Arrays.asList(2), Arrays.asList(3, 4),
            Arrays.asList(6, 5, 7), Arrays.asList(4, 11, 8, 3))));
}

@Test
public void test4Levels_3() {
    assertEquals(16, solution(Arrays.asList(Arrays.asList(2), Arrays.asList(3, 4),
            Arrays.asList(6, 5, 7), Arrays.asList(5, 11, 8, 13))));
}

@Test
public void test4Levels_4() {
    assertEquals(18, solution(Arrays.asList(Arrays.asList(2), Arrays.asList(3, 4),
            Arrays.asList(6, 5, 7), Arrays.asList(15, 11, 8, 13))));
}

Please do take all the advices explained by @Simon and @Tim. They are all very important for improving your coding style.

A few additional points on top of those:

  1. When processing the one before last row, you don't need to update dp[level][index], you can return the value directly:

    if (level == triangle.size() - 1) {
        return triangle.get(level).get(index);
    }
    
  2. This code looked immediately suspicious:

    getMin(triangle, 0, 0, dp);
    return dp[0][0];
    

    Side effects are not good. Especially by methods named getSomething. When you have a getSomething method that produces side effects, that's a good sign that you need to rethink your logic and refactor your code, or at the minimum find a better name for the method.

\$\endgroup\$
  • \$\begingroup\$ This is a standard recursive brute-force depth-first-search approach. While entirely readable and definitely 100% accurate, I am not sure if it is faster than the original code. As the size of the triangle is increased, this will be a lot slower. Time complexity O(2^n), where n is the number of rows in the triangle. \$\endgroup\$ – Simon Forsberg Oct 18 '14 at 16:42
  • \$\begingroup\$ I like the unit testing, but you might want to consider a parametrized unit test for that. \$\endgroup\$ – Simon Forsberg Oct 18 '14 at 16:52
  • \$\begingroup\$ It turns out that the OP's code is O(n^2) while your 'alternative algorithm' is O(2^n). You are definitely not iterating through each element twice. \$\endgroup\$ – Simon Forsberg Oct 18 '14 at 20:45
3
\$\begingroup\$

Just for the record, too.

While janos' now-deleted solution is slow, there's a simple and clear way how to speed it up: memoization. This method

public static int getMin(List<List<Integer>> triangle, int level, int index, int accum) {
    if (level == triangle.size()) {
        return accum;
    }
    int newAccum = accum + triangle.get(level).get(index);
    return Math.min(
            getMin(triangle, level + 1, index, newAccum),
            getMin(triangle, level + 1, index + 1, newAccum)
            );
}

is not directly usable for this, but a trivial rewrite

public static int solution(List<List<Integer>> triangle) {
    return new Solver(triangle).getMin(0, 0);
}

public static int getMin(int level, int index) {
    if (level == triangle.size()) {
        return 0;
    }
    int current = triangle.get(level).get(index);
    return Math.min(
            current + getMin(level + 1, index),
            current + getMin(level + 1, index + 1)
            );
}

reduces the number of arguments to two (triangle is a new instance variable and accum has been eliminated).

Now we have a method depending only the position in the triangle. The slowness of janos' solution comes from computing getMin multiple times for the same position. Storing it after the first call eliminates all the inefficiency (that's actually just like dynamic programming, but hopefully clearer).


It's pretty trivial

private final List<List<Integer>> triangle;
// Stores the results of getMin; 0 means uninitialized.
private final int[][] getMinTable;

public static int solution(List<List<Integer>> triangle) {
    return new Solver(triangle).getMin(0, 0);
}

private Solver(List<List<Integer>> triangle) {
    this.triangle = triangle;
    getMinTable = new int[triangle.size()][triangle.size()];
}

private static int getMin(int level, int index) {
    if (level == triangle.size()) {
        return 0;
    }
    int result = getMinTable[level][size];
    if (result != 0) {
        return result;
    }
    int current = triangle.get(level).get(index);
    result = Math.min(
            current + getMin(level + 1, index),
            current + getMin(level + 1, index + 1)
            );
    getMinTable[level][size] = result;
    return result;
}

Actually, there should be a class Triangle. Using List<List<Integer>> is not very nice. But my answer is overlong already now.

\$\endgroup\$
  • \$\begingroup\$ I'm glad you still found my answer helpful. I will undelete a bit later, after the better answers are safely in the lead. On the other hand, this code doesn't store anything either, so it still looks like it will call getMin twice for the same position. \$\endgroup\$ – Stop ongoing harm to Monica Oct 19 '14 at 15:34
  • \$\begingroup\$ @janos The code does not, but see the last sentence. Maybe I should implement it? \$\endgroup\$ – maaartinus Oct 19 '14 at 15:37
  • \$\begingroup\$ You meant, storing it would eliminate the inefficiency... If you add the implementation to your answer, that should increase its value for sure. (I myself already +1-ed though ;-) \$\endgroup\$ – Stop ongoing harm to Monica Oct 19 '14 at 15:38
  • 1
    \$\begingroup\$ @janos Done. I find it important to start with a nice solution and make it fast (without crippling it too much) and this was a perfect chance to demonstrate it. \$\endgroup\$ – maaartinus Oct 19 '14 at 15:59
1
\$\begingroup\$

I'm too lazy to do a full review, but you could make the code clearer by going a bit more OO and defining some intermediary type where you would store the intermediate costs with their associated path.

It would make the code longer, but cleaner.

I actually implemented it in Scala (I was very lazy) in this answer to a post for a review to the same question. If you can read Scala you can get a better idea of what I mean.

\$\endgroup\$
  • \$\begingroup\$ IMO, the fact that you're lazy is totally irrelevant to the answer. \$\endgroup\$ – Simon Forsberg Oct 19 '14 at 16:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.