Validate Balanced Brackets — Problem Statement & Solution Guide

StackMediumMixed

TimeO(n)

SpaceO(n)

Problem Description

You are tasked with verifying the structural integrity of a sequence of delimiters. Given a string s composed exclusively of the characters '(', ')', '{', '}', '[', and ']', determine whether the sequence is syntactically balanced. A sequence is considered balanced if and only if every opening delimiter is matched by a closing delimiter of the same type, and these pairs are properly nested without any interleaving or mismatched ordering. Specifically, a closing bracket must always correspond to the most recent unmatched opening bracket of the same kind. If at any point a closing bracket appears without a corresponding open bracket, or if the types do not match, the sequence is invalid. Additionally, any remaining unmatched opening brackets at the end of the string render the sequence invalid. Your function should return true if the string is valid, and false otherwise.

DSA Pattern Breakdown

"Validate Balanced Brackets"

medium

WHY DOES IT MATTER?

Balanced‑bracket validation is a fundamental pattern for parsing nested structures, such as expressions, HTML/XML tags, and programming language syntax. Mastery of this pattern demonstrates a candidate's ability to model hierarchical constraints using appropriate data structures.

OPTIMIZATION CHALLENGE

The key insight is recognizing that only the most recent unmatched opening bracket matters at any point, allowing us to discard all earlier context once it is matched, which collapses a potentially quadratic comparison into a linear scan with constant‑time stack operations.

REAL-WORLD CONNECTION

Compilers use a similar stack‑based mechanism to ensure that scopes, parentheses, and block delimiters are correctly nested, while distributed transaction systems track nested compensation actions using a stack to unwind operations on failure.

During an interview, write the mapping of closing to opening brackets early, and always check for an empty stack before peeking; this prevents null‑pointer errors and makes the code robust for edge cases like "}" or "()[]}".

COMPLEXITY AT A GLANCE

⏱ Time:O(n)

💾 Space:O(n)

Core Theory — Why This Approach?

The balanced‑brackets problem is a classic example of using a stack to enforce a last‑in‑first‑out (LIFO) ordering constraint. When scanning the string from left to right, each opening delimiter is pushed onto the stack, and each closing delimiter must match the type of the delimiter on the top of the stack; otherwise the sequence is invalid. This works because a well‑formed expression requires that the most recent unmatched opening bracket be closed before any earlier ones, which is exactly the property a stack provides.\n\nA naive approach might attempt to compare every opening bracket with every later closing bracket, leading to O(n^2) time and complicated bookkeeping, which quickly becomes infeasible for long inputs (e.g., strings of length 10^5). The optimal paradigm leverages the stack to achieve linear time: each character is processed once, and each push or pop operation is O(1). This reduces both time and auxiliary space to the minimum required for the problem, making the solution scalable for large inputs.

Interview Questions on This Problem

Q1How would you modify the algorithm to also return the index of the first mismatched bracket?

Maintain the current index while iterating; when a mismatch occurs (either a closing bracket with an empty stack or a type mismatch), immediately return that index. If the loop finishes with a non‑empty stack, return the index of the top element, which is the first unmatched opening bracket.

Q2Can you solve the balanced brackets problem without using extra space?

Only if the input is mutable and you can overwrite characters; you could simulate a stack by using two pointers and rewriting the string in‑place, but this sacrifices readability and is generally not recommended for interview settings where O(n) auxiliary space is acceptable.

Q3What is the time and space complexity if the input string contains only one type of bracket, e.g., only '(' and ')', and you pre‑compute a prefix sum?

Using a prefix sum you can achieve O(n) time and O(1) extra space by tracking the net count of '(' minus ')'; the sequence is balanced if the count never goes negative and ends at zero. However, this technique fails for multiple bracket types, which is why the stack remains the universal solution.

Examples

Example 1

Input

s = "([{}])"

Output

true

Explanation: 1. Push '(' onto stack. Stack: ['(']. 2. Push '[' onto stack. Stack: ['(', '[']. 3. Push '{' onto stack. Stack: ['(', '[', '{']. 4. Encounter '}'. Top is '{', which matches. Pop '{'. Stack: ['(', '[']. 5. Encounter ']'. Top is '[', which matches. Pop '['. Stack: ['(']. 6. Encounter ')'. Top is '(', which matches. Pop '('. Stack: []. 7. Stack is empty at the end. Return true.

Example 2

Input

s = "(]"

Output

false

Explanation: 1. Push '(' onto stack. Stack: ['(']. 2. Encounter ']'. Top is '(', which does not match ']'. Return false immediately.

Example 3

Input

s = "{[()]}"

Output

true

Explanation: 1. Push '{'. Stack: ['{']. 2. Push '['. Stack: ['{', '[']. 3. Push '('. Stack: ['{', '[', '(']. 4. Encounter ')'. Matches '('. Pop. Stack: ['{', '[']. 5. Encounter ']'. Matches '['. Pop. Stack: ['{']. 6. Encounter '}'. Matches '{'. Pop. Stack: []. 7. Stack is empty. Return true.

Example 4

Input

s = "(("

Output

false

Explanation: 1. Push '('. Stack: ['(']. 2. Push '('. Stack: ['(', '(']. 3. End of string reached. Stack is not empty. Return false.

Constraints

1 <= s.length <= 10^5
s consists only of the characters '(', ')', '{', '}', '[' and ']'
The string length is always odd or even, but validity depends on pairing, not length parity alone

Optimal Approach & Strategy

Use a stack to push opening brackets and pop when a matching closing bracket appears, processing each character exactly once. This yields O(n) time with O(n) auxiliary space for the stack.

Brute Force Approach

A naive method would compare each opening bracket with every later closing bracket to find a match, leading to nested loops. This results in O(n^2) time and is impractical for long strings.

Verified Code Solutions

Language:

JavaScript Solution

Time: O(n)

function isValid(s) {
    const stack = [];
    const map = { ')': '(', '}': '{', ']': '[' };
    for (let char of s) {
        if (char in map) {
            if (stack.length === 0 || stack.pop() !== map[char]) {
                return false;
            }
        } else {
            stack.push(char);
        }
    }
    return stack.length === 0;
}

#include <stack>
#include <string>

class Solution {
public:
    bool isValid(std::string s) {
        std::stack<char> st;
        for (char c : s) {
            if (c == '(' || c == '{' || c == '[') {
                st.push(c);
            } else {
                if (st.empty()) return false;
                char top = st.top();
                st.pop();
                if ((c == ')' && top != '(') ||
                    (c == '}' && top != '{') ||
                    (c == ']' && top != '[')) {
                    return false;
                }
            }
        }
        return st.empty();
    }
};

import java.util.Stack;

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            if (c == '(' || c == '{' || c == '[') {
                stack.push(c);
            } else {
                if (stack.isEmpty()) return false;
                char top = stack.pop();
                if ((c == ')' && top != '(') ||
                    (c == '}' && top != '{') ||
                    (c == ']' && top != '[')) {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }
}

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        mapping = {")": "(", "}": "{", "]": "["}
        for char in s:
            if char in mapping:
                top_element = stack.pop() if stack else '#'
                if mapping[char] != top_element:
                    return False
            else:
                stack.append(char)
        return not stack

function isValid(s) {
    const stack = [];
    const map = { ')': '(', '}': '{', ']': '[' };
    for (let char of s) {
        if (char in map) {
            if (stack.length === 0 || stack.pop() !== map[char]) {
                return false;
            }
        } else {
            stack.push(char);
        }
    }
    return stack.length === 0;
}

Asked in Top Tech Interviews

stacks-and-queuesmediumdivide-and-conquer

Solve in Interative Editor

Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.

Validate Balanced Brackets Solution

Problem Statement

Input

Output

Input

Output

Input

Output

Input

Output

Constraints

More Stack

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

Validate Balanced Brackets — Problem Statement & Solution Guide

Problem Description

DSA Pattern Breakdown

Core Theory — Why This Approach?

Interview Questions on This Problem

Examples

Constraints

Optimal Approach & Strategy

Brute Force Approach

Verified Code Solutions

Asked in Top Tech Interviews

Solve in Interative Editor