valid-parentheses

Difficulty: Easy  ·  Topic: Stack  ·  Practice it on parikshan: /practice/valid-parentheses/start

The story

A configuration linter for a JSON-like internal format must reject files where brackets do not nest correctly. A user opens {, then [, then (, and closes them. The valid closing order is ), ], }: most recently opened, first to be closed. The invalid orders are everything else. Your job is to tell the user, in a single pass, whether their file's bracket structure is consistent.

This is the JSON, HTML, YAML, and Markdown parser embryo. Every linter in your IDE relies on a more elaborate version of this one function.

What's actually being asked

Given a string s containing only the characters ()[]{}, return true if the brackets are well-formed. Open brackets must close in the right order, and every open bracket must have a matching close of the same type.

Examples:

• "()" → true
• "()[]{}" → true
• "(]" → false
• "([)]" → false (closed in the wrong order)
• "{[]}" → true

The naive approach

Repeatedly find () or [] or {} adjacent pairs and remove them. If the string ends up empty, it was valid. Correct, but O(n²) because each scan removes one pair and there are up to n/2 pairs.

The key insight

The valid order is last-opened first-closed. That is the defining property of a stack: a LIFO container. Walk the string left to right. Push every open bracket. When you see a close bracket, pop the top of the stack and check whether it matches. If the stack is empty when you try to pop, or the top doesn't match, the string is invalid. After the loop, the stack must be empty.

That is the entire algorithm in three sentences. Stacks were invented for problems shaped exactly like this one.

Step-by-step approach

1. Create an empty stack (a list, used as LIFO).
2. Create a map: {')': '(', ']': '[', '}': '{'} from close to its matching open.
3. For each character c in the string:
   • If c is an open bracket, push it.
   • Else (it's a close bracket): if the stack is empty, return false. Pop the top; if it isn't the matching open, return false.
4. After the loop, return true if the stack is empty, false otherwise.

Worked example

s = "{[()]}"

End: stack is empty → return true.

Counter-example: "([)]".

Complexity

• Time: O(n), one pass.
• Space: O(n), the stack (worst case is a string of all opens).

Common pitfalls

• Returning true at the end without checking the stack is empty. "((" would slip through; both pushes happen, no pops, no mismatch, and you return true. Always check len(stack) == 0 at the end.
• Trying to use a counter instead of a stack. A single integer (+1 on open, -1 on close, fail if it goes negative) works for one bracket type. With three types you must remember which type was opened, so you need a stack.
• Wrong direction. Pushing closes and popping opens "works" by symmetry but is harder to reason about. Push opens, pop on close.

Where this shows up in the enterprise

• VS Code, IntelliJ, Sublime: every IDE's bracket-matching highlight runs a variant of this on the visible buffer every time the cursor moves.
• ESLint, RuboCop, Prettier: lexer-level bracket balance check before syntactic parsing.
• Postman, Insomnia, curl: validating JSON request bodies before sending.
• AWS CloudFormation, Terraform: pre-parse balance check on configuration files.
• Markdown processors (GitHub, Slack, Notion): matching [ with ] for link parsing, then ( with ) for the URL.
• SQL clients (DataGrip, DBeaver): balancing parentheses in nested queries.
• HTML / XML validators: same idea, with named tags as bracket types.
• Network protocol decoders: balanced delimiters in framed protocols (LDAP, ASN.1, S-expression-style RPC).
• CI pipeline YAML: well-formedness check before semantic validation.

Variants you'll see elsewhere

• min-stack: a stack that also returns the minimum in O(1). Auxiliary stack pattern.
• evaluate-reverse-polish-notation: the same stack runs an arithmetic VM.
• generate-parentheses: backtracking to enumerate all valid bracket strings.
• daily-temperatures, next-greater-element-i: monotonic stacks for "next greater" patterns.
• HTML / XML validators in production code; tag names instead of bracket types.

How parikshan turns this into a learning loop

In parikshan, this problem is the moment many candidates discover they have been memorising solutions instead of internalising patterns. The judge runs your solution against per-session dynamic tests that include adversarial strings (mismatched close, only opens, only closes, deeply nested, alternating, length 0, length 1). Without the pattern internalised, you will fail at least one and learn it the hard way; with the pattern, all dynamic variants pass on the first try because they share the invariant.

The AI training mode lets you ask the assistant to Find Bugs on your draft. The recommended workflow: write a first attempt without help, hit Submit, see the verdict, and only if the verdict is WA do you spend integrity points on Find Bugs. That integrity discipline trains the pattern into reflex.

In the AI-integrated workspace

In production, when an agent generates a parser for a bracketed format, your review is asking:

• Does it use a stack, not a counter? (Required for multi-type brackets.)
• Does it check the stack-empty case on every close?
• Does it check the stack is empty at the end?
• Does it pair the right type? (No } closing [.)

Those four checks are the entire correctness argument. An agent that misses any of the four ships a parser that "looks right and validates valid input but lets invalid input through". That is exactly the kind of silent bug that, in a security context, becomes a CVE (think log4j-style injection of malformed input).

valid-parentheses is small but its discipline is the discipline of every parser in your career. Treat it as such.