Valid Parentheses

EasystackMetaAmazon

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

Input:s = "()[]{}"

Output:true

Hint 1

Use a stack to keep track of opening brackets.

Official asymptotic Big-O runtime and auxiliary memory analysis

Linear

Algorithmic Approach

Use a stack to track opening brackets. For every closing bracket, pop from the stack and verify that it matches the corresponding opening bracket.

Time ComplexityO(N)

Why:

Processes each character of string of length N exactly once, performing O(1) push and pop operations on the stack.

Space ComplexityO(N)

Why:

In the worst case (e.g. all opening brackets '((((('), the stack holds all N characters.

Big-O Growth CurveLinear (O(N))

Execution time scales directly in proportion to the input size.

🔍 Dry Run

Solution⏱ O(N) | 💾 O(N)

Empty