Valid Parentheses - JS Solution

Editorial

Editorial solutions and visualizations are prepared with care, but we do not guarantee 100% accuracy or completeness. Please use your own judgment to verify results. Visucodize is not responsible for decisions made based on this content.

const CURRENT = 'current', CURRENT_COLOR = 'lightblue';

function visMainFunction(inputS) {
    initClassProperties();
    explanationAndColorSchemaNotifications();

    startBatch();
    const stack = new VisArray();
    const bracketMap = new VisObject({
        ')': '(',
        '}': '{',
        ']': '['
    });
    const s = new VisArray(...inputS);
    
    let charIndex = 0;
    makeVisVariable(charIndex).registerAsIndexPointer(s, CURRENT);
    endBatch();

    notification(`
        📘 <b>Initialization Summary:</b><br/>
        We set up key components for validating parentheses:
        <ul>
        <li><b><code>stack</code></b> → Used to store <b>opening brackets</b> ('(', '{', '[') as they appear.  
            When a closing bracket is found, we check whether it matches the latest opening one on the stack.</li>
        <li><b><code>bracketMap</code></b> → A mapping of <b>closing → opening</b> brackets:
            <code>{ ')': '(', '}': '{', ']': '[' }</code>.  
            It helps us quickly find the expected opening bracket for any closing bracket.</li>
        </ul>
        At this point, the <b>stack is empty</b> and ready to store opening brackets as we scan through <code>s</code>.
    `);

    for (const char of s) {
        startPartialBatch();

        if (char in bracketMap) {
            notification(`🧐 <b>Encountered a closing bracket:</b> ${makeColoredSpan(`"${char}"`, CURRENT_COLOR)}. Checking for a <b>matching opening bracket</b> on top of the stack...`);

            if (stack.length === 0) {
                notification(`❌ <b>Stack is empty!</b> There is no opening bracket available to match ${makeColoredSpan(`"${char}"`, CURRENT_COLOR)}. This means the string is invalid.`);
                validationFailNotification();
                return false;
            }

            const top = stack.pop();
            notification(`🔄 <b>Popped from stack:</b> "${top}". We <b>expected</b> "${bracketMap[char]}" to match the closing bracket ${makeColoredSpan(`"${char}"`, CURRENT_COLOR)}.`);

            if (top !== bracketMap[char]) {
                notification(`❌ <b>Mismatched pair!</b> The last opening bracket was "${top}", but ${makeColoredSpan(`"${char}"`, CURRENT_COLOR)} requires "${bracketMap[char]}".`);
                validationFailNotification();
                return false;
            }

            notification(`✅ <b>Matching brackets found!</b> "${top}" and ${makeColoredSpan(`"${char}"`, CURRENT_COLOR)} are a valid pair.`);
        } else {
            notification(`🆕 <b>Encountered an opening bracket:</b> ${makeColoredSpan(`"${char}"`, CURRENT_COLOR)}. Pushing it onto the stack.`);
            stack.push(char);
        }

        charIndex += 1;
        endBatch();
    }

    if (stack.length > 0) {
        notification(`❌ <b>Stack is not empty!</b> Some opening brackets were never closed, so the string is invalid.`);
        validationFailNotification();
        return false;
    }

    notification(`🏁 <b>Validation complete:</b> All brackets were properly opened and closed in order. ✅ The string is a <b>valid</b> parentheses sequence.`);
    return true;
}

function validationFailNotification() {
    notification(`🏁 <b>Validation complete:</b> The string is <b>NOT</b> a valid set of parentheses! ❌`);
}

function explanationAndColorSchemaNotifications() {
    explanationNotification();
    notification(`
        🎨 <b>Color Schema:</b><br/>
        <span class='${CURRENT}' style='background:${CURRENT_COLOR};color:black;'>${CURRENT_COLOR} background</span> → 
        Highlights the <b>current character</b> being processed in the input string.<br/>
    `);
}

function initClassProperties() {
    setClassProperties(CURRENT, {
        backgroundColor: CURRENT_COLOR
    });
}

Approach

To determine whether a string of brackets is valid, we need to verify two things:

Every opening bracket ((, {, [) is eventually closed by a matching closing bracket.
The brackets close in the correct order — no overlaps or mismatched nesting.

We use a stack to track currently “open” brackets, since the last bracket opened must always be the first one to close (LIFO order). Alongside it, we hold a mapping of closing to opening brackets: { ')': '(', '}': '{', ']': '[' }. This helps the algorithm instantly identify which opening type is expected when a closing bracket appears.

As we scan through the string:

When we see an opening bracket, we push it onto the stack. It stays there until a matching closing bracket appears later. The top of the stack always represents the most recent unclosed bracket.
When we see a closing bracket, we look at the top of the stack — the most recent opening.
- If the stack is empty, there’s no opening bracket to match — the string becomes invalid immediately.
- If the top doesn’t match the required opening bracket from our mapping, the pair is mismatched — invalid as well.
- If it matches, we pop it off the stack — that bracket pair is now successfully closed.

After processing the entire string, we check the stack:

If the stack is empty, all brackets were properly opened and closed — the string is valid.
If anything remains, it means there are unclosed openings — the string is invalid.

Why this works: The stack mirrors the natural nesting structure of brackets — every new opening must be closed before earlier ones can close. The mapping ensures each closing bracket is checked against the correct type of opening. Together, they guarantee both pairing correctness and order consistency, catching every possible invalid pattern.

Time Complexity

Let n be the length of the input string. We scan the string exactly once, performing constant-time operations for each character — either a push or a pop from the stack, plus a constant-time lookup in the mapping. Therefore, the time complexity is O(n).

Space Complexity

The algorithm uses:

A stack to store not yet matched opening brackets during scanning. In the worst case, all characters are opening brackets, so the stack can grow up to size n.
A fixed bracketMap storing the three bracket pairs ({ ')': '(', '}': '{', ']': '[' }), which takes O(1) space.

Therefore, the total auxiliary space complexity is O(n) in the worst case.

Input-1

Valid Parentheses - JS Solution

Solution code

Solution explanation

Solution explanation

Approach

Time Complexity

Space Complexity