Time limit exceeded


  • 2
    J

    The following solution uses recursion. It uses recursion on a binary tree, the minimum at a node is the simply the min of ( min of its left subtree + itself, min of its right subtree + itself)

    But it is giving time limit exceeded. help!

    class Solution {
    
                //use existing vector as data structure, but operate on it like binary trees
                //given a node triangle[i][j];
                //left child: triangle[i+1][j];
                //right child: triangle[i+1][j+1];
    
        public:
            int minimumTotal(vector<vector<int> > &triangle) {
    
                
                if (triangle.empty()) return 0;
                
                return minimum(triangle, 0, 0);
            }
            
            int minimum(vector<vector<int>> &triangle, int i, int j) {
                if (i==triangle.size()-1)
                    return triangle[i][j];
                return triangle[i][j] + min(minimum(triangle, i+1, j), minimum(triangle, i+1, j+1));
            }
        };

  • 0
    W

    @jz left subtree's right subtree and right subtree's left subtree is overlap, you call minimum() on such subtrees duplicately many many times. You can memorize the intermediate results and do a lookup first before calling the minimum() on each subtree.


Log in to reply
 

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