LESSON 316 OF 409 · STACK

Valid Parentheses in C++: Stack Solution in O(n)

Given a string input containing just the characters '(', ')', '{', '}', '[' and ']', determine if it is valid.

An input string is valid if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.

Example 1:

Input: input = "()"
Output: true

Example 2:

Input: input = "()[]{}"
Output: true

Example 3:

Input: input = "(]"
Output: false

Example 4:

Input: input = "([)]"
Output: false

Example 5:

Input: input = "{[]}"
Output: true

Constraints:

The length of input is between 1 and 10⁴.
input consists of parentheses only '()[]{}'.

Note:

Your algorithm should run in O(n) time and use O(n) extra space.

STEP 1 OF 11

Guided

Ctrl + Enter to check

C++ · STACK

Valid Parentheses in C++, explained

Problem overview

The method isValid(string input) receives a string made only of the characters (, ), {, }, [ and ]. It returns true when the brackets are valid, which needs two things: every opening bracket is closed by a bracket of the same type, and brackets are closed in the correct order, so the one opened last is closed first.

Examples: "()", "()[]{}" and "{[]}" are valid. "(]" is not, because the types differ. "([)]" is not either: each type is paired up, but the [ opened inside the parentheses is still open when the ) arrives, so the order is wrong.

Approach: a stack of unmatched opening brackets

The rule "last opened, first closed" is the behaviour of a stack. Read the string from left to right:

An opening bracket cannot be checked yet, so push it on the stack.
A closing bracket must match the most recent unmatched opening bracket, which is the top of the stack. If the stack is empty, there is nothing to close and the string is invalid. If the top is a different type, it is invalid. Otherwise pop the top and continue.
At the end, the stack must be empty. Anything left on it was opened and never closed.

Trace "([)]": push (, push [. Then ) arrives and the top is [, whose partner is ], not ), so the answer is false. Trace "{[]}": push {, push [, ] matches the top [ and pops it, } matches { and pops it, and the stack ends empty, so the answer is true.

A lookup table from each opening bracket to its closing bracket keeps the matching test to one line, instead of a chain of comparisons.

A tempting alternative is to keep deleting adjacent pairs such as (), [] and {} from the string until nothing changes. It gives the right answer, but each deletion shifts the rest of the string, so it can take O(n²) time. The stack handles every character once.

Step by step

Build the table. An unordered_map<char, char> named closingBrackets maps ( to ), { to } and [ to ].
Create an empty stack<char>.
Loop over the characters of input with a range-based for.
Detect an opening bracket. A character is an opening bracket exactly when it is a key of the table, so closingBrackets.count(bracket) is 1 for opening brackets and 0 for closing ones.
Push it when it is an opening bracket.
Otherwise it is a closing bracket. If the stack is empty, return false: nothing is open to close.
Read, then remove, the top. In C++, pop() returns nothing, so copy top() into openBracket first and then call pop().
Compare. If the current bracket is not closingBrackets[openBracket], return false.
After the loop, return stack.empty().

The solution in C++

class Solution {
public:
	bool isValid(string input) {
        unordered_map<char, char> closingBrackets({
            {'(', ')'},
            {'{', '}'},
            {'[', ']'}
        });
        stack<char> stack;
    
        for (char bracket : input) {
            if (closingBrackets.count(bracket)) {
                stack.push(bracket);
            } else {
                if (stack.empty()) {
                    return false;
                }
                char openBracket = stack.top();
                stack.pop();
                if (bracket != closingBrackets[openBracket]) {
                    return false;
                }
            }
        }
    
        return stack.empty();
    }
};

The C++ details:

pop() returns void. That is why the code copies top() into a variable before popping. Calling top() or pop() on an empty stack is undefined behaviour, which is exactly what the stack.empty() check prevents.
The variable named stack hides the type name std::stack from that line to the end of the function. It compiles because the type is not needed again, but a name such as open avoids the confusion.
count as a condition. It returns 0 or 1 for a map, which converts to false or true. Writing closingBrackets[bracket] for the test would be a mistake, since [] inserts missing keys.
Passing by value. string input copies the string. For a long string, const string& avoids that, but the solution works either way.

Complexity

Time: O(n). Each character is handled once, and every stack operation and table lookup is O(1) on average.

Space: O(n). In the worst case, a string of only opening brackets puts all n characters on the stack.

Edge cases and common mistakes

A closing bracket first. "]" reaches the empty-stack check and returns false. Without that check, top() on an empty stack is undefined behaviour.
Unclosed brackets. "((" never fails inside the loop, but two brackets remain, so stack.empty() at the end returns false. Returning true straight after the loop would be wrong.
Odd length. A string with an odd number of characters can never be valid. Checking input.size() % 2 up front is an easy early exit, although the stack handles it anyway.
Counting instead of stacking. Counting opening and closing brackets of each type accepts "([)]". Order matters, which is why a stack is needed.
Empty string. The constraints promise at least one character; if an empty string is passed, the loop does not run and the function returns true.

Testing

"()" gives true.
"()[]{}" gives true.
"{[()]}" gives true.
"(]" gives false.
"([)]" gives false.
"(" and "]" both give false.

Keep going with C++About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free