Valid Parentheses — Editorial

Opening the reading…

Intuitionwhy the next closing bracket must match the stack top

A closing bracket cannot match just any earlier opening bracket. It must match the most recently opened bracket that has not been closed yet. For example, in ([ ]), the square bracket closes before the parenthesis because it was opened later. A stack stores exactly that unfinished nesting order: every new opening bracket goes on top, and only the top can be removed.

When a closing bracket arrives, compare it with the stack top. An empty stack means there is nothing to close, and a different bracket means the nesting order is broken; either case makes the string invalid immediately. If the types match, pop the opening bracket. At the end, the stack must be empty, because leftover openings are also unmatched.

Approachone pass, with the stack representing unfinished openings

Create a mapping from each closing bracket to its matching opening bracket, because checking the expected opener in one place avoids repeating three separate comparison rules.

Create an empty stack of opening brackets, because the stack must remember every opener that has not yet been matched.

Scan the string from left to right, because bracket validity depends on the order in which brackets appear rather than on their total counts.

Push every opening bracket onto the stack, because it may be the bracket that a later closing bracket must match.

For a closing bracket, return false if the stack is empty or its top is not the mapped opening bracket, because this closing bracket has no legal match at the only position it is allowed to close.

For a matching closing bracket, pop the stack, because that opening bracket is now complete and must no longer affect future matches.

After the scan, return whether the stack is empty, because any remaining opener was never closed even if every closing bracket seen so far was valid.

Complexitythe stack grows only with unmatched opening brackets

MEASURE	BOUND	WHY
Time	O(n)	The scan examines each character once. Each character causes at most one mapping lookup and one stack operation, and no character is revisited, so the total work is linear.
Space	O(n) extra	The returned value is a boolean and adds no output storage. The stack can hold every character in the worst input shape, such as a string containing only opening brackets, so the working memory is O(n).

Here n is the length of the input string.

Annotated solutionC++ · iterative stack scan · complete judge-ready class

CPPScan each bracket, matching closers against the most recent unmatched opener.

#include <stack>
#include <string>
#include <unordered_map>

using namespace std;

class Solution {
public:
    bool isValid(string s) {
        unordered_map<char, char> pairs = {{')', '('}, {'}', '{'}, {']', '['}};
        stack<char> st;

        for (char c : s) {
            if (pairs.count(c)) {
                if (st.empty() || st.top() != pairs[c]) {
                    return false;
                }
                st.pop();
            } else {
                st.push(c);
            }
        }

        return st.empty();
    }
};

The condition st.empty() must be checked before st.top(), because an input beginning with a closing bracket has no element to inspect. The final st.empty() is a separate requirement: a string such as ( contains no bad closing bracket, but it still leaves an opening bracket unmatched. Together, these checks cover both directions of imbalance.