20. Valid Parentheses

easyAsked at LinkedIn

Determine whether a string of brackets is correctly matched using a stack — LinkedIn uses this as a 5-minute coding warm-up, often paired with a JSON or template-syntax validation scenario to tie the abstract stack to the profile-rendering pipeline that parses nested markup in member summaries.

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

Problem

Given a string s containing only the characters '(', ')', '{', '}', '[', and ']', determine if the input string is valid. A string is valid if: open brackets must be closed by the same type of bracket and open brackets must be closed in the correct order. An empty string is considered valid.

Constraints

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

Examples

Example 1

Input

s = "()[]{}"

Output

true

Example 2

Input

s = "([)]"

Output

false

Explanation: The closing ')' does not match the most recent open bracket '[' on the stack.

Example 3

Input

s = "{[]}"

Output

true

Approaches

1. Counter-based — only works for single bracket type

Track open count with a counter. Works for '()' alone but breaks for mixed types like '([)]'. Name this to show you understand why a stack is necessary.

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

// Only correct for a single bracket type — breaks for mixed brackets:
// function isValidSingle(s) {
//   let count = 0;
//   for (const c of s) {
//     if (c === '(') count++;
//     else if (c === ')') { if (count === 0) return false; count--; }
//   }
//   return count === 0;
// }

Tradeoff:

2. Stack with close-bracket map — optimal

Use a Map from each closing bracket to its matching opener. Push openers onto the stack. On a closer, pop the stack and verify it matches. Valid iff stack is empty at the end.

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

function isValid(s) {
  const matching = new Map([[')', '('], ['}', '{'], [']', '[']]);
  const stack = [];
  for (const c of s) {
    if (!matching.has(c)) {
      stack.push(c); // opener
    } else {
      if (stack.pop() !== matching.get(c)) return false; // wrong closer or empty stack
    }
  }
  return stack.length === 0;
}

Tradeoff:

LinkedIn-specific tips

LinkedIn uses Valid Parentheses to test clear thinking before the harder questions. The move that impresses: use a Map from closer → opener rather than a chain of if-else comparisons. It's the same number of lines but signals you reach for data structures naturally. Be ready for the follow-up: 'what if the string also contains alphanumeric characters (like real code)?' — answer is unchanged, just skip non-bracket characters. Second follow-up: 'what if you need to find the minimum number of removals to make the string valid?' (LC 1249) — two-pass counting approach.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →