Skip to main content

20. Valid Parentheses

easyAsked at Akamai

Determine whether a string of brackets is correctly nested. Akamai asks this to test stack-based reasoning — the same pattern underpins parsing HTTP header fields and configuration syntax that edge servers process at high throughput.

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

Source citations

Public interview reports confirming this problem appears in Akamai loops.

  • Glassdoor (2025-12)— Mentioned as a first-round coding question in Akamai SWE onsite feedback.
  • Blind (2025-09)— Akamai phone-screen threads list Valid Parentheses as a common warm-up problem.

Problem

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

Constraints

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

Examples

Example 1

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

Explanation: Each bracket type is correctly matched and closed.

Example 2

Input
s = "(]"
Output
false

Explanation: Open paren closed by square bracket — type mismatch.

Example 3

Input
s = "([)]"
Output
false

Explanation: Incorrect nesting order.

Approaches

1. Stack with match map

Push every open bracket onto a stack. When a closing bracket is seen, check that the top of the stack is the matching opener. If not, or if the stack is empty, return false. At the end the stack must be empty.

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

Tradeoff: One pass, O(n) time, O(n) space for the stack. The closing-bracket map keeps the logic clean and avoids three separate if-else branches.

Akamai-specific tips

Akamai values precise reasoning about edge cases. Before coding, enumerate them aloud: empty string (valid), single open bracket (invalid — stack non-empty at end), mismatched type, correct brackets but wrong order. This shows the systematic thinking Akamai expects before writing a single line of code.

Common mistakes

  • Not checking for an empty stack before popping — causes an undefined comparison instead of returning false.
  • Forgetting to verify stack.length === 0 at the end — '(((' passes all pops but is invalid.
  • Trying to count brackets instead of using a stack — counts cannot detect nesting order violations like '([)]'.

Follow-up questions

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

  • How would you extend this to validate full JSON or XML structure?
  • What if the input stream is too large to hold in memory — can you still validate it?
  • Generate Parentheses (LC 22) — produce all valid combinations of n pairs.

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 pop before checking rather than peek?

pop() removes and returns the top element in one step. If we peeked and then conditionally popped, we'd need an extra operation. The mismatch check and removal are logically the same event.

Does an empty string return true or false?

True — an empty stack at the end satisfies all conditions. There are no unmatched brackets.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →