LeetCode 20: Valid Parentheses in C++ Using a Stack

Disclaimer

This article is an independent educational explanation of a programming problem originally published on LeetCode. The original problem statement, examples, constraints, trademarks, and related materials belong to LeetCode and their respective rights holders.

The real-world scenario is a hypothetical educational adaptation and does not represent a confirmed company process unless explicitly stated with a reliable source.

The solution, explanation, and code are for learning and reference. Other valid approaches may exist. Readers should verify current requirements on the original LeetCode page.

Article Summary

The Valid Parentheses problem asks us to determine whether every opening bracket in a string is closed by the correct bracket type and in the correct order.

The key observation is that nested brackets must be closed in reverse order. The most recently opened bracket must be the first one closed. This behavior matches a stack, which is a Last-In, First-Out data structure.

This article explains how to recognize the stack pattern, validate bracket pairs, prove that the algorithm works, and calculate the correct time and space complexity.

Original Problem and Credit

This article is based on the LeetCode problem “20. Valid Parentheses.”

• Original problem: https://leetcode.com/problems/valid-parentheses/
• Platform: LeetCode
• Original problem, examples, and constraints credit: LeetCode
• Explanation, adaptation, analysis, and commentary: Andy

The original problem statement is summarized and adapted rather than reproduced in full.

Real-World Scenario

Imagine a hypothetical document-processing service that validates nested formatting scopes before accepting a document.

The service recognizes three types of formatting boundaries:

• ( and ) represent a comment scope.
• [ and ] represent a metadata scope.
• { and } represent a configuration scope.

Every scope must be closed using the same boundary type that opened it. Nested scopes must also be closed from the inside out.

For example:

([])

This sequence represents a comment scope containing a metadata scope.

The metadata scope must close before the surrounding comment scope because it was opened more recently.

However, the following sequence is invalid:

([)]

The comment scope attempts to close while the metadata scope is still open.

This scenario is hypothetical, but it preserves the exact input, output, ordering rules, edge cases, and constraints of the original problem.

Examples

Example 1

Input: s = "()"
Output: true

The opening parenthesis is closed by the matching closing parenthesis.

Example 2

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

Every opening bracket has a matching closing bracket, and all pairs are closed in the correct order.

Example 3

Input: s = "(]"
Output: false

The opening parenthesis cannot be closed by a square bracket.

Example 4

Input: s = "([])"
Output: true

The square brackets are correctly nested inside the parentheses.

Example 5

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

The bracket types are present in matching quantities, but they are closed in the wrong order.

Constraints

1 <= s.length <= 10^4

The string contains only the following characters:

()[]{}

Mapping to the Original Problem

The names are different, but the validation rules remain mathematically identical.

Solution Intuition

Recognizing the Ordering Pattern

Suppose two scopes are opened in the following order:

Open A
Open B

Because scope B is nested inside scope A, they must be closed in reverse order:

Close B
Close A

The most recently opened scope must always be the next one closed.

This is a Last-In, First-Out, or LIFO, pattern.

A stack is a data structure designed for LIFO behavior:

• push adds an element to the top.
• top examines the most recently added element.
• pop removes the most recently added element.

A queue would not work because a queue follows First-In, First-Out, or FIFO, behavior. It would process the oldest opening bracket first instead of the most recent one.

What the Stack Stores

Whenever we encounter an opening bracket, we push it onto the stack.

The top of the stack represents the opening bracket that must be closed next.

For example, after reading:

