# JavaScript Algorithms: Valid Parentheses (LeetCode)

# 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.

**Example 1:**

**Input:** s = "()"

**Output:** true

**Example 2:**

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

**Output:** true

**Example 3:**

**Input:** s = "(]"

**Output:** false

**Example 4:**

**Input:** s = "([)]"

**Output:** false

**Example 5:**

**Input:** s = "{[]}"

**Output:** true

**Constraints:**

`1 <= s.length <= 104`

`s`

consists of parentheses only`'()[]{}'`

.

# Solution

The best data structure here is `stack`

. Because we need to check the right order of these parentheses. For example, if we have `{][}`

the number of parentheses is correct, but the order is not.

So. the algorithm is pretty straightforward — go through these parentheses and if we see an opening character we need to push it to `stack`

, if not (closing) - we need to check whether the top of the `stack`

is a corresponding opening character.

Let’s look at the example below `{[()]}`

Let’s think about how we can optimize this solution.

We can create a `Set`

with opening characters and `Map`

with closing to opening key-value pairs. Now, we can easily understand if it’s an opening one or not. And if not we can easily figure out whether the `stack`

has the corresponding top with the opening character.

It looks better, but we can still improve it.

Instead of pushing opening characters, we can push closing characters. And when we see some closing characters we can match it with the top of the `stack`

. Thus we can reduce our codebase (use only `Map`

).

Let’s look at the same example below `{[()]}`

Let’s implement this approach:

And we can check if the `s.length`

is even or not. If not we can return false.

Now, I think it’s optimal. So, the time complexity is `O(n)`

and space complexity is `O(n)`

as well because in the worst-case scenario if we get a sequence with only opening characters `(({[([{{[(`

we’ll push all of them to the `stack`

.

I hope, it was useful for you. Thanks for reading! Looking forward to your feedback. See you soon ✌️

Enjoyed this article? If so, get more similar content by **subscribing to Decoded, our YouTube channel****!**