LESSON 317 OF 410 · STACK

Valid Parentheses in JavaScript: O(n) with a Stack

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

JAVASCRIPT · STACK

Valid Parentheses in JavaScript, explained

Problem overview

The method isValid(input) receives a string made only of the characters (, ), {, }, [ and ]. It returns true when the brackets are balanced and false otherwise. Two rules define balanced:

every opening bracket is closed by a bracket of the same type;
brackets are closed in the right order: the most recently opened one must be closed first.

So "()", "()[]{}" and "{[]}" are valid. "(]" is invalid because the types differ, and "([)]" is invalid because the ) arrives while the [ opened after the ( is still open. The string has between 1 and 10,000 characters, and the lesson asks for O(n) time and O(n) extra space.

Approach: a stack of open brackets

Reading the string left to right, the closing bracket you meet must always match the most recent opening bracket that is still open. "Most recent first" is exactly how a stack behaves: the last item pushed is the first one popped. So:

on an opening bracket, push it on the stack;
on a closing bracket, pop the top of the stack and check that it is the matching opener;
at the end, the stack must be empty, otherwise some bracket was never closed.

Counting brackets of each type is not enough. "([)]" has one of each, yet it is invalid, because the order is wrong. Only a structure that remembers the order of the open brackets catches this. Compare with scanning for adjacent pairs like () and deleting them repeatedly: that also works, but it rescans the string many times and can take O(n²). The stack does it in a single pass.

Trace "{[]}": { is pushed, so the stack holds {. Then [ is pushed and the stack holds { [. The ] pops [, which matches. The } pops {, which matches. The stack is empty at the end, so the answer is true. Trace "([)]": after ( and [ the stack holds ( [. The ) pops [, which does not match ), so the answer is false immediately.

Step by step

Map each opener to its closer. An object closingBrackets with the pairs ( to ), { to } and [ to ] answers two questions at once: its keys are the opening brackets, and its values are what must close them.
Create the stack as an empty array. push and pop work at the end of an array, so the last element is the top of the stack.
Loop over the characters of input with for...of, which visits a string one character at a time.
Test for an opener with the in operator: bracket in closingBrackets is true only when the character is one of the keys.
Push openers. They wait on the stack until their closer arrives.
Handle a closer in the else branch. First, if the stack is empty, return false: there is nothing for this closer to close.
Pop the most recent opener into openBracket. It is the only bracket this closer is allowed to close.
Compare. Look up closingBrackets[openBracket], the one bracket that may close it. If the current character differs, return false.
After the loop, return whether the stack is empty. Any opener left over was never closed. The comparison stack.length == 0 is already a boolean, so it is returned directly.

The solution in JavaScript

class Solution {
    isValid(input) {
        let closingBrackets = {
            "(": ")",
            "{": "}",
            "[": "]"
        };
        let stack = [];
    
        for (let bracket of input) {
            if (bracket in closingBrackets) {
                stack.push(bracket);
            } else {
                if (stack.length == 0) {
                    return false;
                }
                let openBracket = stack.pop();
                if (bracket != closingBrackets[openBracket]) {
                    return false;
                }
            }
        }
    
        return stack.length == 0;
    }
}

Some JavaScript details:

An array works as a stack. push adds to the end and pop removes and returns the last element, both in constant time. Calling pop() on an empty array returns undefined without an error, so the explicit empty check before it is what makes the closer-first case return false cleanly.
The in operator tests keys, not values. "(" in closingBrackets is true and ")" in closingBrackets is false, since ")" is a value. This is what separates openers from closers. It also looks up inherited properties, so "toString" in closingBrackets is true. That does not matter here, because the input only has bracket characters, but with arbitrary text a Map and has, or Object.hasOwn, would be safer.
for...of over a string gives one character at a time, as a one-character string. for...in would give the indices instead.
Object literal syntax. The brackets are keys, so they are written as strings: "(". The quotes are required, because these characters are not valid identifiers.

Complexity

Each character is looked at once, and every push, pop and lookup takes constant time, so the time is O(n). In the worst case, such as a string of only openers, the stack grows to hold up to n characters, so the extra space is O(n).

Edge cases and common mistakes

Only openers. "((" never fails inside the loop, and is rejected only by the final check. Without that last stack.length == 0, it would wrongly return true.
A closer first. "]" or "))" must return false from the empty-stack check. Without it, pop() returns undefined, and the lookup closingBrackets[undefined] is also undefined. The comparison would then correctly fail here, but only by accident, and relying on it is fragile.
Right counts, wrong order. "([)]" shows why counting each bracket type is not enough.
Odd length. A string with an odd number of characters can never be valid. You can return false at once as a shortcut, though the stack handles it without special code.

Testing

Try these in the editor:

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

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

Start learning free