Balanced Parentheses Problem Using Stack in DSA Typescript - Deep Dive

Overview - Balanced Parentheses Problem Using Stack

What is it?

Balanced parentheses means every opening bracket like '(' has a matching closing bracket ')' in the correct order. This problem checks if a string of brackets is properly matched and nested. We use a stack, a simple data structure, to keep track of opening brackets and verify they close correctly. This helps ensure expressions or code are syntactically correct.

Why it matters

Without checking balanced parentheses, programs or expressions can have errors that cause crashes or wrong results. For example, missing a closing bracket in math or code breaks the logic. This problem helps catch such mistakes early, making software more reliable and easier to debug. It also teaches how to use stacks, a key tool in many computer tasks.

Where it fits

Before this, learners should know what stacks are and how they work (LIFO - last in, first out). After this, they can learn about parsing expressions, syntax checking, and more complex data structures like trees or graphs that build on these ideas.

Mental Model

Core Idea

Use a stack to remember opening brackets and match them with closing ones in the right order to check if parentheses are balanced.

Think of it like...

Imagine you are stacking plates. Each time you see an opening bracket, you put a plate on the stack. When you see a closing bracket, you take the top plate off. If you try to take a plate when none is there or plates remain at the end, the stack is unbalanced.

Input: ( [ { } ] )
Stack operations:
  ( -> push '('
  [ -> push '['
  { -> push '{'
  } -> pop '{'
  ] -> pop '['
  ) -> pop '('
Final stack empty -> Balanced

Build-Up - 7 Steps

1

Foundation

Understanding Parentheses Types

Concept: Introduce different types of parentheses and what balanced means.

Parentheses include round (), square [], and curly {} brackets. Balanced means every opening bracket has a matching closing bracket of the same type, and they close in the correct order. For example, '([])' is balanced but '([)]' is not.

Result

Learner knows what balanced parentheses look like and can identify simple balanced vs unbalanced strings.

Understanding the types and matching rules is essential before checking balance programmatically.

2

Foundation

Basics of Stack Data Structure

Concept: Explain stack as a last-in-first-out container to hold opening brackets.

A stack lets you add items on top and remove the top item only. Think of a stack of books: you add or remove only the top book. This fits perfectly for tracking opening brackets as you read the string left to right.

Result

Learner understands how to use a stack to remember opening brackets in order.

Knowing stack behavior is key to solving balanced parentheses efficiently.

3

Intermediate

Algorithm to Check Balanced Parentheses

🤔Before reading on: do you think we should check all characters or only brackets? Commit to your answer.

Concept: Use stack to push opening brackets and pop when matching closing brackets appear; if mismatch or leftover, not balanced.

1. Start with empty stack. 2. For each character in string: - If opening bracket, push it. - If closing bracket, check if stack top matches; if yes, pop; else, unbalanced. 3. After processing, if stack empty, balanced; else, unbalanced.

Result

Algorithm correctly identifies balanced and unbalanced strings.

This step shows how stack operations directly solve the problem by tracking unmatched openings.

4

Intermediate

Implementing Stack in TypeScript

🤔Before reading on: do you think TypeScript has a built-in stack or do we use arrays? Commit to your answer.

Concept: Use TypeScript arrays as stacks with push and pop methods to implement the algorithm.

TypeScript arrays have push() to add and pop() to remove last element, perfect for stack. We'll use an array of characters to track opening brackets.

Result

Learner can write stack-based code in TypeScript for balanced parentheses.

Knowing how to use arrays as stacks in TypeScript bridges theory to practical coding.

5

Intermediate

Handling Multiple Bracket Types

🤔Before reading on: do you think one stack can handle all bracket types or do we need separate stacks? Commit to your answer.

Concept: Use one stack and a matching map to handle all bracket types correctly.

Create a map: closing bracket -> opening bracket, e.g. ')' -> '('. When a closing bracket appears, check if stack top matches the map. This way, one stack handles all types.

Result

Algorithm correctly matches different bracket types in mixed strings.

Using a map for matching brackets simplifies code and supports multiple bracket types elegantly.

6

Advanced

