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
– Mark Ransom, Commented Feb 25, 2022 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
– aminrd, Commented Feb 25, 2022 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
– 463035818_is_not_an_ai, Commented Feb 25, 2022 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
– Albert G Lieu, Commented Feb 25, 2022 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
– Albert G Lieu, Commented Feb 25, 2022 at 18:42

quamrana · Accepted Answer · 2022-02-25 22:53:00Z

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, 2022 at 22:53

quamrana

39.5k13 gold badges57 silver badges77 bronze badges

Sign up to request clarification or add additional context in comments.

9 Comments

John Kugelman Over a year ago

It does create a load of unnecessary strings, though I would expect RAII to immediately destroy them and not use much extra memory overall.

quamrana Over a year ago

@JohnKugelman: I have this nagging suspicion that LeetCode may be overestimating the amount of memory used.

Albert G Lieu Over a year ago

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?'

quamrana Over a year ago

Are you saying that LeetCode accepts this code? Does it give a size of memory used?

Albert G Lieu Over a year ago

yes, leetcode accepted your answer! Yes, your code used 13MB

|

Collectives™ on Stack Overflow

Memory Limit Exceeded in C++ but not in Python

1 Answer 1

9 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

9 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related