DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

Valid Parentheses

easyStack and queue Must-do

Problem statement

Given a string made only of the characters ( ) [ ] { }, decide whether it is valid: every opening bracket is closed by the same type of bracket, and brackets close in the right order.

Examples

Example 1

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

Output: True

Explanation: Each bracket is closed by its matching type, innermost first.

Approach

Optimal

The most recently opened bracket must be the first one closed. "Last in, first out" is exactly what a stack does. Push each opening bracket; when a closing bracket arrives, it must match whatever is on top.

  1. Map each closing bracket to its opening partner: ')' -> '(', ']' -> '[', '}' -> '{'.
  2. Walk through the string. Push every opening bracket onto a stack.
  3. For a closing bracket, the stack must be non-empty and its top must be the matching opener. Pop it; otherwise the string is invalid.
  4. At the end, the string is valid only if the stack is empty (nothing left unclosed).
ComplexityTime O(n)Space O(n)
Python
def is_valid(s: str) -> bool:
pairs = {")": "(", "]": "[", "}": "{"}
stack = []
for ch in s:
if ch in pairs: # closing bracket
if not stack or stack[-1] != pairs[ch]:
return False
stack.pop()
else: # opening bracket
stack.append(ch)
return not stack

Frequently asked questions

Anything that nests uses this check: validating that a Helm or Jinja template closes every {{ }} and {% %} block, checking JSON or HCL braces before a deploy, or matching BEGIN and END markers in a log. Interviewers often extend it to "report the line number of the first unmatched bracket", so practise tracking positions too.

  • Forgetting to check that the stack is empty at the end, so "((" is wrongly accepted.
  • Popping from an empty stack when the string starts with a closing bracket.
  • Only counting brackets, which accepts "([)]" even though the order is wrong.