What is the time complexity of Valid Parentheses?

The optimal solution has a time complexity of O(n).

What data structures are used to solve Valid Parentheses?

This problem uses String, Stack. Understanding these concepts is essential for solving this Easy problem efficiently.

What are the key insights for solving Valid Parentheses?

**Stack as a Memory for Unclosed Brackets:** The core insight is that a stack perfectly models the LIFO (Last-In, First-Out) nature of bracket nesting. When you open a bracket, you 'expect' its closure. If you open another one before closing the first, the *newest* opening bracket is the one you must close *first*. The stack stores these 'pending' open brackets in the correct order for future matching. **Efficient Type Mapping and Empty Stack Grace:** Utilizing a hash map (like `mapping` here) to quickly associate closing brackets with their required opening types (`')': '('`, etc.) is crucial for clean and fast type checking. Equally important is the robust handling of encountering a closing bracket when the stack is empty (e.g., `')abc'`). By popping `if stack else '#'`, we prevent an `IndexError` and introduce a sentinel value (`'#'`) that will never validly match an opening bracket, ensuring such cases correctly return `False`.

Which companies ask LeetCode 20. Valid Parentheses in interviews?

This problem is frequently asked at Accenture, Accolite, Adobe, Agoda, Airbnb and 88 more companies.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Valid Parentheses - LeetCode 20 Solution

Valid Parentheses - Complete Solution Guide

Valid Parentheses is LeetCode problem 20, a Easy level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

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: tr

Detailed Explanation

The "Valid Parentheses" problem challenges us to determine if a given string, composed solely of bracket characters like `(`, `)`, `{`, `}`, `[`, and `]`, is well-formed. This isn't just about ensuring an equal count of opening and closing brackets; it's crucially about their *order* and *type*. Specifically, three rules must be upheld: an open bracket must be closed by its *same type* (e.g., `(` by `)`, not `]`), brackets must be closed in the *correct nesting order* (e.g., `([{}])` is valid, but `([)]` is not), and every closing bracket must have a *corresponding open bracket* of the same type preceding it. Consider a string like `"([)]"`: while it has an equal number of open and close parentheses and square brackets, the `)` closes `(` *before* `[` is closed, violating the order. This makes the problem less about simple counting and more about managing expectations for closures.

Solution Approach

The most intuitive and elegant approach for this problem leverages a stack, mirroring how we mentally process bracket sequences. When iterating through the input string, if we encounter an *opening* bracket (`(`, `{`, `[`), we push it onto our stack. This essentially means we're "expecting" its corresponding closing bracket at some point in the future. If we instead encounter a *closing* bracket (`)`, `}`, `]`): we immediately need to check if it's the right type to close the *most recently opened* bracket. We achieve this by popping the top element from our stack. If the stack was empty when we encountered a closing bracket (e.g., `"]"`), or if the popped open bracket doesn't match the type of the current closing bracket (e.g., popping `[` for a `)`), the string is invalid. If they match, we continue. After processing the entire string, if our stack is empty, it means every opened bracket found its proper closure; otherwise, if there are still elements on the stack (e.g., `"((("`), it implies some brackets were opened but never closed, rendering the string invalid.

Step-by-Step Algorithm

Initialize an empty stack.
Iterate through the input string `s` character by character.
If the character is an opening parenthesis ('(', '[', or '{'), push it onto the stack.
If the character is a closing parenthesis (')', ']', or '}'), check if the stack is empty. If empty, return `false` (no matching opening parenthesis).
If the stack is not empty, pop the top element from the stack.
Check if the popped element matches the current closing parenthesis. If they don't match, return `false`.
After the loop, if the stack is empty, return `true`; otherwise, return `false` (unmatched opening parentheses).

Key Insights

