Skip to main content

20. Valid Parentheses

easyAsked at Atlassian

Valid Parentheses is Atlassian's stack-introduction warm-up. Given a string containing only the characters '()', '[]', and '{}', determine if the input is properly matched. Atlassian uses it to check you know when to reach for a stack before pivoting to a harder parsing question.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Atlassian loops.

  • Glassdoor (2026-Q1)— Atlassian SWE-I phone-screen reports cite Valid Parentheses as a 10-15 minute opener before harder parser-style follow-ups.
  • Reddit r/cscareerquestions (2025-08)— Multiple Atlassian onsite reports use Valid Parentheses as the warm-up before the markdown/HTML-parser variant.

Problem

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. An input string is valid if: open brackets must be closed by the same type of brackets; open brackets must be closed in the correct order; and every close bracket has a corresponding open bracket of the same type.

Constraints

  • 1 <= s.length <= 10^4
  • s consists of parentheses only '()[]{}'.

Examples

Example 1

Input
s = "()"
Output
true

Example 2

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

Example 3

Input
s = "(]"
Output
false

Example 4

Input
s = "([])"
Output
true

Approaches

1. Repeated pair-removal (brute)

Replace any of '()', '[]', '{}' with empty string until the string stops shrinking. Valid iff the final string is empty.

Time
O(n^2)
Space
O(n)
function isValidBrute(s) {
  let prev;
  while (s !== prev) {
    prev = s;
    s = s.replace('()', '').replace('[]', '').replace('{}', '');
  }
  return s.length === 0;
}

Tradeoff: Pleasingly short and easy to explain, but quadratic — each replace rescans the string, and you may need n/2 passes. Useful only as a 30-second 'I could write it like this, but here's the linear version' framing for the interviewer.

2. Single-pass stack (optimal)

Walk the string. Push openers. On a closer, pop and verify the popped opener matches; mismatch or empty stack ⇒ false. Valid iff the stack is empty at the end.

Time
O(n)
Space
O(n)
function isValid(s) {
  const pairs = { ')': '(', ']': '[', '}': '{' };
  const stack = [];
  for (const ch of s) {
    if (ch === '(' || ch === '[' || ch === '{') {
      stack.push(ch);
    } else {
      if (stack.pop() !== pairs[ch]) return false;
    }
  }
  return stack.length === 0;
}

Tradeoff: Linear time, linear worst-case space (all-opens input). The pairs lookup table is faster and cleaner than chained if/else on every character; Atlassian interviewers consistently mark candidates up for the table.

Atlassian-specific tips

Atlassian rewards explicit edge-case enumeration. Before coding, state out loud: empty string is valid (vacuously), odd length is automatically false, a string starting with a closer is false, and you must check the stack is empty at the end. Two of those three are the cases that break naive implementations on the LeetCode hidden test set.

Common mistakes

  • Forgetting to check stack.length === 0 at the end — '(((' returns true if you skip this.
  • Using stack.pop() on an empty stack and not handling undefined — JS does not throw, so the comparison silently passes when it shouldn't.
  • Coding the brackets with if/else instead of a pairs map and shipping an unreadable cascade.

Follow-up questions

An interviewer at Atlassian may pivot to one of these next:

  • Minimum Remove to Make Valid Parentheses (LeetCode 1249) — return the shortest valid string after removing the minimum number of brackets.
  • Generate Parentheses (LeetCode 22) — generate all valid combinations of n pairs.
  • What if the alphabet of brackets were dynamic — e.g., XML/HTML tags? Stack stays the same but the matcher becomes a string-prefix comparison.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Is the stack-based solution always linear?

Time, yes. Space is worst-case linear when the input is all openers — '(((((' forces the stack to grow with the input. Mention this; Atlassian interviewers grade explicit-space candor.

Can I solve it without a stack using counters?

Only if there is one bracket type. With three types you must remember the most-recent unmatched opener, which is exactly what a stack gives you. Don't try the counter approach — it doesn't generalize and the interviewer will catch it.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

Drill Valid Parentheses and other Atlassian interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →