Maximum Nesting Depth of the Parentheses
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. The nesting depth is the number of parentheses layers surrounding the most deeply nested part of the expression.
For (1+(2*3)+((8)/4))+1, look at the character 8. To reach it from the outside, you cross three opening parentheses: the outermost (, then the two (( just before 8. That gives a depth of 3, and no other character sits deeper, so the answer is 3.
Every ( increases the current depth by one and every ) decreases it by one. The answer is the largest depth reached at any point during a left-to-right scan.
Key Constraints:
s is a valid parentheses string→ We don't have to handle mismatched or invalid parentheses. Every)closes a previously opened(, so the running depth never goes negative. That guarantee is what lets us track depth with a single counter instead of validating structure as we go.1 <= s.length <= 100→ The bound is small, but a single left-to-right pass already solves this in O(n) time, so there is no reason to do anything heavier.
Approach 1: Using a Stack
Intuition
A stack tracks nesting directly: push on (, pop on ). At any moment the stack holds exactly the parentheses that are currently open, so its size equals the current nesting depth. The maximum nesting depth is the largest size the stack ever reaches.
Each ( opens a new level and each ) closes the innermost open level, which matches the push and pop operations one for one. Recording the peak stack size during the scan gives the deepest point in the expression.
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 never has its contents inspected. The only value read from it is its size, so the next approach replaces it with a single integer counter and drops the O(n) space.
Approach 2: Counter (Optimal)
Intuition
The stack from Approach 1 always holds copies of the same character, (, and the only thing read from it is its size. A single integer carries that same information. Increment it on (, decrement it on ), and the integer equals the current nesting depth at every step. The maximum value it reaches is the answer.
The counter equals the stack size from Approach 1 at every step, because each ( adds one to both and each ) subtracts one from both. Since the input is a valid parentheses string, every ) closes an earlier (, so the counter is non-negative throughout and matches the true nesting depth. When the depth alone is needed, rather than the positions or characters of the matched brackets, the counter replaces the stack with O(1) space.
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.