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

Time Complexity: Balanced Parentheses Problem Using Stack

O(n)

Understanding Time Complexity

We want to know how the time to check balanced parentheses grows as the input string gets longer.

Specifically, how many steps does it take to verify if parentheses are balanced?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

bool isBalanced(char* expr) {
    Stack s = createStack();
    for (int i = 0; expr[i] != '\0'; i++) {
        if (expr[i] == '(') {
            push(&s, '(');
        } else if (expr[i] == ')') {
            if (isEmpty(&s)) return false;
            pop(&s);
        }
    }
    return isEmpty(&s);
}
    

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

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

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

How Execution Grows With Input

Each character is checked once, so the steps grow directly with input size.

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: Operations increase linearly as input size increases.

Final Time Complexity

Time Complexity: O(n)

This means the time to check balanced parentheses grows in direct proportion to the input length.

Common Mistake

[X] Wrong: "The time complexity is higher because of stack operations inside the loop."

[OK] Correct: Each stack operation (push/pop) takes constant time, so they do not add extra loops or multiply the steps.

Interview Connect

Understanding this linear time check helps you handle many real-world problems involving matching pairs efficiently.

Self-Check

"What if we also had to check for multiple types of brackets like {}, [], and ()? How would the time complexity change?"