Complete TypeScript Code for Balanced Parentheses

🤔Before reading on: do you think the code should return true/false or print messages? Commit to your answer.

Concept: Write full TypeScript function that returns true if balanced, false otherwise, using stack and map.

function isBalanced(s: string): boolean { const stack: string[] = []; const pairs: Record = {')': '(', ']': '[', '}': '{'}; for (const char of s) { if (['(', '[', '{'].includes(char)) { stack.push(char); } else if ([')', ']', '}'].includes(char)) { if (stack.length === 0 || stack.pop() !== pairs[char]) { return false; } } } return stack.length === 0; } // Example usage: console.log(isBalanced('({[]})')); // true console.log(isBalanced('({[})')); // false

Result

Function returns true for balanced strings and false for unbalanced ones.

Seeing the full code connects all concepts and shows a practical, reusable solution.

7

Expert

Edge Cases and Performance Considerations

🤔Before reading on: do you think empty strings or strings without brackets are balanced? Commit to your answer.

Concept: Consider empty strings, strings with no brackets, and very long strings; analyze time and space complexity.

Empty string or string without brackets is balanced by definition. The algorithm runs in O(n) time, where n is string length, because each character is processed once. Space is O(n) in worst case if all are opening brackets. This is efficient for most uses.

Result

Learner understands how the algorithm behaves in special cases and its efficiency.

Knowing edge cases and complexity prepares learners for real-world scenarios and optimization.

Under the Hood

The stack stores opening brackets as they appear. When a closing bracket comes, the algorithm checks the top of the stack to see if it matches the expected opening bracket. If it matches, the opening bracket is removed (popped). This ensures brackets close in the correct order. If a mismatch or empty stack occurs when expecting a match, the string is unbalanced. At the end, if the stack is empty, all brackets matched correctly.

Why designed this way?

Stacks naturally fit the problem because they remember the most recent opening bracket, which must be closed first. Alternatives like queues or lists would not track the order correctly. This design is simple, efficient, and easy to implement, making it a classic solution in computer science.

Input string: ( [ { } ] )

Processing:
┌─────────────┐
│ Start: []   │
├─────────────┤
│ Read '(': push '(' -> ['(']
│ Read '[': push '[' -> ['(', '[']
│ Read '{': push '{' -> ['(', '[', '{']
│ Read '}': pop '{' -> ['(', '[']
│ Read ']': pop '[' -> ['(']
│ Read ')': pop '(' -> []
├─────────────┤
│ End stack empty -> Balanced
└─────────────┘

Myth Busters - 4 Common Misconceptions

Quick: Does a string with only opening brackets count as balanced? Commit yes or no.

Common Belief: If a string has only opening brackets, it is balanced because no closing brackets mean no mismatch.

Reality: A string with only opening brackets is not balanced because each opening bracket must have a matching closing bracket.

Why it matters: Assuming only openings are balanced leads to false positives and bugs in syntax checking or expression evaluation.

Quick: Can different types of brackets close each other? Commit yes or no.

Common Belief: Any closing bracket can close any opening bracket as long as the total number matches.

Reality: Each closing bracket must match the exact type of the last opening bracket; mixing types is unbalanced.

Why it matters: Ignoring bracket types causes incorrect validation, allowing invalid expressions to pass.

Quick: Is it okay to ignore characters other than brackets when checking balance? Commit yes or no.

Common Belief: All characters must be considered when checking balanced parentheses.

Reality: Only brackets matter for balance; other characters are ignored in this problem.

Why it matters: Including non-bracket characters complicates the algorithm unnecessarily and can cause wrong results.

Quick: Does the order of brackets matter if counts are equal? Commit yes or no.

Common Belief: If the number of opening and closing brackets is equal, the string is balanced regardless of order.

Reality: Order matters; brackets must close in the correct nested order to be balanced.

Why it matters: Ignoring order leads to accepting invalid strings like '([)]' which break syntax rules.

Expert Zone

1

The stack approach can be extended to validate other paired symbols like HTML tags or quotes with slight modifications.

2

In some languages, early exit on mismatch improves performance, but in others, full parsing is needed for error reporting.

3

