DSA-VerseLearn by watching code run
DashboardData StructuresAlgorithmsVisualizerCORECoding PlaygroundInterview QuestionsComplexity AnalyzerLearning NotesBookmarksLearning ProgressSettings
All interview questions

Interview preparation

Valid Parentheses

EasyStringsStacks and Queues
AmazonMicrosoftMetaGoogle Community-reported practice tags — not verified company questions.

1Problem statement

Given a string s containing only the characters ( ) [ ] { }, decide whether it is valid: every opening bracket must be closed by the same type of bracket, and brackets must close in the correct order.

2Examples

Input: s = "()[]{}"
Output: true
Input: s = "(]"
Output: false
Input: s = "([)]"
Output: false
Explanation: The [ is closed by ) before it is closed by ].
Input: s = "{[]}"
Output: true

3Constraints

  • 1 ≤ s.length ≤ 10⁴
  • s consists of brackets only.

4Approaches

Approach 1

Brute Force

Repeatedly delete adjacent pairs '()', '[]', '{}' until nothing changes; valid if the string becomes empty.

Time O(n²)Space O(n)

Approach 2

Better: Counters

Counting open/close per type catches unbalanced counts but fails on order like '([)]' — useful to see why order needs a stack.

Time O(n)Space O(1)

Approach 3

Optimal: Stack

Push opening brackets. For a closing bracket the top of the stack must be its matching opener; pop it. At the end the stack must be empty.

Time O(n)Space O(n)

5Code (optimal approach)

Complete programs that print the example outputs — verified in JavaScript, Python, Java and Go.

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

for (const s of ["()[]{}", "(]", "([)]", "{[]}"]) {
  console.log(s, isValid(s));
}

6Complexity

Time

O(n)

Space

O(n)

7Visual walkthrough

  1. 1.s = "{[]}": push "{" → stack ["{"]
  2. 2.push "[" → stack ["{", "["]
  3. 3."]" matches top "[" → pop → stack ["{"]
  4. 4."}" matches top "{" → pop → stack [] → empty, so valid

Related visualization (Stack Push and Pop) — shows the core data-structure operations this solution relies on:

Stack Push and Popinteractive Open full visualizer
push 10push 20push 30push 40pop()pop()pop()pop()
push
10
0
1
2
top = −1 (empty)

Size 0 / 3 · LIFO — the last value pushed is the first one popped

Top elementJust pushedPopped / rejected

A stack is Last-In-First-Out (LIFO): push adds to the top, pop removes from the top. A fixed capacity shows overflow (push when full) and underflow (pop when empty).

1 / 24

8Related questions

Implement Queue using Stacks

On this page

  1. 01Problem statement
  2. 02Examples
  3. 03Constraints
  4. 04Approaches
  5. 05Code (4 languages)
  6. 06Complexity
  7. 07Visual walkthrough
  8. 08Related questions