Balanced Parentheses Problem Using Stack in DSA Python - Time & Space Complexity

Time Complexity: Balanced Parentheses Problem Using Stack

O(n)

Understanding Time Complexity

We want to know how the time needed to check balanced parentheses changes as the input string grows.

How does the number of steps grow when the string gets longer?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

def is_balanced(s: str) -> bool:
    stack = []
    pairs = {')': '(', ']': '[', '}': '{'}
    for char in s:
        if char in '([{':
            stack.append(char)
        elif char in ')]}':
            if not stack or stack.pop() != pairs[char]:
                return False
    return not stack

This code checks if the parentheses in the string are balanced using a stack.

Identify Repeating Operations

• Primary operation: Looping through each character in the string once.
• How many times: Exactly once for each character (n times for string length n).

How Execution Grows With Input

As the string gets longer, the number of steps grows directly with the number of characters.

Input Size (n)	Approx. Operations
10	About 10 checks and stack operations
100	About 100 checks and stack operations
1000	About 1000 checks and stack operations

Pattern observation: The work grows in a straight line with input size.

Final Time Complexity

Time Complexity: O(n)

This means the time to check balanced parentheses grows linearly with the length of the string.

Common Mistake

[X] Wrong: "Because of the stack operations, the time complexity is more than linear, maybe quadratic."

[OK] Correct: Each character is processed once, and stack push/pop are constant time, so total time stays linear.

Interview Connect

Understanding this linear time check shows you can analyze how data structures like stacks help solve problems efficiently.

Self-Check

"What if we checked for balanced parentheses without using a stack, by scanning multiple times? How would the time complexity change?"