Lists, stacks & queues / Beginner

Valid Parentheses Visualizer

Push every opening bracket. A closing bracket must match the top of the stack. At the end, the stack must be empty.

Start the Valid Parentheses simulation → Step forward and back, change the input, follow the code line by line in Java, Python, C++, C or JavaScript. Free, no sign-up.

Time and space complexity

Best time	O(n)
Average time	O(n)
Worst time	O(n)
Extra space	O(n)

Worked example, step by step

The same steps the simulator shows, on a small input.

Read the brackets from left to right. Openers go on a stack.
{ opens something. Push it.
[ opens something. Push it.
( opens something. Push it.
) closes (. Pop it.
( opens something. Push it.
) closes (. Pop it.
] closes [. Pop it.
} closes {. Pop it.
Every bracket was matched and the stack is empty. Valid.

Try it with your own input →

Stack: valid parentheses in Java, Python, C++, C and JavaScript

JavaPythonC++CJavaScript

boolean isValid(String s) {
  Deque<Character> st = new ArrayDeque<>();
  for (char c : s.toCharArray()) {
    if (c == '(' || c == '[' || c == '{') st.push(c);
    else {
      if (st.isEmpty()) return false;
      char open = st.pop();
      if (!matches(open, c)) return false;
    }
  }
  return st.isEmpty();
}

PAIRS = {')': '(', ']': '[', '}': '{'}

def is_valid(s):
    st = []
    for c in s:
        if c in '([{':
            st.append(c)
        else:
            if not st:
                return False
            open_c = st.pop()
            if PAIRS[c] != open_c:
                return False
    return not st

bool matches(char open, char close) {
  return (open == '(' && close == ')') || (open == '[' && close == ']') || (open == '{' && close == '}');
}
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 open = st.top(); st.pop();
      if (!matches(open, c)) return false;
    }
  }
  return st.empty();
}

#include <string.h>
#include <stdlib.h>

int matches(char open, char close) {
  return (open == '(' && close == ')') || (open == '[' && close == ']') || (open == '{' && close == '}');
}
int isValid(const char* s) {
  int n = strlen(s), top = 0, ok = 1;
  char* st = malloc(n + 1);
  for (int x = 0; x < n && ok; x++) {
    char c = s[x];
    if (c == '(' || c == '[' || c == '{') st[top++] = c;
    else {
      if (top == 0) ok = 0;
      else {
        char open = st[--top];
        if (!matches(open, c)) ok = 0;
      }
    }
  }
  free(st);
  return ok && top == 0;
}

const PAIRS = { ')': '(', ']': '[', '}': '{' };

function isValid(s) {
  const st = [];
  for (const c of s) {
    if (c === '(' || c === '[' || c === '{') st.push(c);
    else {
      if (st.length === 0) return false;
      const open = st.pop();
      if (PAIRS[c] !== open) return false;
    }
  }
  return st.length === 0;
}

In an interview

LeetCode 20, Valid Parentheses.

There are three ways to fail: a closer with an empty stack, a mismatch, or openers left over at the end. Test all three.

Time and space complexity

Worked example, step by step

Stack: valid parentheses in Java, Python, C++, C and JavaScript

In an interview

More lists, stacks & queues