Balanced Parentheses Problem Using Stack in DSA Typescript - Execution Trace

Concept Flow - Balanced Parentheses Problem Using Stack

Start

↓

Read next char

↓

Is char '(' or '{' or '['?

Yes→Push to stack

↓

Is char ')' or '}' or '

↓

Stack empty?

Yes→Unbalanced

↓

Pop from stack and check match

↓

Match?

No→Unbalanced

↓

More chars?

Yes→Read next char

No↓

Stack empty?

Yes→Balanced

No↓

Unbalanced

The flow reads each character, pushes opening brackets to stack, pops and checks matching for closing brackets, and finally checks if stack is empty to decide balance.

Execution Sample

DSA Typescript

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

Checks if input string s has balanced parentheses using a stack.

Execution Table

Step	Operation	Current Char	Stack Before	Stack After	Action	Visual State
1	Read char	(	[]	(	Push '('	( ) -> [ ( ]
2	Read char	[	(	(, [	Push '['	( ) -> [ ( ] -> [ [ ]
3	Read char	]	(, [	(	Pop '[' and match with ']'	( ) -> [ ( ]
4	Read char	)	(		Pop '(' and match with ')'	( ) -> [ ]
5	End of string				Stack empty, balanced	( ) -> [ ]

💡 End of string reached and stack is empty, so parentheses are balanced.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	Final
stack	[]	(	(, [	(
current char		(	[	]	)

Key Moments - 3 Insights

Why do we push only opening brackets to the stack?

Because opening brackets mark a new group that must be closed later. This is shown in execution_table steps 1 and 2 where '(' and '[' are pushed.

What happens if we find a closing bracket but the stack is empty?

It means there is no matching opening bracket, so the string is unbalanced. This is checked in the code before popping, as shown in execution_table step 3.

Why do we check if the popped bracket matches the current closing bracket?

To ensure correct pairing of brackets. If they don't match, the string is unbalanced. This is shown in execution_table step 3 and 4 where matching is verified.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what is the stack after popping?

A (

B

C ([

D [

💡 Hint

Check the 'Stack After' column at step 3 in execution_table.

At which step does the stack become empty again?

A Step 2

B Step 3

C Step 4

D Step 5

💡 Hint

Look at the 'Stack After' column to see when it becomes [].

If the input string started with a closing bracket, what would happen at step 1?

A Push closing bracket to stack

B Return false immediately

C Pop from empty stack

D Ignore the character

💡 Hint

Refer to the code logic and execution_table where stack length is checked before popping.

Concept Snapshot

Balanced Parentheses Using Stack:
- Push opening brackets '(' '{' '[' onto stack
- For closing brackets ')', '}', ']', pop and check match
- If mismatch or pop from empty stack, unbalanced
- At end, if stack empty, balanced; else unbalanced

Full Transcript

This concept uses a stack to check if parentheses in a string are balanced. We read each character. If it is an opening bracket, we push it onto the stack. If it is a closing bracket, we pop from the stack and check if it matches. If not, or if the stack is empty when popping, the string is unbalanced. After processing all characters, if the stack is empty, the string is balanced. The execution table shows each step with stack state and actions. Key moments clarify why we push only opening brackets, what happens if stack is empty on pop, and why matching is checked. The visual quiz tests understanding of stack changes and error cases.

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