Valid Parentheses

return true if parentheses are valid

Valid Parentheses

Problem

You are given a string s that has only these characters: (, ), {, }, [ and ]. Check if the string is valid.

A string is valid if:

• Every open bracket is closed by the same type of bracket.
• Open brackets are closed in the correct order.
• Every close bracket has a matching open bracket of the same type.

Examples

Example 1

Input: s = "()"
Output: true

Example 2

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

Example 3

Input: s = "(]"
Output: false

• The open bracket ( is closed by ], which is the wrong type.

Example 4

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

• [] is closed first, and then () is closed. The order is correct.

Example 5

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

• The bracket [ is still open, but we try to close ( first. The order is wrong.

Constraints

• 1 <= s.length <= 10^4
• s has only the characters ()[]{}.

Main Idea

The last open bracket must be closed first. This is the LIFO rule, so a stack is a perfect fit.

We read the string from left to right:

• Open bracket ((, [ or {): Push it on the stack. It is waiting for its closing bracket.
• Close bracket (), ] or }): Look at the top of the stack.
  • If the top is the matching open bracket, pop it. The pair is done.
  • If not, the string is invalid.

At the end, the stack must be empty. If it is not, some open brackets never got closed.

Stack Class Used in the Solution

class Stack {
    constructor() {
        this.items = [];
    }

    push(element) {
        this.items.push(element);
    }

    pop() {
        if (this.isEmpty()) return "Stack Underflow";
        return this.items.pop();
    }

    // returns null when the stack is empty
    peek() {
        return this.isEmpty() ? null : this.items[this.items.length - 1];
    }

    isEmpty() {
        return this.items.length === 0;
    }
}

Solution: Stack

var isValid = function (s) {
    let stack = new Stack();

    for (let i = 0; i < s.length; i++) {
        let str = s[i];

        if (str == '(' || str == '[' || str == '{') {
            // open bracket, so push it
            stack.push(str);
        } else if (!stack.isEmpty()) {
            // close bracket, and the stack has an open bracket
            let peek = stack.peek();

            if (
                (str == ')' && peek == '(') ||
                (str == '}' && peek == '{') ||
                (str == ']' && peek == '[')
            ) {
                // matching pair, so remove it
                stack.pop();
            } else {
                // Return false #1: wrong type of bracket
                return false;
            }
        } else {
            // Return false #2: no open bracket to match
            return false;
        }
    }

    // valid only if no open bracket is left
    return stack.isEmpty() ? true : false;
};

Why There Are Two return false Statements

Inside the loop, a close bracket can fail in two different ways. Each one has its own return false.

Return false #1: Wrong bracket on top

This is inside the else if (!stack.isEmpty()) block, in the inner else.

• When it happens: The current character is a close bracket, and the stack has an open bracket on top. But the top is not the matching type.
• What it handles: Wrong type, or wrong order.
• Example: s = "(]"
  • ( is pushed.
  • ] comes. The top is (, but ] needs [. So we return false.
• Example: s = "([)]"
  • ( and [ are pushed.
  • ) comes. The top is [, but ) needs (. So we return false.

This rule covers the first two conditions of the problem: same type and correct order.

Return false #2: Close bracket with an empty stack

This is in the last else of the if chain.

• When it happens: The current character is a close bracket, but the stack is empty. There is no open bracket to match.
• What it handles: An extra close bracket.
• Example: s = ")"
  • The stack is empty, and ) comes. There is nothing to match. So we return false.
• Example: s = "())"
  • ( is pushed, and the first ) removes it.
  • The second ) comes, and the stack is empty. So we return false.

This rule covers the third condition: every close bracket needs an open bracket.

Why we cannot skip the empty check

• If we call peek() on an empty stack, we get null. That would be treated as a mismatch anyway, but checking isEmpty() first makes the reason clear.
• We also need a separate case so that the code never tries to pop() from an empty stack.

The final check

After the loop, we do stack.isEmpty() ? true : false.

• When it matters: The string has extra open brackets that never got closed.
• Example: s = "(("
  • Both ( are pushed, and no close bracket comes.
  • The loop ends without any return false. But the stack still has 2 items, so the answer is false.

Summary of all three failure cases

How the Code Works

Step 1: Create the stack

• stack keeps the open brackets that are still waiting for a close bracket.

Step 2: Read each character

• If it is an open bracket, we push it.
• If it is a close bracket and the stack is not empty, we compare it with the top.
  • It matches: pop.
  • It does not match: return false.
• If it is a close bracket and the stack is empty, we return false.

Step 3: Check the stack at the end

• An empty stack means every open bracket was matched. The string is valid.

Dry Run

Let us take s = "([])".

The stack is empty, so the answer is true.

Now let us take s = "([)]".

The answer is false.

Complexity

• Time Complexity: O(n)
  • n is the length of the string.
  • Each character is pushed at most once and popped at most once.
• Space Complexity: O(n)
  • In the worst case, all characters are open brackets, so the stack holds n items.

Shorter Version (Optional)

We can use a map of close brackets to open brackets. Then we can merge both return false cases into one check.

var isValid = function (s) {
    let stack = [];
    let pairs = { ')': '(', ']': '[', '}': '{' };

    for (let ch of s) {
        if (ch in pairs) {
            // close bracket: the top must be its matching open bracket
            // (an empty stack gives undefined, which never matches)
            if (stack.pop() !== pairs[ch]) {
                return false;
            }
        } else {
            // open bracket
            stack.push(ch);
        }
    }

    return stack.length === 0;
};

• Here, stack.pop() on an empty stack gives undefined. It never equals an open bracket, so both failure cases are handled by one if.

Complexity

• Time Complexity: O(n)
• Space Complexity: O(n)

Comparison

Summary

• The last open bracket must be closed first, so we use a stack.
• Open brackets are pushed. Close brackets are checked against the top.
• There are two return false cases inside the loop:
  • #1: The top is the wrong type of bracket (wrong type or wrong order).
  • #2: The stack is empty, so the close bracket has no partner.
• The final stack.isEmpty() check catches open brackets that were never closed.
• The solution runs in O(n) time and uses O(n) space.