My 8 line DP Java code(4 meaningful lines) with O(1) space


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

    The idea is simple.

    1. Go from bottom to top.

    2. We start form the row above the bottom row [size()-2].

    3. Each number add the smaller number of two numbers that below it.

    4. And finally we get to the top we the smallest sum.


  • 25
    H

    you modified the original array. it may be inappropriate


  • 1
    T

    +1 for should not modify the original array. But that could be solved simply clone a list.


  • 8
    E

    My C++ version of your algorithm. I hope it's easier to read.

    int minimumTotal(vector<vector<int> > &triangle) {
        for (int i=triangle.size()-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];
    }

  • 0
    L

    What if the List is LinkedList? What is the complexity of the get function ?


  • 0
    S

    Awesome approach !


  • 1
    Z

    Why cannot the original array be modified?


  • 2
    Z

    I see this solution only beats 8.41% of java solutions. But I can't figure out why this concise solution is slow. Any idea?


  • 2
    U

    it's O(n), if it's linked list, I think we should better use iterator to traverse every layer, otherwise using get/set the time complexity would be terrible


  • 0

    @zizizi You surely can modify it, but it's just not a good coding style. Because it may cause some mistakes in certain cases.


  • 0
    A

    Why does my code fail for inputs [[-1],[2,3],[1,-1,-3]].The output which I get is -2 while the expected output is -1 ,but -2 is less than -1 so shouldnt that be the answer


  • 0
    R

    @lihao814386741 For people asking "what if get(i) takes some time"? Then just store the intermediate results.

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

    If it's a linked list you can also use iterators.


  • 0

    @hpplayer here is a way to avoid modifying the input, C#

        public int MinimumTotal(IList<IList<int>> triangle) 
        {
            int[] row = triangle[triangle.Count - 1].ToArray();
            
            for (int level = triangle.Count - 2; level >= 0; level--)
            {
                int[] nextRow = new int[triangle[level].Count];
                for (int i = 0; i < triangle[level].Count; i++)
                {
                    nextRow[i] = triangle[level][i] + Math.Min(row[i], row[i+1]);
                }
                row = nextRow;
            }
            
            return row[0];
        }
    

  • 0
    L

    for(int j = 0; j <= i; j++) is less illustrative than for(int j = 0; j <= triangle.get(i).size(); j++), while, in fact, i == triangle.get(i).size() in this case/problem.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.