What is the Memory Limit?

#1

My solution won’t pass because of memory limit. I don’t understand what am I supposed to do. I stored the trees, then deleted duplicate trees. I also cleared all my containers after using them. Will it only pass if I never created duplicate trees to begin with?

#2

Probably duplicate trees are the problem, if it’s not then try clearing all the memory you used (which in c++ if you used a vector v would be something like v.clear()). Anyways, you should try coming up with a solution without duplicates.

#3

I do not have duplicate trees in my solution and I am using dynamic programming, yet I can only successfully solve up to N=11. With N=12 I get a Memory limit exceeded. I am using python3. I wonder if the memory limits are set too strict for this problem.

#4

problem stupid, memory limits way too strict.

#5

Don’t create the same trees over and over. Store the already created trees’ root node in a (arraylist) cache and when trying to generate a tree already generated, just re-use the already created tree.

#6

@amir-r

I don’t create duplicate trees, and still have MLE problem. Apparently the configuration of the problem is wrong.

Here’s the code if you need to verify.

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

struct storeItem {
    storeItem(int parent, int current, int start, int end)
        : parent(parent), current(current), start(start), end(end) {}
    int parent;
    int current;
    int start;
    int end;
};

vector<storeItem> store;
int size;

vector<TreeNode*> output;

void doOutput() {
    vector<int> parent(size + 1);
    
    for (const storeItem& item : store) {
        if (item.current == -1)
            continue;
        // The following will be done multiple times due to the construction of store,
        // but it's okay.
        parent[item.current] = item.parent;
    }

    vector<TreeNode*> nodes(size + 1);
    for (int i = 1; i <= size; ++i)
        nodes[i] = new TreeNode(i);

    for (int i = 1; i <= size; ++i) {
        if (parent[i] == -1)
            output.push_back(nodes[i]);
        else if (i < parent[i])
            nodes[parent[i]]->left = nodes[i];
        else
            nodes[parent[i]]->right = nodes[i];
    }
}

int num_output = 0;

void generate(int to_process) {
    if (to_process == store.size()) {
        doOutput();
        return;
    }
        
    int current = store[to_process].current;
    int start = store[to_process].start;
    int end = store[to_process].end;
    
    if (end < start) {
        generate(to_process + 1);
        return;
    }
    
    for (int mid = start; mid <= end; ++mid) {
        store.emplace_back(current, mid, start, mid - 1);
        store.emplace_back(current, mid, mid + 1, end);
        generate(to_process + 1);
        store.pop_back();
        store.pop_back();
    }
}

vector<TreeNode*> Solution::generateTrees(int A) {
    size = A;
    store.clear();
    store.emplace_back(-1, -1, 1, A);

    generate(0);
    store.clear();

    return std::move(output);
}
#7

Finally I tried the insane approach to decrease memory usage by having different tree roots sharing the same leaves. This reduces the total number of nodes from 742900*13 to 1440025 for A=13.

The nodes can be built easily using DP (the code has less than 50 lines).

And miraculously this solution passed the checker.