**Stack as a Memory for Unclosed Brackets:** The core insight is that a stack perfectly models the LIFO (Last-In, First-Out) nature of bracket nesting. When you open a bracket, you 'expect' its closure. If you open another one before closing the first, the *newest* opening bracket is the one you must close *first*. The stack stores these 'pending' open brackets in the correct order for future matching.
**Efficient Type Mapping and Empty Stack Grace:** Utilizing a hash map (like `mapping` here) to quickly associate closing brackets with their required opening types (`')': '('`, etc.) is crucial for clean and fast type checking. Equally important is the robust handling of encountering a closing bracket when the stack is empty (e.g., `')abc'`). By popping `if stack else '#'`, we prevent an `IndexError` and introduce a sentinel value (`'#'`) that will never validly match an opening bracket, ensuring such cases correctly return `False`.
**Final Stack State as Validity Indicator:** The elegance culminates in the final check: `return not stack`. If the stack is empty after iterating through the entire string, it signifies that every opening bracket found its proper, corresponding closing bracket. A non-empty stack, conversely, indicates unclosed brackets (e.g., `"((("`) or mismatched pairs where an invalid sequence led to an imbalance, providing a concise ultimate verdict.

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(n)

Topics

This problem involves: String, Stack.

Companies

Asked at: Accenture, Accolite, Adobe, Agoda, Airbnb, Amazon, Anduril, Apple, Autodesk, Bank of America, Barclays, BlackRock, Bloomberg, Bolt, Booking.com, Braze, Capital One, Cisco, Cognizant, Criteo, DE Shaw, Dell, Deloitte, Disney, EPAM Systems, Epic Systems, Expedia, FreshWorks, GE Healthcare, Goldman Sachs, Google, Grab, HCL, Huawei, IBM, Infosys, Intel, Intuit, J.P. Morgan, LinkedIn, Lucid, Mastercard, Meta, Microsoft, Millennium, Mitsogo, Morgan Stanley, Nagarro, Netflix, Nike, Nvidia, Odoo, Ozon, Palo Alto Networks, PayPal, Paytm, Publicis Sapient, Qualcomm, Roblox, SAP, SOTI, Salesforce, Samsung, ServiceNow, Shopee, Siemens, Splunk, Spotify, Squarespace, Swiggy, Tencent, Tesla, ThoughtWorks, TikTok, Tripadvisor, Turing, UBS, Uber, VK, Visa, Walmart Labs, Wipro, Wix, X, Yahoo, Yandex, Zenefits, Zillow, Zoho, eBay, opentext, persistent systems, tcs.

Valid Parentheses | LeetCode 20

Easy

String Stack

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

Solution Code

Available in:

import java.util.Stack;

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            if (c == '(' || c == '[' || c == '{') {
                stack.push(c);
            } else if (c == ')' && !stack.isEmpty() && stack.peek() == '(') {
                stack.pop();
            } else if (c == ']' && !stack.isEmpty() && stack.peek() == '[') {
                stack.pop();
            } else if (c == '}' && !stack.isEmpty() && stack.peek() == '{') {
                stack.pop();
            } else {
                return false;
            }
        }
        return stack.isEmpty();
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 20: Valid Parentheses - Detailed explanation and solution approaches.

Topics

String Stack

Companies

AccentureAccoliteAdobeAgodaAirbnbAmazonAndurilApple

Stats

Difficulty:Easy

Languages:4

Companies:93

Problem #:20

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

7 steps

1
Initialize an empty stack.
2
Iterate through the input string `s` character by character.
3
If the character is an opening parenthesis ('(', '[', or '{'), push it onto the stack.
4
If the character is a closing parenthesis (')', ']', or '}'), check if the stack is empty. If empty, return `false` (no matching opening parenthesis).
5
If the stack is not empty, pop the top element from the stack.
6
Check if the popped element matches the current closing parenthesis. If they don't match, return `false`.
7
After the loop, if the stack is empty, return `true`; otherwise, return `false` (unmatched opening parentheses).

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n)

👍 Linear - Good! Visits each element once.

💾

Space Complexity

O(n)

📦 Linear space - Memory grows with input size.

📝

Why?

The dominant operation is the iteration through the string. The stack operations (push and pop) take constant time. The maximum size of the stack is proportional to the length of the input string, hence the O(n) space complexity.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Recursive Approach

A recursive approach could be implemented, but it would likely be less efficient than the iterative stack-based approach, potentially leading to stack overflow errors for very long strings.

Time: O(n)Space: O(n) in the worst case due to the recursive call stack

