Skip to main content

20. Valid Parentheses

easyAsked at Cohere

Determine if a string of brackets is balanced. Cohere uses this as a warm-up to test stack reasoning — the same pattern that validates structured outputs and nested function calls in LLM inference pipelines.

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

Source citations

Public interview reports confirming this problem appears in Cohere loops.

  • Glassdoor (2025-Q4)— Mentioned in Cohere junior SWE interview reports as a common phone-screen opener.
  • Blind (2025-10)— Cohere candidates reference Valid Parentheses as a frequent warm-up before harder algorithm questions.

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

Explanation: Single matching pair.

Example 2

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

Explanation: '{' is opened after '[' but closed before ']' — order violation.

Example 3

Input
s = "{[]}"
Output
true

Explanation: Properly nested.

Approaches

1. Stack with mapping

Push open brackets onto a stack. On a close bracket, check whether the top of the stack is the matching open bracket. If not, or if the stack is empty, return false. Return true only if the stack is empty at the end.

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

Tradeoff: Linear time and space — optimal. The map-based approach cleanly handles all three bracket types without a chain of conditionals.

Cohere-specific tips

Cohere may frame this as: 'We receive structured JSON responses from an LLM; validate the bracket structure before parsing.' Lean into that context — mention that the same stack logic validates deeply nested JSON or XML schemas produced by generative models. Discuss how you would extend it to handle escaped quotes or string literals.

Common mistakes

  • Forgetting to check stack.length === 0 at the end — a string like '(' would otherwise return true.
  • Using pop() without checking for empty stack — pop() returns undefined on an empty array in JS, so the comparison to map[ch] accidentally works, but state it explicitly.
  • Not handling odd-length strings early — an early return for odd length is a nice optimization to mention.
  • Using a counter instead of a stack — a counter works for a single bracket type but fails for mixed types.

Follow-up questions

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

  • Minimum remove to make valid — remove the fewest characters to balance the string.
  • Generate parentheses — produce all combinations of n pairs of valid parentheses.
  • How would you validate nested JSON brackets in a streaming response from a language model?

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Why does popping from an empty stack not crash in JS?

Array.pop() on an empty array returns undefined. Comparing undefined !== map[ch] is still false-safe — but you should document this assumption rather than rely on it silently.

Can you do this in O(1) space?

No — in the worst case (all open brackets) you need O(n) stack space.

Does the order of checks matter?

You can check for open brackets first and fall through to the close-bracket branch, or use an explicit set. Either is fine as long as the logic is clear.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →