Skip to main content

20. Valid Parentheses

easyAsked at Cisco

Valid Parentheses at Cisco is a 5-minute warm-up where the interviewer just wants to confirm you know what a stack is. Skip it in under 10 minutes and you've earned the harder graph round. The interviewer is grading whether you map closing brackets to openers correctly and whether you handle the empty-stack pop.

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

Source citations

Public interview reports confirming this problem appears in Cisco loops.

  • Glassdoor (2026-Q1)— Cisco SDE-I phone-screen reports cite this as a recurring warm-up.
  • Levels.fyi (2025-11)— Cisco new-grad interview reports list Valid Parentheses as a typical first round.

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 are closed by the same type of brackets, open brackets are 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
false

Explanation: Brackets must be closed in nesting order.

Approaches

1. Brute-force: repeatedly remove matching pairs

Scan the string for '()', '[]', '{}' and delete them. Repeat until either the string is empty (valid) or no more matches are found (invalid).

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

Tradeoff: Cute and works, but each replace pass is O(n) and we might do n/2 passes. Quadratic and not the answer Cisco wants. Useful only to show you can solve it before optimizing.

2. Stack with map (optimal)

Map each closing bracket to its opener. Push openers, pop on closers and check the match.

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

Tradeoff: Linear time, O(n) extra space for the stack. The mapping object is what makes the close-bracket logic a single line — interviewers respect the compactness. Critical edge case: `stack.pop()` on empty returns undefined, which won't match any opener, so the early-return on mismatch handles that branch implicitly.

Cisco-specific tips

Cisco interviewers want this solved in 5-10 minutes flat. State the algorithm before writing: 'I use a stack. Push openers, pop on closers and check the match. At the end, the stack must be empty.' Then write it. If you're done in under 5, ask whether they want to extend to additional bracket types or string-with-other-characters — that initiative shows engineering polish.

Common mistakes

  • Forgetting the final `stack.length === 0` check — '(()' passes the loop but should return false.
  • Mapping openers to closers instead of the other way around — works but harder to read because you check after the push.
  • Calling `stack.pop()` and using strict equality with undefined incorrectly — works in JS but flag it to the interviewer.

Follow-up questions

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

  • Generate Parentheses (LC 22) — backtracking generation of all valid sequences of length 2*n.
  • Longest Valid Parentheses (LC 32) — stack of indices for the longest matching substring.
  • Minimum Remove to Make Valid (LC 1249) — stack + index tracking + post-pass removal.
  • What if you also need to ignore non-bracket characters? (Filter or skip them in the loop.)

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Should I use one map for closers or for both?

Use one map (closer → opener) so the check at pop is `stack.pop() === close[ch]`. Mapping the other direction (opener → closer) forces you to look up before push and is harder to read.

Why is this an 'Easy' problem on LeetCode?

Because the algorithm is one paragraph and the pattern (push openers, pop closers, validate match) generalizes immediately. Cisco asks it as a filter, not a discriminator — solving it slow or wrong on the phone screen ends the loop.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →