Bracket Sequence Validator — Problem Statement & Solution Guide

StackMediumImplementing a Stack to Validate Sequences

TimeO(n)

SpaceO(n)

Quick Answer & Algorithm Key Takeaway

Master coding challenges related to Stack and solve the Bracket Sequence Validator problem optimally.

TopicStack

PatternImplementing a Stack to Validate Sequences

TimeO(n)

SpaceO(n)

Problem Description

Given a string s composed exclusively of the characters '(' , ')' , '[' , ']' , '{' , '}', determine whether the brackets are correctly nested. A bracket sequence is correct if each opening bracket is matched with a closing bracket of the same type and the pairs are ordered such that a closing bracket always corresponds to the most recent unmatched opening bracket. Return true when the sequence is correct, otherwise return false.

DSA Pattern Breakdown

"Bracket Sequence Validator"

medium

WHY DOES IT MATTER?

The stack pattern is essential because many real‑world problems involve nested, hierarchical structures where the most recent element must be resolved first; mastering it unlocks solutions for parsing, expression evaluation, and backtracking tasks.

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 and achieve linear time with a simple push/pop discipline.

REAL-WORLD CONNECTION

Compilers use a stack to match parentheses, braces, and scopes while parsing source code, and network protocol parsers use similar mechanisms to validate nested message frames.

During an interview, explicitly state the invariant (the stack always contains unmatched openings in order) before coding; this demonstrates clear reasoning and helps avoid off‑by‑one errors.

COMPLEXITY AT A GLANCE

⏱ Time:O(n)

💾 Space:O(n)

Core Theory — Why This Approach?

The Bracket Sequence Validator is a canonical problem that illustrates the power of the stack data structure for handling nested, last‑in‑first‑out relationships. In a correctly nested sequence, each opening bracket must be closed by the same type of bracket, and the most recent unmatched opening bracket must be closed first. This property maps directly onto a stack: we push every opening bracket onto the stack, and when we encounter a closing bracket we check whether it matches the element on the top of the stack. If it does, we pop; otherwise the sequence is invalid. The algorithm proceeds in a single left‑to‑right pass, guaranteeing that the order of operations respects the nesting constraints.

A naive solution might attempt to compare every opening bracket with every later closing bracket using nested loops or recursion, leading to O(n^2) time or exponential blow‑up for recursive backtracking. Such approaches quickly become infeasible for long strings (e.g., millions of characters) because they repeatedly scan already processed portions of the input. Moreover, recursive solutions risk stack overflow in languages with limited call‑stack depth. The optimal paradigm replaces these repeated scans with a single pass and a constant‑time check per character, using a stack to remember only the unmatched openings. This reduces the time complexity to linear O(n) and the auxiliary space to O(n) in the worst case (when all characters are opening brackets).

The stack‑based method also scales well in practice: each character triggers at most one push or pop, and modern CPUs handle these operations extremely efficiently. By coupling the stack with a hash map that maps closing brackets to their corresponding opening brackets, the implementation remains concise, readable, and easy to extend (e.g., adding new bracket types). This combination of theoretical optimality and practical simplicity makes the stack solution the de‑facto standard for bracket validation problems.

Interview Questions on This Problem

Q1How would you validate a string of mixed brackets in O(n) time and O(n) space?

Use a stack: iterate through the string, push opening brackets, and when a closing bracket appears, check if it matches the top of the stack; if it does, pop, otherwise return false. At the end, the string is valid if the stack is empty.

Q2In a fintech transaction parser, why is bracket validation critical and how would you handle malformed inputs efficiently?

Bracket validation ensures the structural integrity of nested data formats (e.g., JSON, custom DSL). By applying the same stack algorithm, you can reject malformed inputs early, avoiding costly downstream processing, and you can augment the stack with position tracking to report precise error locations.

Q3A high‑growth startup wants to extend the validator to support custom delimiters like '<' and '>'. What changes are needed in your algorithm?

Add the new delimiter pair to the mapping dictionary and treat '<' as an opening bracket and '>' as a closing bracket. The core stack logic remains unchanged, demonstrating the algorithm’s extensibility.

Examples

Example 1

Input

([]){}

Output

true

Explanation: Read '(' → push. Read '[' → push. Read ']' → top is '[' → pop. Read ')' → top is '(' → pop. Read '{' → push. Read '}' → top is '{' → pop. Stack empty at end → valid.

Example 2

Input

([)]

Output

false

Explanation: Read '(' → push. Read '[' → push. Read ')' → top is '[' which does not match ')', mismatch → invalid.

Example 3

Input

((({[]})))

Output

true

Explanation: Push three '(' then '{' then '['. Encounter ']' → matches '[' → pop. Encounter '}' → matches '{' → pop. Then three ')' each match a '(' → pop each. Stack empty → valid.

Constraints

1 <= s.length <= 100000
s contains only '(' , ')' , '[' , ']' , '{' , '}'
Expected time complexity O(n)
Expected auxiliary space O(n)

Optimal Approach & Strategy

The optimal solution uses a stack to track unmatched openings, achieving O(n) time by processing each character once and O(n) space for the stack in the worst case.

Brute Force Approach

A naive method checks every opening bracket against every later closing bracket, often using nested loops or recursion, leading to O(n^2) or exponential time. It also requires repeatedly scanning already processed parts of the string.

Code Solutions

Language:

JavaScript Solution

Time: O(n)

function isValid(s) {
    const stack = [];
    for (let ch of s) {
        if (ch === '(' || ch === '[' || ch === '{') {
            stack.push(ch);
        } else {
            if (stack.length === 0) return false;
            const top = stack.pop();
            if ((ch === ')' && top !== '(') ||
                (ch === ']' && top !== '[') ||
                (ch === '}' && top !== '{')) {
                return false;
            }
        }
    }
    return stack.length === 0;
}

const fs = require('fs');
const input = fs.readFileSync(0, 'utf8').trim();
console.log(isValid(input) ? "true" : "false");

#include <bits/stdc++.h>
using namespace std;

bool isValid(const string& s) {
    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();
}

int main() {
    string s;
    getline(cin, s);
    cout << (isValid(s) ? "true" : "false");
    return 0;
}

import java.util.*;

public class Main {
    public static boolean isValid(String s) {
        Deque<Character> stack = new ArrayDeque<>();
        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();
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        System.out.print(isValid(s) ? "true" : "false");
    }
}

def is_valid(s):
    stack = []
    mapping = {')': '(', ']': '[', '}': '{'}
    for ch in s:
        if ch in "([{":
            stack.append(ch)
        else:
            if not stack or stack.pop() != mapping.get(ch):
                return False
    return not stack

if __name__ == "__main__":
    import sys
    s = sys.stdin.read().strip()
    print("true" if is_valid(s) else "false")

function isValid(s) {
    const stack = [];
    for (let ch of s) {
        if (ch === '(' || ch === '[' || ch === '{') {
            stack.push(ch);
        } else {
            if (stack.length === 0) return false;
            const top = stack.pop();
            if ((ch === ')' && top !== '(') ||
                (ch === ']' && top !== '[') ||
                (ch === '}' && top !== '{')) {
                return false;
            }
        }
    }
    return stack.length === 0;
}

const fs = require('fs');
const input = fs.readFileSync(0, 'utf8').trim();
console.log(isValid(input) ? "true" : "false");

Asked in Top Tech Interviews

Zomato

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.