Start learning free

LESSON 296 OF 347 · STACK

Valid Parentheses in C#: O(n) with a Stack

Practice O(n) Read the full explanation

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

An input string is valid if:

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

Example 1:

Input: s = "()"
Output: true

Example 2:

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

Example 3:

Input: s = "(]"
Output: false

Example 4:

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

Example 5:

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

Constraints:

  • 1 <= s.length <= 104
  • s consists of parentheses only '()[]{}'.

Note:

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


STEP 1 OF 10
    Ctrl + Enter to check

    C# · STACK

    Valid Parentheses in C#, explained

    Problem overview

    The method IsValid receives a string made only of the six characters (, ), {, }, [ and ]. It returns true when the brackets are balanced and false otherwise. Balanced means two things: every opening bracket is closed by a bracket of the same type, and brackets are closed in the correct order, so the most recently opened one is closed first.

    Some examples:

    • "()", "()[]{}" and "{[]}" are valid.
    • "(]" is invalid because the types don't match.
    • "([)]" is invalid because the order is wrong: the [ is still open when the ) tries to close the ( behind it.

    The lesson asks for O(n) time and O(n) extra space.

    Approach: remember the open brackets in a stack

    Read the string from left to right. An opening bracket is a promise: some matching closing bracket has to arrive later. A closing bracket can only fulfil the latest promise that is still open, since anything older is wrapped around it. "Latest first" is the last in, first out behaviour of a stack.

    So the algorithm is:

    • On an opening bracket, push it onto the stack.
    • On a closing bracket, pop the top of the stack. If the stack is empty, or the popped bracket is of a different type, the string is invalid.
    • At the end, the string is valid only if the stack is empty. Anything left over is an opening bracket that was never closed.

    Here is "{[]}". The characters { and [ are pushed. The ] pops [, which matches. The } pops {, which matches. The stack is empty at the end, so the result is true.

    Now "([)]". The characters ( and [ are pushed. The ) pops [, but [ needs a ], so the method returns false right there.

    Step by step

    1. Build a lookup table. A Dictionary<char, char> named closingBrackets maps each opening bracket to its closing partner. A collection initializer fills it as it is created.
    2. Create the stack. A Stack<char> named stack holds the opening brackets that are still waiting.
    3. Iterate over the characters. A foreach loop over input.ToCharArray() visits each bracket.
    4. Classify the character. The dictionary's keys are exactly the opening brackets, so ContainsKey(bracket) tells whether the character opens something.
    5. Push openers. In that case, Push the bracket on the stack.
    6. Handle closers in the else branch. Anything that is not an opener is a closing bracket.
    7. Reject a closer with nothing open. If stack.Count == 0, return false.
    8. Pop the latest opener into openBracket. It is the only bracket this closer is allowed to close.
    9. Check the pair. If bracket is not closingBrackets[openBracket], return false.
    10. Check for leftovers. After the loop, return stack.Count == 0.

    The solution in C#

    class Solution {
    public bool IsValid(string input) {
        Dictionary<char, char> closingBrackets = new Dictionary<char, char>() {
            { '(', ')' },
            { '{', '}' },
            { '[', ']' }
        };
        Stack<char> stack = new Stack<char>();

        foreach (char bracket in input.ToCharArray()) {
            if (closingBrackets.ContainsKey(bracket)) {
                stack.Push(bracket);
            } else {
                if (stack.Count == 0) {
                    return false;
                }
                char openBracket = stack.Pop();
                if (bracket != closingBrackets[openBracket]) {
                    return false;
                }
            }
        }

        return stack.Count == 0;
    }
}

    Some C# details to notice:

    • The collection initializer. Each { '(', ')' } inside the braces is a key and a value, and C# turns it into a call to Add. Characters use single quotes. Double quotes would make strings, which are a different type.
    • Indexing a dictionary. closingBrackets[openBracket] returns the value for a key, and throws a KeyNotFoundException if the key is absent. It is safe here because only keys of the dictionary are ever pushed on the stack.
    • Empty-stack errors. Pop() on an empty Stack<char> throws an InvalidOperationException. The check on stack.Count comes first for that reason.
    • Comparing characters. != on two char values compares the characters themselves.
    • Looping over characters. A string can be used in foreach directly, so input.ToCharArray() only makes an extra copy. The lesson's form works the same way.
    • The method name. The method is called IsValid with a capital I, and the parameter is called input. C# is case-sensitive, so use the names from the editor.
    • Returning a comparison. return stack.Count == 0; returns the bool that the comparison produces, replacing a longer if/else.

    Complexity

    Time: O(n). Each character is handled once, and a push, a pop, a dictionary lookup and a comparison each take constant time.

    Space: O(n). In the worst case, such as a string of only opening brackets, the stack holds every character. The array from ToCharArray() also takes O(n).

    Edge cases and common mistakes

    • Only a closing bracket. For ")" the stack is empty when the closer arrives, so the answer is false. Skipping the empty check would make Pop() throw.
    • Only an opening bracket. For "(" the loop ends with one bracket on the stack. Returning true without checking the stack is a classic bug.
    • Right counts, wrong order. "([)]" has one bracket of each kind opened and closed, yet it is invalid. Counting brackets is not enough, and the stack is what catches it.
    • Mismatched types. "(]" fails at the pair check, not at the empty check.
    • An empty string. The loop never runs and the stack is empty, so the method returns true. The constraints guarantee at least one character, but the logic handles it.
    • Pushing the closing bracket instead. Some solutions push the expected closer and compare on pop. That also works, but keep the lesson's convention when you follow its steps.

    Testing

    • "()" gives true.
    • "()[]{}" gives true.
    • "{[]}" gives true.
    • "(]" gives false.
    • "([)]" gives false.
    • "(" gives false.
    • ")" gives 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