Valid Parentheses

LeetCode 20 | Difficulty: Easy

Easy

Problem 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

Example 4:

Input: s = "([])"

Output: true

Example 5:

Input: s = "([)]"

Output: false

Constraints:

- `1 <= s.length <= 10^4`

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

Topics: String, Stack

---

Approach

Stack

Use a stack (LIFO) to track elements that need future processing. Process elements when a "trigger" condition is met (e.g., finding a smaller/larger element). Monotonic stack maintains elements in sorted order for next greater/smaller element problems.

When to use

Matching brackets, next greater element, evaluating expressions, backtracking history.

String Processing

Consider character frequency counts, two-pointer approaches, or building strings efficiently. For pattern matching, think about KMP or rolling hash. For palindromes, expand from center or use DP.

When to use

Anagram detection, palindrome checking, string transformation, pattern matching.

---

Solutions

Solution 1: C# (Best: 76 ms)

Metric	Value
Runtime	76 ms
Memory	21.3 MB
Date	2019-12-27

Solution

public class Solution {
    public bool IsValid(string s) {
        if(string.IsNullOrEmpty(s)) return true;
        if(s.Length%2!=0) return false;
    Stack<char> st = new Stack<char>();
    foreach (var c in s.ToCharArray())
    {
        if(c=='[') st.Push(']');
        else if (c == '(') st.Push(')');
        else if (c == '{') st.Push('}');
        else if (st.Count == 0 || st.Pop() != c) return false;
        
    }
    return st.Count == 0;
    }
}

📜 2 more C# submission(s)

Submission (2018-07-14) — 80 ms, N/A

public class Solution {
    public bool IsValid(string s) {
        if(string.IsNullOrEmpty(s)) return true;
        if(s.Length%2!=0) return false;
    Stack<char> st = new Stack<char>();
    foreach (var c in s.ToCharArray())
    {
        if(c=='[') st.Push(']');
        else if (c == '(') st.Push(')');
        else if (c == '{') st.Push('}');
        else if (st.Count == 0 || st.Pop() != c) return false;
        
    }
    return st.Count == 0;
    }
}

Submission (2017-08-01) — 162 ms, N/A

public class Solution {
    public bool IsValid(string s) {
Stack<char> st = new Stack<char>();
    foreach (var c in s.ToCharArray())
    {
        if(c=='[') st.Push(']');
        else if (c == '(') st.Push(')');
        else if (c == '{') st.Push('}');
        else if (st.Count == 0 || st.Pop() != c) return false;
        
    }
    return st.Count == 0;
    }
}

---

Complexity Analysis

Approach	Time	Space
Stack	$O(n)$	$O(n)$

---

Interview Tips

Key Points

• Start by clarifying edge cases: empty input, single element, all duplicates.
• Think about what triggers a pop: is it finding a match, or finding a smaller/larger element?
• LeetCode provides 3 hint(s) for this problem — try solving without them first.

💡 Hints

Hint 1: Use a stack of characters.

Hint 2: When you encounter an opening bracket, push it to the top of the stack.

Hint 3: When you encounter a closing bracket, check if the top of the stack was the opening for it. If yes, pop it from the stack. Otherwise, return false.