Time limit exceeded

  • 2

    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];
            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

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