Interesting Memory Differences in Valid Parentheses

Friday, October 20, 2023

class Solution {
public:
    bool isValid(string s) {
        stack<char> seen;

        for (const auto ch : s) {
            if (ch == '(' || ch == '{' || ch == '[') {
                seen.emplace(ch);
                continue;
            }
            if (ch == ')') {
                if (seen.size() <= 0 || seen.top() != '(') {
                    return false;
                }
                seen.pop();
            }
            else if (ch == '}') {
                if (seen.size() <= 0 || seen.top() != '{') {
                    return false;
                }
                seen.pop();
            }
            else if (ch == ']') {
                if (seen.size() <= 0 || seen.top() != '[') {
                    return false;
                }
                seen.pop();
            } else {
                continue;
            }
        }
        return seen.size() == 0;
    }
};

has better memory usage (6.3 MB) than

class Solution {
public:
    bool isValid(string s) {
        stack<char> seen;

        for (const auto ch : s) {
            if (ch == '(' || ch == '{' || ch == '[') {
                seen.emplace(ch);
                continue;
            }
            if (ch == ')') {
                if (seen.size() <= 0 || seen.top() != '(') {
                    return false;
                }
            }
            else if (ch == '}') {
                if (seen.size() <= 0 || seen.top() != '{') {
                    return false;
                }
            }
            else if (ch == ']') {
                if (seen.size() <= 0 || seen.top() != '[') {
                    return false;
                }
            } else {
                continue;
            }
            seen.pop();
        }
        return seen.size() == 0;
    }
};

with (6.6 MB).

Not a massive difference in absolute sense but the first is 90th percentile while the second is 50th percentile.

Similarly in Python, we see 90th percentile memory usage with the first but 30% percentile with the seecond. Interestingly the Python version has a tradeoff of memory usage, while the C++ one just runs so fast (0 ms) for both versions.

←Previous
Next→