20. Valid Parentheses

Q: Why use a stack instead of a counter?

A simple counter works for a single bracket type, but with three types you must track which opener is waiting to be closed. The stack preserves that ordering.

Q: What if the string is empty?

The loop never runs and stack.length === 0 returns true — an empty string is considered valid per the problem definition.

Q: Can this be done in O(1) space?

Not in general — consider '((((': you need to remember all the unmatched openers. O(n) stack space is unavoidable in the worst case.

easyAsked at HP

Parsing structured expressions is core to HP's firmware configuration parsers and printer command languages (PCL/PJL). Valid Parentheses tests whether you can maintain state with a stack — the same discipline behind device-command validation.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-22

Source citations

Public interview reports confirming this problem appears in HP loops.

Glassdoor (2025-Q4)— Cited in HP SWE intern and new-grad interview reports as a common first-round warm-up.
Blind (2025-10)— HP candidates mention Valid Parentheses as a typical phone-screen question for entry-level engineering roles.

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: Each bracket pair is correctly matched and ordered.

Example 2

Input

s = "(]"

Output

false

Explanation: The closing bracket ] does not match the open bracket (.

Example 3

Input

s = "([)]"

Output

false

Explanation: Brackets interleave instead of nesting properly.

Approaches

1. Stack with map

Push open brackets onto a stack. For each closing bracket, verify the top of the stack holds its matching opener. If the stack is empty at end, the string is valid.

Time: O(n)
Space: O(n)

function isValid(s) {
  const stack = [];
  const map = { ')': '(', '}': '{', ']': '[' };
  for (const ch of s) {
    if (ch === '(' || ch === '{' || ch === '[') {
      stack.push(ch);
    } else {
      if (stack.length === 0 || stack[stack.length - 1] !== map[ch]) {
        return false;
      }
      stack.pop();
    }
  }
  return stack.length === 0;
}

Tradeoff: Clean O(n) solution. Using a map for matching keeps the closing-bracket logic compact and avoids long if-else chains. This is the industry-standard answer.

HP-specific tips

HP interviewers look for explicit edge-case handling — mention the empty-stack check before popping and the final stack-length check. In the context of HP's parser infrastructure, point out that this pattern is directly applicable to validating nested configuration directives or markup languages. Walk through at least one failing example character-by-character to demonstrate correctness.

Common mistakes

Not checking if the stack is empty before popping — leads to a runtime error on strings that start with a closing bracket.
Forgetting the final stack.length === 0 check — the string '(((' passes the inner loop but the stack is non-empty.
Using three separate if-branches instead of a lookup map — verbose and error-prone.
Returning true as soon as all characters are processed without verifying the stack is empty.

Follow-up questions

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

Extend the solution to handle nested HTML or XML tags.
What is the minimum number of bracket insertions to make a string valid?
How would you handle escaped brackets inside string literals?

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 use a stack instead of a counter?

A simple counter works for a single bracket type, but with three types you must track which opener is waiting to be closed. The stack preserves that ordering.

What if the string is empty?

The loop never runs and stack.length === 0 returns true — an empty string is considered valid per the problem definition.

Can this be done in O(1) space?

Not in general — consider '((((': you need to remember all the unmatched openers. O(n) stack space is unavoidable in the worst case.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →