Memory Limit Exceeded in C++ but not in Python

Question

I am working on question 1249. Minimum Remove to Make Valid Parentheses on LeetCode. It is an easy question which I can solve with stack in both C++ and Python. However, my C++ version code leads to Memory Limit Exceeded, while my exact same Python code only consumes 15.3 MB memory. Could anyone help me understand what is wrong, please?

C++ code:

class Solution {
public:
    string minRemoveToMakeValid(string s) {
        stack<pair<char, int>> stack;
        for (int i=0; i<s.size();i++){
            if (s[i]!='(' && s[i]!=')')
                continue;
            else{
                if (!(stack.empty()) && stack.top().first=='(' && s[i]==')')
                    stack.pop();
                else
                    stack.push({s[i],i});
            } 
        }
        string res;
        for (int i=s.size()-1; i>=0;i--){ 
            if (!stack.empty() && i==stack.top().second)
                stack.pop();
            else{
                res = s[i] + res;
            }
        }
        return res;
            
    }
};

Even if replace stack data structure in C++ with vector, it still leads to Memory Limit Exceeded.

Python3

class Solution:
    def minRemoveToMakeValid(self, s: str) -> str:
        stack = []
        for i, c in enumerate(s):
            if c!="(" and c!=")":
                continue
            if stack and stack[-1][0] == '(' and c==")":
                stack.pop()
            else:
                stack.append([c,i])
        
        res =""
        for i in range(len(s)-1,-1,-1):
            if stack and i == stack[-1][1]:
                stack.pop()
            else:
                res = s[i] + res
        return res

Maybe using `stack` as both a class name and variable name is giving you grief? — Mark Ransom, Feb 25 '22 at 18:36
Could it be because `stack` implementation in C++ grows faster and goes beyond the limit? Do you want to try `vector` and see what happens? In Python, you're using a list and use it as a stack? — aminrd, Feb 25 '22 at 18:38
not sure if thats the problem, but `s.size()-1` is wrong. When the size is `0` then `s.size()-1` wraps around to the largest unsigned value — 463035818_is_not_an_ai, Feb 25 '22 at 18:39
@MarkRansom using stack as variable is not the issue, I saw many people do that. After renaming stack variable to st, nothing changed. — Albert G Lieu, Feb 25 '22 at 18:41
@463035818_is_not_a_number it is guarantted that 1 <= s.length <= 10^5, so ````s.size()-1```` is not the cause here — Albert G Lieu, Feb 25 '22 at 18:42
@aminrd after replace stack data structure with vector in c++, it still leads to ````Memory Limit Exceeded````, could you please help further? — Albert G Lieu, Feb 25 '22 at 18:46
Does it make a difference if you change the c++ method signature to: `string minRemoveToMakeValid(const string& s){`? Is this allowed on `LeetCode`? — quamrana, Feb 25 '22 at 18:47
@quamrana ````string minRemoveToMakeValid(const string& s){```` still leads to ````Memory Limit Exceeded```` — Albert G Lieu, Feb 25 '22 at 18:49
Do the answers to this [question](https://stackoverflow.com/questions/8468597/prepend-stdstring) help with memory? Perhaps: `string res; res.reserve(s.size());` might also help. — quamrana, Feb 25 '22 at 19:00
@quamrana ````string res; res.reserve(s.size());```` does not help, still causing Memory Limit Exceeded — Albert G Lieu, Feb 25 '22 at 19:04

score 2 · Answer 1 · answered Feb 25 '22 at 22:53

2

This is another guess about what could reduce the memory footprint.

I guess that each res = s[i] + res; may repeatedly reallocate memory resulting in res being over allocated above what is needed.

The code below (I'm hoping) makes far fewer allocations, each of an exact size needed at the time:

class Solution {
public:
    std::string minRemoveToMakeValid(std::string s) {
        std::stack<std::pair<char, int>> stack;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] != '(' && s[i] != ')')
                continue;
            else {
                if (!(stack.empty()) && stack.top().first == '(' && s[i] == ')')
                    stack.pop();
                else
                    stack.push({ s[i],i });
            }
        }
        std::string res(s.size(),' ');
        auto iter{ s.size() };
        for (int i = s.size() - 1; i >= 0; i--) {
            if (!stack.empty() && i == stack.top().second)
                stack.pop();
            else {
                //res = s[i] + res;
                res[--iter] = s[i];
            }
        }
        return res.substr(iter);

    }
};

answered Feb 25 '22 at 22:53

quamrana

37,849
12
53
71

It does create a load of unnecessary strings, though I would expect RAII to immediately destroy them and not use much extra memory overall. – John Kugelman Feb 25 '22 at 22:56
@JohnKugelman: I have this nagging suspicion that LeetCode may be overestimating the amount of memory used. – quamrana Feb 25 '22 at 23:00
it seems that ````res = s[i] + res;```` is the cause of Memory Limit Exceeded, but I can't understand why. I could understand that ````res = s[i] + res;```` may be slower than ````res = res + s[i] ;````, as the latter runs in O(1), but why they differ in memory usage?' – Albert G Lieu Feb 25 '22 at 23:08
Are you saying that LeetCode accepts this code? Does it give a size of memory used? – quamrana Feb 25 '22 at 23:09
yes, leetcode accepted your answer! Yes, your code used 13MB – Albert G Lieu Feb 25 '22 at 23:12
both ````res = res + s[i];```` and ````res = s[i] + res;```` cause Memory Limit Exceeded,. – Albert G Lieu Feb 25 '22 at 23:12
Ok, my suspicion is that LeetCode may be totalling up all the sizes of the allocations made, ignoring the common practise of many allocators which is to reuse recently deleted memory. `res = s[i] + res;` will make *a lot* of allocations, roughly n^2 bytes where `n==s.size()`. – quamrana Feb 25 '22 at 23:14
@quamrana are you saying this is Leetcode's problem, not the internal issue of C++ language? I guess I will try to profile this code in CLion to see how much memory on earth it uses. – Albert G Lieu Feb 25 '22 at 23:16
Yes, but this is pure conjecture. If you are going to the trouble of profiling, you could simulate what I suspect by collecting a redundant vector of strings of the intermediate values of `res` to see how much memory *could* be wasted by an inefficient allocator. – quamrana Feb 25 '22 at 23:19

Memory Limit Exceeded in C++ but not in Python

1 Answers1