Handling Unicode or custom bracket pairs requires adapting the matching map and possibly normalizing input.

When NOT to use

This stack method is not suitable for checking context-sensitive grammar or nested structures with additional rules, where parsers or automata are better. For example, matching tags with attributes or recursive language syntax needs more powerful tools.

Production Patterns

In real systems, balanced parentheses checking is part of compilers, interpreters, and editors for syntax highlighting and error detection. It is often combined with tokenization and parsing stages for full language processing.

Connections

Stack Data Structure

Builds-on

Understanding balanced parentheses deepens knowledge of stack usage, showing a practical and common application.

Parsing Expressions

Builds-on

Balanced parentheses checking is a foundational step in parsing mathematical or programming expressions, enabling correct interpretation.

Human Memory and Task Management

Analogy to cognitive process

The stack mirrors how humans remember tasks in order, handling the most recent task first, which helps understand why stacks solve nested problems.

Common Pitfalls

#1 Ignoring bracket types and only counting total brackets.

Wrong approach:

function isBalanced(s: string): boolean {
let count = 0;
for (const char of s) {
if (char === '(') count++;
else if (char === ')') count--;
}
return count === 0;
}

Correct approach:

function isBalanced(s: string): boolean {
const stack: string[] = [];
const pairs: Record = {')': '(', ']': '[', '}': '{'};
for (const char of s) {
if (['(', '[', '{'].includes(char)) {
stack.push(char);
} else if ([')', ']', '}'].includes(char)) {
if (stack.length === 0 || stack.pop() !== pairs[char]) {
return false;
}
}
}
return stack.length === 0;
}

Root cause:

Misunderstanding that matching requires correct types and order, not just counts.

#2 Popping from stack without checking if it is empty first.

Wrong approach:

if (char === ')') {
if (stack.pop() !== '(') return false;
}

Correct approach:

if (char === ')') {
if (stack.length === 0 || stack.pop() !== '(') return false;
}

Root cause:

Not handling empty stack leads to runtime errors or incorrect results.

#3 Returning true immediately after matching one pair without checking the rest.

Wrong approach:

for (const char of s) {
if (char === '(') stack.push(char);
else if (char === ')') {
if (stack.pop() !== '(') return false;
else return true;
}
}
return stack.length === 0;

Correct approach:

for (const char of s) {
if (char === '(') stack.push(char);
else if (char === ')') {
if (stack.pop() !== '(') return false;
}
}
return stack.length === 0;

Root cause:

Misunderstanding that all characters must be processed before deciding balance.

Key Takeaways

Balanced parentheses means every opening bracket has a matching closing bracket in the correct order and type.

A stack is the perfect tool to track opening brackets and match them with closing ones using last-in-first-out behavior.

Using a map to match closing brackets to their opening counterparts simplifies handling multiple bracket types.

The algorithm runs efficiently in linear time and handles edge cases like empty strings or no brackets gracefully.

Common mistakes include ignoring bracket types, not checking stack emptiness before popping, and premature returns.

Practice

1. What is the core idea behind using a stack to validate balanced parentheses?

easy

A. Count total opening and closing brackets and compare

B. Push opening brackets onto the stack; when a closing bracket appears, check if the top matches

C. Sort the string and compare first and last characters

D. Use a counter that increments for '(' and decrements for ')'

Solution

1. Step 1: Stack tracks unmatched opens

   Opening brackets are pushed onto the stack. Each closing bracket must match the most recent unmatched opening bracket - the stack top.

2. Step 2: Why stack, not counter

   A counter works for a single bracket type but fails for mixed types: '([)]' has equal counts but is invalid. Stack tracks TYPE and ORDER.

3. Final Answer:

   Push open, match against stack top on close. -> Option B

4. Quick Check:

   Stack: push '(' '[' '{'. On close, pop and verify match. [OK]

Hint: Stack: push opens, pop+match on close. Counter alone fails for mixed bracket types. [OK]

Common Mistakes:

• Using a counter which fails for '([)]'
• Not checking bracket TYPE when matching
• Forgetting to check stack is empty at the end

2. What should be returned when a closing bracket is encountered but the stack is empty?

