LeetCode: 20. Valid Parentheses

2026-03-02

Use a stack to validate that every closing bracket matches the most recent unmatched opening bracket.

LeetCode: 20. Valid Parentheses

LeetCode: 20. Valid Parentheses

Summary

Determine whether the input string of brackets is valid.

Approach

Use a stack.

  • If we see an opening bracket ((, {, [), push it onto the stack.
  • If we see a closing bracket (), }, ]), pop from the stack and check whether it matches.
  • If the stack is empty when a closing bracket appears, or the pair does not match, return false.

Function

Initialization:

  • stack: an array of characters.

For each character in the string s:

  • If the character is an opening bracket, push it onto stack.
  • Otherwise:
    • If stack is empty, return false.
    • Pop one bracket from stack.
    • If the popped bracket and current character are not a valid pair, return false.

After processing all characters, return true only if stack is empty.

Complexity

Time complexity: O(S), where S is the length of the input string.
Space complexity: O(S) in the worst case (all opening brackets).