easy Valid Parentheses

Problem Statement

Determine if an input string containing only the characters '(', ')', '{', '}', '[', and ']' is valid. A string is considered valid if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Each close bracket has a corresponding open bracket of the same type.

Examples

- Input: "(]"
- Expected Output: false
- Justification: The opening parenthesis '(' is not closed by its corresponding closing parenthesis.
- Input: "{[]}"
- Expected Output: true
- Justification: The string contains pairs of opening and closing brackets in the correct order.
- Input: "[{]}"
- Expected Output: false
- Justification: The opening square bracket '[' is closed by a curly brace '}', which is incorrect.

Constraints:

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

Try it yourself

Try solving this question here:

🎯 STRICT STANDOUT — Valid Parentheses (problem)

1. Why / judgment

LC-style valid parentheses — still the core parsing stack. Multi-type nesting ⇒ stack, not counts alone.

2. Worked complexity / trace (K11)

"(]" false; "{[]}" true; "[{]}" false. Θ(n) target.

3. Pattern + when-NOT (K12)

Name: LIFO BRACKET MATCH

Recognition: only ()[]{}; order+type validity.

When-NOT: Queue cannot match nesting. Counter works only for one type. Not mono NGE.

4. Edge hand-run (K13)

"([)]": false. "{}": true. "(((" final non-empty false.

5. Interviewer follow-ups

Q1. Equal counts enough?
A: No — order matters.

Q2. Space?
A: O(n) worst.

Q3. Follow-up min add to make valid?
A: Different problem — balance + stack variants.

✅ Solution Valid Parentheses

Problem Statement

Determine if an input string containing only the characters '(', ')', '{', '}', '[', and ']' is valid. A string is considered valid if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Each close bracket has a corresponding open bracket of the same type.

Examples

- Input: "(]"
- Expected Output: false
- Justification: The opening parenthesis '(' is not closed by its corresponding closing parenthesis.
- Input: "{[]}"
- Expected Output: true
- Justification: The string contains pairs of opening and closing brackets in the correct order.
- Input: "[{]}"
- Expected Output: false
- Justification: The opening square bracket '[' is closed by a curly brace '}', which is incorrect.

Constraints:

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

Solution

Initialization:
- Start with an empty stack.
- For every bracket in the input string:
  - If the bracket is an opening bracket ('(', '{', '['), push it onto the stack.
  - If the bracket is a closing bracket (')', '}', ']'):
    - If the stack is empty, return false.
    - Pop the top of the stack and check if it matches the corresponding opening bracket.
Validation:
- If the current closing bracket doesn't match the top of the stack, return false.
- If the stack is not empty after processing all brackets in the string, return false.
Final Output:
- If the stack is empty at the end, return true, indicating that the string has valid parentheses.

Algorithm Walkthrough

Using the input "{[]}":

Start with an empty stack.
Encounter '{', push onto the stack.
Encounter '[', push onto the stack.
Encounter ']', pop from the stack and check if the popped character is '['. It matches, so continue.
Encounter '}', pop from the stack and check if the popped character is '{'. It matches.
The string is processed and the stack is empty, so return true.

Code

java

import java.util.Stack;

public class Solution {

  public boolean isValid(String s) {
    Stack<Character> stack = new Stack<>();
    // Iterate through each character in the string
    for (char c : s.toCharArray()) {
      // If it's an opening bracket, push to stack
      if (c == '(' || c == '{' || c == '[') {
        stack.push(c);
      } else {
        // If stack is empty, it means no matching opening bracket
        if (stack.isEmpty()) return false;
        char top = stack.pop(); // Get the top element of the stack
        // Check if the current closing bracket matches the top of the stack
        if (c == ')' && top != '(') return false;
        if (c == '}' && top != '{') return false;
        if (c == ']' && top != '[') return false;
      }
    }
    // If stack is empty, all brackets were matched
    return stack.isEmpty();
  }

  public static void main(String[] args) {
    Solution solution = new Solution();
    System.out.println(solution.isValid("(]")); // false
    System.out.println(solution.isValid("{[]}")); // true
    System.out.println(solution.isValid("[{]}")); // false
  }
}

Complexity Analysis

Time Complexity: O(n) where n is the length of the string. Each character is processed once.
Space Complexity: O(n) in the worst case when all characters are opening brackets.

🎯 STRICT STANDOUT — Solution Valid Parentheses

1. Why / judgment

Push open, match close, final empty. Prefer Deque; map closer→opener. Same core as Balanced Parentheses.

2. Worked complexity / trace (K11)

"{[]}": push { [ ; pop ] matches [; pop } matches { → true.
"[{]}": push [ { ; ] mismatches { → false. Θ(n)/Θ(n).

3. Pattern + when-NOT (K12)

Name: OPENER STACK MATCH

Recognition: LC20 family.

When-NOT: Generate parentheses → backtracking. Score parentheses → DP/stack hybrid. ArrayDeque over Stack.

4. Edge hand-run (K13)

"(((": false final non-empty. "))": false empty pop. "()[]{}": true.

5. Interviewer follow-ups

Q1. Map vs switch?
A: Both fine; map scales if more pair types.

Q2. Early exit?
A: On mismatch or empty pop — yes.

Q3. Production container?
A: ArrayDeque.

🧩 Pattern · Stack

Recognize it: Matching / nesting, or “next greater / smaller” → LIFO, or a monotonic stack.

▶ Visualize this problem (step it, predict each fork)

⛶ Open this problem debugger in explore mode

🤖 Don't fully get this? Learn it with Claude

Stuck on Valid Parentheses? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🪜 Hint ladder (no spoilers)

Progressively stronger hints — you still solve it.

I'm working on the problem **Valid Parentheses** (DSA). Give me a HINT LADDER: start with the tiniest nudge, then wait. Only reveal the next, stronger hint when I ask. Do NOT show the full solution unless I type 'show solution'. Keep me doing the thinking. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🎨 Explain the approach visually

See the technique, not just code.

Explain the optimal approach to **Valid Parentheses** with a VISUAL walkthrough: trace it on a small concrete example using ASCII art / a step-by-step diagram, narrate what changes each step, then give time & space complexity with a one-line derivation. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔍 Review my solution

Catch bugs, edge cases, sub-optimality.

I'll paste my solution to **Valid Parentheses**. Review it for correctness, missed edge cases, and time/space complexity, then coach me toward the optimal — don't just rewrite it. Ask me to paste my code now. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔁 Drill the pattern

Lock in recognition with look-alikes.

Give me 2 problems that use the SAME underlying pattern as **Valid Parentheses**. For each, let me attempt first, then review my answer and name the trigger signal that reveals the pattern. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

← Problem 9 Make The String Great Problem 3 Decimal to Binary Conver →