Coding problem · Easy · Stack

Valid Parentheses

Easy Algorithms & data structures Most askedSeen at Amazon, Meta, Google, Microsoft, Bloomberg

Given a string s containing only ()[]{}, return true if every opening bracket is closed by the same type of bracket in the correct order.

Example 1

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

Example 2

Input: s = "(]"
Output: false

Example 3

Input: s = "([])"
Output: true

Constraints

1 <= s.length <= 10^4

Hints

Hint 1

The most recent unclosed bracket must be closed first — that's a stack.

Write and run your solution

Loading the editor… (JavaScript is required to run code in your browser.)

Solution and explanation

Show the solution

Time O(n) · Space O(n)

Push opening brackets; on a closing bracket, the stack top must be its partner. At the end the stack must be empty (no unclosed brackets).

Reference solution

function isValid(s) {
  const pairs = { ")": "(", "]": "[", "}": "{" };
  const stack = [];
  for (const c of s) {
    if (c in pairs) {
      if (stack.pop() !== pairs[c]) return false;
    } else stack.push(c);
  }
  return stack.length === 0;
}

function isValid(s: string): boolean {
  const pairs: Record<string, string> = { ")": "(", "]": "[", "}": "{" };
  const stack: string[] = [];
  for (const c of s) {
    if (c in pairs) {
      if (stack.pop() !== pairs[c]) return false;
    } else stack.push(c);
  }
  return stack.length === 0;
}

def is_valid(s: str) -> bool:
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for c in s:
        if c in pairs:
            if not stack or stack.pop() != pairs[c]:
                return False
        else:
            stack.append(c)
    return not stack

<?php

function isValid(string $s): bool
{
    $pairs = [')' => '(', ']' => '[', '}' => '{'];
    $stack = [];
    foreach (str_split($s) as $c) {
        if (isset($pairs[$c])) {
            if (array_pop($stack) !== $pairs[$c]) {
                return false;
            }
        } else {
            $stack[] = $c;
        }
    }
    return $stack === [];
}

class Solution {
    public 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 open = stack.pop();
                if ((c == ')' && open != '(') || (c == ']' && open != '[') || (c == '}' && open != '{')) return false;
            }
        }
        return stack.isEmpty();
    }
}

Common mistakes

Forgetting the final empty-stack check — "((" must be false.
Popping from an empty stack on input like "){".

Daily Temperatures · Medium
Min Stack · Medium