Balanced Parentheses Problem Using Stack in DSA Typescript

Mental Model

We use a stack to keep track of opening brackets and check if each closing bracket matches the last opened one.

Analogy: Imagine stacking plates: you put a plate on top for every opening bracket, and remove the top plate when you see a matching closing bracket. If plates match perfectly, the stack ends empty.

Stack (top) -> [] (empty)
String: ( [ { } ] )

Dry Run Walkthrough

Input: string: "({[]})"

Goal: Check if all parentheses in the string are balanced and correctly nested

Step 1: Push '(' onto stack

Stack: [ '(' ]
String pointer at '{'

Why: We save the opening bracket to match later

Step 2: Push '{' onto stack

Stack: [ '(', '{' ]
String pointer at '['

Why: Another opening bracket to match later

Step 3: Push '[' onto stack

Stack: [ '(', '{', '[' ]
String pointer at ']'

Why: Keep track of nested opening bracket

Step 4: Pop '[' from stack because current char is ']' and matches top

Stack: [ '(', '{' ]
String pointer at '}'

Why: Closing bracket matches last opening bracket

Step 5: Pop '{' from stack because current char is '}' and matches top

Stack: [ '(' ]
String pointer at ')'

Why: Closing bracket matches last opening bracket

Step 6: Pop '(' from stack because current char is ')' and matches top

Stack: []
String pointer at end

Why: Closing bracket matches last opening bracket

Result:

Stack: []
All parentheses matched correctly -> Balanced

Annotated Code

DSA Typescript

class Stack {
  private items: string[] = [];

  push(element: string): void {
    this.items.push(element);
  }

  pop(): string | undefined {
    return this.items.pop();
  }

  peek(): string | undefined {
    return this.items[this.items.length - 1];
  }

  isEmpty(): boolean {
    return this.items.length === 0;
  }
}

function isBalancedParentheses(s: string): boolean {
  const stack = new Stack();
  const pairs: { [key: string]: string } = { ')': '(', ']': '[', '}': '{' };

  for (const char of s) {
    if (char === '(' || char === '[' || char === '{') {
      stack.push(char); // push opening bracket
    } else if (char === ')' || char === ']' || char === '}') {
      if (stack.isEmpty()) return false; // no matching opening
      const top = stack.pop();
      if (top !== pairs[char]) return false; // mismatch
    }
  }

  return stack.isEmpty(); // true if all matched
}

// Driver code
const input = "({[]})";
const result = isBalancedParentheses(input);
console.log(result ? "Balanced" : "Not Balanced");

stack.push(char); // push opening bracket

Add opening bracket to stack to match later

if (stack.isEmpty()) return false; // no matching opening

If closing bracket found but stack empty, no match possible

const top = stack.pop();

Remove last opening bracket to check match

if (top !== pairs[char]) return false; // mismatch

If popped bracket doesn't match closing bracket, fail

return stack.isEmpty(); // true if all matched

If stack empty at end, all brackets matched

Output

Balanced

Complexity Analysis

Time: O(n) because we scan the string once and each character is processed in constant time

Space: O(n) because in worst case all characters are opening brackets stored in stack

vs Alternative: Compared to counting brackets without stack, this method correctly handles nested and ordered pairs with linear time and space

Edge Cases

Empty string

Returns true because no brackets means balanced

DSA Typescript

return stack.isEmpty(); // true if all matched

String with only opening brackets like "((("

Returns false because stack not empty at end

DSA Typescript

return stack.isEmpty(); // true if all matched

String with closing bracket first like ")("

Returns false because stack empty when closing bracket found

DSA Typescript

if (stack.isEmpty()) return false; // no matching opening

When to Use This Pattern

When you see a problem asking if brackets or symbols are properly matched and nested, use a stack to track opening symbols and verify closing ones in order.

Common Mistakes

Mistake: Not checking if stack is empty before popping on a closing bracket
Fix: Add a check to return false if stack is empty before popping

Mistake: Comparing closing bracket directly to opening bracket without mapping pairs
Fix: Use a map/dictionary to match each closing bracket to its correct opening bracket

Summary

Checks if every opening bracket has a matching closing bracket in correct order using a stack.

Use it when you need to verify balanced and properly nested parentheses or symbols.

The key insight is to push opening brackets and pop them only when a matching closing bracket appears, ensuring order and balance.

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