Maximum Nesting Depth of the Parentheses
Last Updated: April 1, 2026
Understanding the Problem
We're given a string containing digits, arithmetic operators, and parentheses, and we need to find how deeply the parentheses are nested. Think of it like counting how many layers of parentheses surround the most deeply nested part of the expression.
For (1+(2*3)+((8)/4))+1, consider the character 8. To reach it, you pass through three opening parentheses: the outermost (, then the (( before 8. That's a depth of 3, and no other character sits deeper, so the answer is 3.
The key observation is straightforward: every ( increases the current depth by one, every ) decreases it by one, and we just need to track the maximum depth reached at any point.
Key Constraints:
1 <= s.length <= 100→ With n at most 100, literally any approach works. But the problem naturally lends itself to a single-pass O(n) solution, so there's no reason to overcomplicate it.s is a valid parentheses string→ We don't need to handle mismatched or invalid parentheses. Every(has a matching), which simplifies our logic significantly.
Approach 1: Using a Stack
Intuition
Parentheses problems and stacks go hand in hand. The natural first instinct is to use a stack: push when you see (, pop when you see ). The nesting depth at any moment is just the size of the stack. The maximum nesting depth is the largest the stack ever gets.
This mirrors how parentheses actually work. Each ( opens a new level, and each ) closes the current level. The stack literally represents all the currently open levels, so its size is the depth.
Algorithm
- Create an empty stack.
- Iterate through each character in the string.
- If the character is
(, push it onto the stack. - If the character is
), pop from the stack. - After each push, update the maximum depth if the stack size exceeds the current maximum.
- Return the maximum depth.
Example Walkthrough
Code
- Time Complexity: O(n). We scan through each character of the string exactly once. Push and pop operations on the stack are O(1) each.
- Space Complexity: O(n). In the worst case (a string like
(((())))with n/2 opening parentheses), the stack holds up to n/2 elements.
The stack approach works, but we never actually use the characters stored in the stack. We only care about its size. Can we replace the entire stack with a single integer counter?
Approach 2: Counter (Optimal)
Intuition
We never look at what's inside the stack. We only push ( and pop it. The only information we extract from the stack is its size. So why maintain a whole data structure when a single integer does the same job?
Replace the stack with a counter variable. Increment it on (, decrement it on ). The counter at any moment represents the current nesting depth. Track the maximum value this counter reaches, and that's our answer.
Since the input is guaranteed to be a valid parentheses string, the counter will never go negative. Every ) is matched by a previous (, so decrementing is always safe. The counter behaves identically to the stack size from Approach 1, just without the overhead of maintaining an actual data structure.
This is a pattern worth internalizing. In many parentheses and bracket problems, if all you need is the depth (not the matching positions or the actual bracket characters), a counter is the cleanest and most efficient approach.
Algorithm
- Initialize
depth = 0andmaxDepth = 0. - Iterate through each character in the string.
- If the character is
(, incrementdepthand updatemaxDepthifdepthexceeds it. - If the character is
), decrementdepth. - Return
maxDepth.
Example Walkthrough
Code
- Time Complexity: O(n). Single pass through the string, O(1) work per character.
- Space Complexity: O(1). We use only two integer variables regardless of input size.