How do you approach Valid Parentheses?

Use a stack to keep track of opening brackets.

What is the time complexity of Valid Parentheses?

Time complexity: O(n) - single pass through the string. Space complexity: O(n) - stack storage in worst case.

What are common mistakes on Valid Parentheses?

Popping without first checking the stack is non-empty. Ignoring what is left on the stack at the end - a non-empty stack is usually itself part of the answer. Pushing values where the problem needs indices back.

Sitelet https://gitgood.dev/coding/valid-parentheses

gitGood.dev

← Back to problems

Valid Parentheses

EasyData Structures

Description

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

An input string is valid if:

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

Example 1

Input: s = "()"

Output: true

Example 2

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

Output: true

Example 3

Input: s = "(]"

Output: false

Constraints

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

Valid Parentheses: approach, complexity and pitfalls

An easy stack problem, graded against 8 test cases (5 of them hidden).

The pattern: Stack

Last-in-first-out processing - matching, nesting, and deferred evaluation.

Reach for it when you see: Balanced brackets, nested structures, undo/back semantics, or expression evaluation.

If you are stuck

Show the 3-step hint ladder

Use a stack to keep track of opening brackets.
When you see a closing bracket, check if it matches the most recent opening bracket.
At the end, the stack should be empty for a valid string.

The optimal approach

Show the approach: Stack Approach

Use a stack to track opening brackets. When encountering a closing bracket, check if it matches the top of the stack.

Time: O(n) - single pass through the string
Space: O(n) - stack storage in worst case

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Empty string. An empty string is passed, so index reads and any assumption of at least one character are tested.

Common Stack mistakes

These apply to the pattern as a whole, not just this problem.

Popping without first checking the stack is non-empty.
Ignoring what is left on the stack at the end - a non-empty stack is usually itself part of the answer.
Pushing values where the problem needs indices back.

← Back to problems

Valid Parentheses

EasyData Structures

Description

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

An input string is valid if:

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

Example 1

Input: s = "()"

Output: true

Example 2

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

Output: true

Example 3

Input: s = "(]"

Output: false

Constraints

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

Valid Parentheses: approach, complexity and pitfalls

An easy stack problem, graded against 8 test cases (5 of them hidden).

The pattern: Stack

Last-in-first-out processing - matching, nesting, and deferred evaluation.

Reach for it when you see: Balanced brackets, nested structures, undo/back semantics, or expression evaluation.

If you are stuck

Show the 3-step hint ladder

Use a stack to keep track of opening brackets.
When you see a closing bracket, check if it matches the most recent opening bracket.
At the end, the stack should be empty for a valid string.

The optimal approach

Show the approach: Stack Approach

Use a stack to track opening brackets. When encountering a closing bracket, check if it matches the top of the stack.

Time: O(n) - single pass through the string
Space: O(n) - stack storage in worst case

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Empty string. An empty string is passed, so index reads and any assumption of at least one character are tested.

Common Stack mistakes

These apply to the pattern as a whole, not just this problem.

Popping without first checking the stack is non-empty.
Ignoring what is left on the stack at the end - a non-empty stack is usually itself part of the answer.
Pushing values where the problem needs indices back.