What is the time and space complexity of Valid Parentheses?

Time complexity: O(n). Space complexity: O(n).

Valid Parentheses

Easy

Code

Loading editor...

Tap Analyze to see visualization

Click Analyze to visualize

See step-by-step execution, variables, and output

Variables

Run code to see variables

Output

Console output will appear here

Press Space to start•← → to step•? all shortcuts

Solution Guide: Valid Parentheses

Approach

Scan characters left to right and use a stack for opening brackets. For each closing bracket, pop from the stack and verify the pair matches. At the end, the stack must be empty for the string to be valid.

Complexity Analysis

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

Pattern

Stack (Bracket Matching)

Why It Works

The most recent unmatched opening bracket must be matched first, which is exactly LIFO order. Any mismatch or leftover opening bracket means invalid nesting.

Updated Feb 2026