easy

A. true - the string might still be balanced

B. false - there is no matching opening bracket

C. Push the closing bracket and continue

D. Skip it and continue scanning

Solution

1. Step 1: Empty stack on close

   If we see ')' but the stack is empty, there is no unmatched opening bracket to pair with it. The string is invalid.

2. Step 2: Return false immediately

   No need to continue scanning - return false right away.

3. Final Answer:

   Return false - unmatched closing bracket. -> Option B

4. Quick Check:

   Close on empty stack = unmatched = false. [OK]

Hint: Empty stack + closing bracket = instant false. No match possible. [OK]

Common Mistakes:

• Continuing to scan (wastes time, wrong)
• Pushing closing bracket (corrupts the stack)
• Returning true (incorrect)

3. Is '([)]' a valid balanced parentheses string?

medium

A. Yes - it has equal counts of each bracket type

B. No - the brackets are nested incorrectly

C. Yes - all brackets are closed

D. Yes - opening and closing counts match

Solution

1. Step 1: Trace the stack

   Push '(': stack=['(']. Push '[': stack=['(','[']. See ')': stack top is '[' ≠ ')' - MISMATCH. Return false.

2. Step 2: Why counting fails

   Count approach: 1 '(', 1 '[', 1 ')', 1 ']' - all equal. But stack reveals the TYPE mismatch.

3. Final Answer:

   Invalid - '[' is at top when ')' arrives. -> Option B

4. Quick Check:

   Stack trace: push '(' push '[' → ')' arrives → top='[' ≠ ')' → false. [OK]

Hint: Trace stack: '([)]' → push '(' push '[' → ')' mismatches '[' → false. [OK]

Common Mistakes:

• Counting brackets and saying valid
• Not checking bracket type on pop
• Thinking equal counts = balanced

4. What is the time and space complexity of the stack-based balanced parentheses solution?

medium

A. Time O(n²), Space O(1)

B. Time O(n log n), Space O(n)

C. Time O(n), Space O(n)

D. Time O(n), Space O(1)

Solution

1. Step 1: Time

   Single pass through string: O(n). Each character: one push or one pop - O(1) each. Total: O(n).

2. Step 2: Space

   Stack can hold up to n/2 characters in worst case '((((...)))'. Space: O(n).

3. Final Answer:

   Time O(n), Space O(n). -> Option C

4. Quick Check:

   One pass = O(n). Stack = O(n) worst case. [OK]

Hint: Balanced parentheses: O(n) time (one pass), O(n) space (stack). [OK]

Common Mistakes:

• Saying O(1) space - stack can grow to O(n)
• Saying O(n²) - only one pass needed
• Confusing with sorting-based approaches

5. Which TypeScript code correctly implements the balanced parentheses check?

hard

A. return s.split('').filter(c => '({['.includes(c)).length === s.split('').filter(c => ')}]'.includes(c)).length;

B. const stack: string[] = []; const map: Record = {')':'(', ']':'[', '}':'{'}; for (const c of s) { if ('([{'.includes(c)) stack.push(c); else if (stack.pop() !== map[c]) return false; } return stack.length === 0;

C. let count = 0; for (const c of s) { if (c === '(') count++; else count--; if (count < 0) return false; } return count === 0;

D. return s.length % 2 === 0;

Solution

1. Step 1: Map for bracket pairs

   map pairs each closing bracket to its expected opening. On close: pop stack and check it matches map[c].

2. Step 2: Final check

   stack.length === 0 ensures no unmatched opening brackets remain.

3. Why A fails

   Only counts, doesn't check types or order.

4. Why C fails

   Counter only works for '()' - fails for '([)]' or mixed types.

5. Final Answer:

   Option B - map + stack with type checking. -> Option B

6. Quick Check:

   Map + stack + empty check at end = correct solution. [OK]

Hint: Use map {')':'(', ']':'[', '}':'{'} + stack. Pop on close, check match. Return stack.length===0. [OK]

Common Mistakes:

• Using count only (fails mixed brackets)
• Not checking stack empty at end (unmatched opens)
• Not using a map for bracket pairs