Trade-offs: Less efficient and more prone to stack overflow errors than the iterative approach. Should be avoided for this problem.

✨

Key Insights

1**Stack as a Memory for Unclosed Brackets:** The core insight is that a stack perfectly models the LIFO (Last-In, First-Out) nature of bracket nesting. When you open a bracket, you 'expect' its closure. If you open another one before closing the first, the *newest* opening bracket is the one you must close *first*. The stack stores these 'pending' open brackets in the correct order for future matching.
2**Efficient Type Mapping and Empty Stack Grace:** Utilizing a hash map (like `mapping` here) to quickly associate closing brackets with their required opening types (`')': '('`, etc.) is crucial for clean and fast type checking. Equally important is the robust handling of encountering a closing bracket when the stack is empty (e.g., `')abc'`). By popping `if stack else '#'`, we prevent an `IndexError` and introduce a sentinel value (`'#'`) that will never validly match an opening bracket, ensuring such cases correctly return `False`.
3**Final Stack State as Validity Indicator:** The elegance culminates in the final check: `return not stack`. If the stack is empty after iterating through the entire string, it signifies that every opening bracket found its proper, corresponding closing bracket. A non-empty stack, conversely, indicates unclosed brackets (e.g., `"((("`) or mismatched pairs where an invalid sequence led to an imbalance, providing a concise ultimate verdict.

📚

Key Terms Explained

For Students

Stack

LIFO structure - Last In, First Out. Like a stack of plates!

String

A sequence of characters. Like a word or sentence in programming!

Edge Cases

Empty String: The solution correctly handles an empty string by returning `true` because there are no parentheses to mismatch.
Uneven Number of Parentheses: The solution correctly identifies strings with an uneven number of opening and closing parentheses as invalid, returning `false`.
Mismatched Parentheses: The algorithm correctly detects mismatched parentheses (e.g., '([)]') and returns `false`.

⚠️

Common Mistakes to Avoid

✗Forgetting to check for an empty stack before popping: This can lead to a runtime error.

✗Not handling all three types of parentheses correctly: Beginners might only handle one or two types, leading to incorrect results for strings containing all three types.

✗Incorrectly handling edge cases: Not handling empty strings or strings with an uneven number of parentheses can lead to incorrect results.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Parsing programming languages: Checking for balanced parentheses in code is a common task in compilers and interpreters.

🏦Data validation: Validating data structures that use parentheses (like JSON or XML) often requires checking for balanced parentheses.

🎮Expression evaluation: Evaluating mathematical expressions often involves checking for correct parentheses balancing.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

String problems often involve sliding windows or two pointers. Consider if the character set is limited (lowercase letters = only 26 possibilities).

🎯 Interview Tip

Don't rush. Explain your thought process clearly. Easy problems are often about communication.

⚠️ Watch Out

Mutating strings directly in languages where strings are immutable. Use StringBuilder or arrays.

👨‍💻 From Experience

This is one of the first problems I solved when learning String. It's a great foundation for more complex problems.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: June 21, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

Don't forget to handle the edge case when the input is empty. Many candidates miss this in interviews.

@DevExpert92Jul 13

The key insight here is recognizing the pattern. Once you see it, the solution becomes straightforward.

@AlgoMasterJul 6

❓

Frequently Asked Questions

How do I handle string manipulation efficiently?

In languages with immutable strings (Java, Python, C#), use StringBuilder/list to avoid O(n) concatenation cost. Consider using character arrays for in-place modifications. For pattern matching, consider KMP or Rabin-Karp for O(n+m) complexity.

What problems are best solved with a stack?

Stacks excel at: matching problems (parentheses validation), next greater/smaller element, expression evaluation, backtracking, and undo operations. The key pattern is LIFO (Last In, First Out) - when you need to access the most recently added element.

How should I approach easy-level algorithm problems?

Easy problems build foundational skills. Focus on: 1) Understanding the problem completely before coding, 2) Writing clean, readable code, 3) Handling all edge cases (empty input, single element, etc.), 4) Analyzing time and space complexity. Don't skip complexity analysis even for simple solutions.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "Valid Parentheses"?

For this easy-level String problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether stack techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?