Introduction
Parentheses problems often look like they require a stack, but LeetCode 1614 – Maximum Nesting Depth of the Parentheses has a much simpler solution.
The task is to find the maximum number of parentheses that are open at the same time while scanning the expression from left to right.
For example:
At one point, the digit 8 is surrounded by three pairs of parentheses:
So the maximum nesting depth is:
The key observation is simple:
- Every
(increases the current nesting depth by1. - Every
)decreases it by1. - After each character, keep track of the largest depth reached.
Because the expression is guaranteed to be valid, the parentheses will always balance correctly.
Problem Statement
Question Link -: Maximum Nesting Depth of the Parentheses
Given a valid parentheses string s, return its maximum nesting depth.
The nesting depth is the maximum number of nested parentheses present at any point in the string.
Example 1
The character 8 is inside three nested pairs of parentheses.
Example 2
The 3 is surrounded by three pairs of parentheses.
Example 3
The deepest section contains three nested pairs.
Understanding the Idea
Before writing the code, it helps to look at what nesting depth actually means.
Consider:
Walking through the string gives:
The largest value reached is 3.
So there is no need to explicitly store every pair of parentheses.
We only need two variables:
Whenever an opening parenthesis appears, increase the current depth.
Whenever a closing parenthesis appears, decrease it.
At every step, compare the current depth with the maximum seen so far.
Approach
The solution uses a single traversal of the string.
Step 1: Track the current depth
Start with:
This represents how many parentheses are currently open.
When ( is found:
When ) is found:
Step 2: Track the maximum depth
Another variable stores the deepest level reached:
After processing each character:
This ensures that an always contains the maximum nesting depth encountered so far.
Java Solution
Here is the solution:
The solution does not need a stack because the problem only asks for the maximum depth, not information about which opening parenthesis matches which closing parenthesis.
Dry Run
Let's take:
We only need to pay attention to the parentheses.
| Character | Current Depth | Maximum Depth |
( | 1 | 1 |
1 | 1 | 1 |
( | 2 | 2 |
2 | 2 | 2 |
* | 2 | 2 |
3 | 2 | 2 |
) | 1 | 2 |
+ | 1 | 2 |
( | 2 | 2 |
( | 3 | 3 |
8 | 3 | 3 |
) | 2 | 3 |
4 | 2 | 3 |
) | 1 | 3 |
) | 0 | 3 |
The maximum value reached by co is 3.
Therefore:
Why Don't We Need a Stack?
A stack is a common choice for parentheses problems, so it is worth asking whether one is necessary here.
For problems such as:
- checking whether parentheses are balanced,
- finding matching parentheses,
- reversing nested substrings,
a stack can be useful because we need to remember individual opening brackets.
Here, however, we don't care about the individual pairs.
We only care about:
How many opening parentheses are currently active?
That information can be represented by a single integer.
For example:
The counter changes like this:
The maximum is 2.
This makes the counter approach both simpler and more memory-efficient than maintaining a stack.
Complexity Analysis
Let n be the length of the string.
The string is scanned exactly once.
Time Complexity
Each character is processed once.
Space Complexity
Only two integer variables are used regardless of the size of the input.
A Pattern Worth Remembering
This problem is a good example of converting a nested structure into a simple counter.
Whenever the task asks for the maximum number of simultaneously open parentheses, the following pattern is worth recognizing:
It is particularly useful when the problem does not require identifying individual matching pairs.
Interview Tip
A useful question to ask during an interview is:
Do I need to know which bracket matches which, or do I only need the current nesting level?
If only the nesting level matters, a counter may be enough.
If individual pairs need to be tracked, a stack is usually more appropriate.
For LeetCode 1614, the counter is sufficient because the problem asks only for the maximum nesting depth.
Conclusion
LeetCode 1614 is a good reminder that not every parentheses problem requires a stack.
The entire solution comes from one observation: an opening parenthesis increases the current depth, while a closing parenthesis decreases it.
By scanning the string once and recording the largest depth reached, the problem can be solved in:
The main pattern to remember is:
A small counter is all that is needed to turn the nested-parentheses problem into a straightforward linear scan.
