Skip to content

Volume ITechnology

4.8.1 — Valid Parentheses ​

LeetCode 20 · Easy · ★ Blind 75

The problem ​

You are given a string s that contains only the six bracket characters (, ), [, ], { and }. Return true if every opening bracket is closed by a bracket of the same type, in the correct order. Otherwise return false.

s = "()[]{}"   →  true
s = "(]"       →  false    (a round bracket closed by a square one)
s = "([)]"     →  false    (right types, wrong order)
s = "{[]}"     →  true     (the square pair sits neatly inside the curly pair)

The string has between 1 and 10,000 characters.

What the problem is really asking ​

Look at "([)]". It has one round pair and one square pair, so simple counting says it is fine. But it is not. The [ was opened after the (, so it must be closed before the (. Here the ) arrives while the [ is still open.

That shows the real rule. A closing bracket must always match the most recently opened bracket that is still waiting to be closed. "Most recent first" is the key phrase.

A structure that always hands back the most recent item first is a stack. A stack is like a pile of plates. You can only add a plate to the top, and you can only take the top plate off. The last plate you put on is the first one you take off. This is called last in, first out.

The brute force, and where it wastes work ​

One slow idea is to keep deleting matched pairs that sit side by side, like (), [] or {}, until nothing changes.

python
def isValid(s):
    while "()" in s or "[]" in s or "{}" in s:
        s = s.replace("()", "").replace("[]", "").replace("{}", "")
    return s == ""

On "{[]}", the first round deletes [] to give "{}", and the second deletes that to give "". Correct. But each round scans and rebuilds the whole string, and a deeply nested string like "(((...)))" needs about n/2 rounds. That is O(n^2).

The waste in one sentence: each round rescans the whole string to find the innermost pair, when a stack always knows which bracket is innermost.

The idea ​

Walk the string once.

  • When you see an opening bracket, push it onto the stack. It is now waiting to be closed.
  • When you see a closing bracket, the top of the stack must be its partner. Pop it and check. If the stack is empty, or the top is the wrong type, the string is invalid.
  • At the end, the stack must be empty. Anything left was opened and never closed.

The solution ​

python
class Solution:
    def isValid(self, s: str) -> bool:
        pairs = {')': '(', ']': '[', '}': '{'}          # (1)
        stack = []                                      # (2)

        for c in s:                                     # (3)
            if c in pairs:                              # (4)
                if not stack or stack.pop() != pairs[c]:   # (5)
                    return False
            else:                                       # (6)
                stack.append(c)

        return not stack                                # (7)
ts
function isValid(s: string): boolean {
  const pairs: Record<string, string> = { ')': '(', ']': '[', '}': '{' };  // (1)
  const stack: string[] = [];                                             // (2)

  for (const c of s) {                                                    // (3)
    if (c in pairs) {                                                     // (4)
      if (stack.pop() !== pairs[c]) return false;                         // (5)
    } else {                                                              // (6)
      stack.push(c);
    }
  }

  return stack.length === 0;                                              // (7)
}

Line by line ​

(1) A map from each closing bracket to its opening partner. It is keyed by the closing bracket because that is the direction we look things up. When we meet ), we want to know what should be on top of the stack, and the map tells us: (.

(2) The stack. A plain list works as a stack. append puts an item on top, and pop takes the top item off and returns it.

(3) Walk the string once, one character at a time.

(4) Is this a closing bracket? c in pairs checks whether c is one of the map's keys, which are exactly the three closing brackets.

(5) Check the top of the stack. Two things can go wrong, and this line catches both.

  • The stack is empty. A closer has nothing to close, as in ")". In Python, pop() on an empty list raises an error, so not stack must be checked first. Python's or stops as soon as the left side is true, so the pop never runs on an empty stack. In JavaScript, pop() on an empty array just returns undefined, which never equals a bracket, so the comparison alone catches it.
  • The top is the wrong type, as in "(]". The popped ( does not equal [, the partner of ].

Either way, the string is invalid.

(6) An opening bracket. Push it. It now waits for its partner.

(7) The stack must be empty at the end. not stack is True when the list is empty. Anything left over was opened and never closed, as in "(((". Forgetting this check is the most common bug here, and it passes most small examples.

Trace ​

Take s = "{[]}".

CharKindActionStack after
{openerpush{
[openerpush{ [
]closerpop [, partner of ] is [, match{
}closerpop {, partner of } is {, matchempty

The stack is empty at the end, so the answer is true.

Now s = "([)]".

CharKindActionStack after
(openerpush(
[openerpush( [
)closerpop [, but the partner of ) is (mismatch → false

Complexity, derived ​

Time. We visit each of the n characters once. Each visit does one map lookup and at most one push or pop, all constant time. So the time is O(n).

Space. In the worst case every character is an opener, like "((((((", and all of them end up on the stack. So the stack can hold n items, which is O(n).

Edge cases ​

  • Only closers, like ")". The stack is empty when the closer arrives, so line (5) returns false.
  • Only openers, like "((". Nothing is ever popped, so line (7) returns false.
  • Odd length. A string with an odd number of characters can never be valid, because brackets come in pairs. You can return false at the start with if len(s) % 2: return False. It is a small shortcut, not required.
  • Deep nesting, like "((((()))))". The stack grows to half the length, then empties.

Why this problem matters more than it looks ​

Nesting is everywhere, and wherever it appears, the answer is a stack.

  • Reading code. Every programming language has blocks inside blocks. The part of a compiler that reads your code checks its brackets exactly like this, with a much bigger set of "brackets". Part 3 covers how that works.
  • The call stack. When a function calls another function, the computer pushes a note of where to come back to. When that function returns, the note is popped. A call is an opener, and a return is its closer.
  • Undo. The most recent action is the first one undone.

If you can see nesting in a problem, you have already chosen your data structure.

Variations you will meet ​

  • Longest Valid Parentheses. Find the longest balanced stretch inside a string of ( and ). You push positions instead of brackets, with a starting marker at the bottom of the stack to measure lengths against.
  • Minimum Add to Make Parentheses Valid. With only one bracket type, you do not need a stack at all. Two counters are enough: how many ( are open, and how many unmatched ) you have seen.
  • Generate Parentheses. Build every valid string, instead of checking one. That is 4.8.4.

The general lesson: when the most recently opened thing must be closed first, use a stack.

What the interviewer will push on ​

"Why not just count each bracket type?" Counting misses order. "([)]" has balanced counts but is invalid.

"What are the three ways the string can fail?" A closer with an empty stack, a closer that does not match the top, and openers left at the end. Naming all three shows you thought about it.

"What if there were only round brackets?" Then one counter is enough. Add 1 for (, subtract 1 for ), fail if it ever goes below zero, and require zero at the end.

"What if the string also contains letters?" Skip anything that is not a bracket. The stack logic does not change.

One thing to volunteer: point out that the map is keyed by the closing bracket on purpose, because that is the direction you look things up when a closer arrives.

Next: 4.8.2 Min Stack. A stack that can also tell you its smallest value instantly.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet