Start learning free

LESSON 297 OF 348 · STACK

Valid Parentheses in TypeScript: 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

    TYPESCRIPT · STACK

    Valid Parentheses in TypeScript, explained

    Problem overview

    The method isValid receives a string, input, 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 right order.

    Some examples:

    • "()", "()[]{}" and "{[]}" are valid.
    • "(]" is not: the ( is closed by the wrong type.
    • "([)]" is not: both pairs have the right types, but they cross. The ( would have to close before the [ that was opened after it.

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

    Approach: the latest opening bracket must close first

    Counting brackets isn't enough, because "([)]" has equal counts of every type and is still invalid. What matters is order. When a closing bracket arrives, it has to match the most recent opening bracket that is still open. That is exactly the last-in, first-out rule of a stack.

    So the scan works like this:

    • On an opening bracket, push it on the stack. It waits for its partner.
    • On a closing bracket, pop the top of the stack and check that this opening bracket is the right partner. If the stack is empty, or the partner is wrong, the string is invalid.
    • At the end, the stack must be empty. Anything left was opened and never closed.

    On "{[]}": push {, push [. The ] pops [, which matches. The } pops {, which matches. The stack is empty, so the result is true. On "([)]": push (, push [. The ) pops [, whose partner is ], not ), so the result is false right away.

    Step by step

    1. Map each opening bracket to its closing bracket. The object closingBrackets is typed { [key: string]: string }, an index signature meaning any string key maps to a string value. Its three entries are ( to ), { to } and [ to ].
    2. Create the stack: an empty string[]. Its last element is the top, since push and pop work at the end of an array.
    3. Loop over the characters with for (const bracket of input).
    4. Detect opening brackets. The test bracket in closingBrackets is true exactly when the character is a key, which means it is an opening bracket.
    5. Push it onto the stack.
    6. Otherwise it is a closing bracket. The else branch handles it.
    7. Guard against an empty stack. If stack.length === 0, return false: there is no opening bracket for this one to close.
    8. Pop the partner into openBracket with pop()!. The exclamation mark tells TypeScript the value isn't undefined, which the empty check above guarantees.
    9. Compare. If bracket is not closingBrackets[openBracket], return false, because the types don't match.
    10. Check what is left. After the loop, return stack.length === 0. Leftover opening brackets make the string invalid.

    The solution in TypeScript

    class Solution {
    isValid(input: string): boolean {
        const closingBrackets: { [key: string]: string } = {
            "(": ")",
            "{": "}",
            "[": "]",
        };
        const stack: string[] = [];

        for (const bracket of input) {
            if (bracket in closingBrackets) {
                stack.push(bracket);
            } else {
                if (stack.length === 0) {
                    return false;
                }
                const openBracket = stack.pop()!;
                if (bracket !== closingBrackets[openBracket]) {
                    return false;
                }
            }
        }

        return stack.length === 0;
    }
}

    The TypeScript details worth a closer look:

    • for...of on a string. It visits the string one character at a time, which is why bracket is a one-character string. A for...in loop would give indexes instead.
    • The in operator tests keys. "(" in closingBrackets is true, and ")" in closingBrackets is false, because ) is a value, not a key. One caution: in also finds inherited names such as "toString". That doesn't matter here, since the input has only bracket characters.
    • The index signature. { [key: string]: string } describes an object with any number of string keys, each holding a string. That lets closingBrackets[openBracket] use a variable as the key, and it is typed string.
    • Non-null assertion. With strict null checking on, pop() is typed string | undefined, and ! removes the undefined part for the compiler. It's an assurance, not a check: at run time, an empty array still gives undefined. The stack.length === 0 check above it is what makes the code safe.
    • Strict comparison. !== compares two strings without conversion.
    • Trailing comma. The last entry of the object literal ends with a comma. That is allowed and makes adding entries cleaner.

    Complexity

    Time: O(n). Each character is looked at once. Pushing, popping, the key test and the object lookup are all constant time on average.

    Space: O(n). In the worst case, such as a string made only of opening brackets, the stack holds every character. The object has three entries, which is O(1).

    Edge cases and common mistakes

    • Only a closing bracket. ")" hits the empty-stack check and returns false immediately.
    • Only opening brackets. "((" passes the loop and fails the final test: the stack still holds two items.
    • Crossed pairs. "([)]" is the reason the type check on the popped bracket exists. Counting only the number of each bracket would accept it.
    • Same count, wrong order. ")(" has one of each, but the closing bracket comes first, so the stack is empty when it arrives.
    • Forgetting the final check. Returning true at the end of the loop would accept "(((".
    • Popping before the empty check. On an empty array, pop() gives undefined, and the comparison afterwards would look up closingBrackets[undefined], which isn't a bracket. The empty check comes first for a reason.
    • An empty string. The constraints say the input has at least one character, but the code would return true for "", since nothing is left open.

    Testing

    • "()" gives true.
    • "()[]{}" gives true.
    • "(]" gives false.
    • "([)]" gives false.
    • "{[]}" gives true.
    • "((" gives false, and ")" gives false.
    Keep going with TypeScriptAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free