([

the stack contains:

Bottom: (
Top:    [

The square bracket must close before the parenthesis.

Processing a Closing Bracket

When we encounter a closing bracket, two conditions must be satisfied:

1. The stack must not be empty.
2. The opening bracket at the top of the stack must match the closing bracket.

For example:

Closing bracket: ]
Required opening bracket: [

A hash map can store the three matching relationships:

')' -> '('
']' -> '['
'}' -> '{'

This allows the algorithm to retrieve the expected opening bracket for each closing bracket.

If the stack is empty, the closing bracket does not have a corresponding opening bracket.

If the stack top does not match the expected opening bracket, the nesting order or bracket type is invalid.

Final Validation

Finding no mismatch during the loop is not enough.

Consider:

(((

No incorrect closing bracket appears, but all three opening brackets remain unmatched.

Therefore, the string is valid only when the stack is empty after every character has been processed.

Algorithm

1. Create an empty stack to store unmatched opening brackets.
2. Create a mapping from every closing bracket to its matching opening bracket.
3. Process each character in the string:
   1. If the character is an opening bracket, push it onto the stack.
   2. Otherwise, the character is a closing bracket:
      • Return false if the stack is empty.
      • Return false if the stack top is not the matching opening bracket.
      • Otherwise, pop the matching opening bracket from the stack.
4. After processing every character, return whether the stack is empty.

Why the Algorithm Works

The main invariant is:

After processing any prefix of the string, the stack contains exactly the opening brackets that have not yet been matched, ordered by when they must be closed.

When the algorithm encounters an opening bracket, that bracket becomes the most recently opened unmatched bracket. Pushing it onto the stack preserves the invariant.

When the algorithm encounters a closing bracket, it must match the opening bracket at the top of the stack. The stack top is the most recently opened unmatched bracket, so it must be closed before any earlier bracket.

If the closing bracket matches, popping the stack removes one correctly completed pair and preserves the invariant.

If the stack is empty when a closing bracket appears, there is no available opening bracket for it. Therefore, the string is invalid.

If the stack top has a different bracket type, the brackets are being closed with the wrong type or in the wrong order. Therefore, the string is invalid.

After the entire string has been processed:

• An empty stack means every opening bracket was matched correctly.
• A nonempty stack means at least one opening bracket was never closed.

Therefore, the algorithm returns true exactly when the input string is valid.

Complexity Analysis

Let n be the number of characters in the input string s.

Time Complexity

The algorithm processes each character exactly once.

For every character, it performs a constant number of operations:

• Opening-bracket comparisons
• A stack push, top, or pop
• An average-case O(1) hash-map lookup

Each stack operation takes O(1) time.

Therefore, the total time complexity is:

O(n)

An opening bracket may be pushed and later popped, but Big-O notation ignores constant factors. The final complexity is O(n), not O(2n).

Space Complexity

The hash map always stores exactly three bracket mappings, so it uses constant space:

O(1)

However, the stack can contain up to n opening brackets.

For example:

(((((((((

Every character is pushed onto the stack, and none are removed before the loop finishes.

Therefore, the stack requires O(n) auxiliary space in the worst case.

The total auxiliary space complexity is:

O(n)

The stack is the largest input-dependent data structure, so the constant-size hash map does not change the final result.

Corrected Solution

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

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

        const std::unordered_map<char, char> bracketDictionary = {
            {')', '('},
            {']', '['},
            {'}', '{'}
        };

        for (char currentBracket : s) {
            if (currentBracket == '(' ||
                currentBracket == '[' ||
                currentBracket == '{') {
                st.push(currentBracket);
                continue;
            }

            if (st.empty() ||
                st.top() != bracketDictionary.at(currentBracket)) {
                return false;
            }

            st.pop();
        }

        return st.empty();
    }
};

Walkthrough

Consider the following input:

s = "([])"

The stack begins empty.

The stack is empty after all characters have been processed.

Therefore:

Output: true

Now consider:

s = "([)]"

The closing parenthesis cannot close the outer parenthesis while the inner square bracket remains open.

Therefore:

Output: false

Common Mistakes

Using a Queue Instead of a Stack

Nested structures must close in reverse order.

A queue processes the oldest opening bracket first, which is the opposite of the required behavior.

Accessing the Stack Top Before Checking Whether It Is Empty

The following code is unsafe:

if (st.top() != expectedBracket) {
    return false;
}

If the input begins with a closing bracket, the stack is empty and calling top() is invalid.

The empty check must come first:

if (st.empty() || st.top() != expectedBracket) {
    return false;
}

C++ uses short-circuit evaluation. When st.empty() is true, the expression after || is not evaluated, so st.top() is not called.

Returning true Without Checking the Final Stack

Consider:

(((

No mismatched closing bracket appears, but the opening brackets are never closed.

The algorithm must finish with:

return st.empty();

Checking Only the Number of Brackets

Having equal numbers of opening and closing brackets is not sufficient.

For example:

([)]

contains one opening and one closing bracket of each type, but the nesting order is invalid.

Popping Before Checking the Bracket Type

The algorithm must compare the closing bracket with the stack top before removing anything.

Popping first could discard the opening bracket needed to identify an invalid match.

Key Takeaways

• Nested structures commonly indicate a stack-based solution.
• A stack follows Last-In, First-Out order, while a queue follows First-In, First-Out order.
• The stack top represents the opening bracket that must be closed next.
• A closing bracket is invalid when the stack is empty or the stack top has the wrong type.
• The solution runs in O(n) time and uses O(n) auxiliary space in the worst case.