# Time limit exceeded

• 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));
}
};``````

• @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.

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