Given a valid parentheses string s, return the nesting depth of s. The nesting depth is the maximum number of nested parentheses.
Example 1:
Input: s = "(1+(2*3)+((8)/4))+1"
Output: 3
Explanation:
Digit 8 is inside of 3 nested parentheses in the string.
Example 2:
Input: s = "(1)+((2))+(((3)))"
Output: 3
Explanation:
Digit 3 is inside of 3 nested parentheses in the string.
Example 3:
Input: s = "()(())((()()))"
Output: 3
Constraints:
1 <= s.length <= 100s consists of digits 0-9 and characters '+', '-', '*', '/', '(', and ')'.s is a VPS.Problem Overview: Given a valid parentheses expression mixed with characters and numbers, return the maximum nesting depth of the parentheses. Depth increases every time you enter a new ( level and decreases when encountering ). The task is to scan the string and track the deepest level reached.
Approach 1: Using a Simple Counter (Time: O(n), Space: O(1))
The simplest solution tracks the current nesting level with an integer counter. Iterate through the string character by character. When you see (, increment the counter because you are entering a deeper level; update a maxDepth variable if the current level becomes larger. When you see ), decrement the counter since that nesting level closes. All other characters are ignored. This works because valid parentheses guarantee every open parenthesis eventually closes, so the counter always represents the current active depth. The algorithm performs a single pass through the string, resulting in O(n) time complexity with constant O(1) extra space.
Approach 2: Track Depth Using Stack (Time: O(n), Space: O(n))
This method uses a stack to explicitly track open parentheses. Iterate through the string and push onto the stack whenever you encounter (. The stack size represents the current nesting depth, so update the maximum depth after each push. When encountering ), pop from the stack because that level closes. The maximum size the stack reaches during traversal equals the deepest nesting level. This approach mirrors how many parentheses validation problems are solved and can be easier to reason about if you're already thinking in terms of stack-based parsing. The traversal still runs in O(n) time, but the stack can grow to O(n) space in the worst case if the expression contains many nested parentheses.
Both approaches rely on the same insight: nesting depth equals the number of currently open parentheses. The difference is whether you track that state with a simple counter or an explicit stack structure.
Recommended for interviews: The simple counter approach is the optimal solution. It runs in O(n) time and O(1) space while remaining easy to implement and reason about. Interviewers typically expect this because the stack structure is unnecessary when only the depth is required. Showing the stack-based approach first demonstrates understanding of classic parentheses parsing with a stack, then optimizing to a counter shows strong problem-solving instincts.
This approach utilizes a single counter to track the current depth of nesting while iterating through the string. Whenever an open parenthesis '(' is encountered, the counter is incremented, and whenever a closing parenthesis ')' is encountered, the counter is decremented. The maximum value of the counter at any point during the iteration is recorded as the maximum nesting depth.
The code iterates through each character of the string. For each '(', the depth counter is increased and checked against the current maximum depth. For each ')', the depth counter is decreased. The maximum recorded depth is returned as the result.
Time Complexity: O(n), where n is the length of the string. Space Complexity: O(1), as only a few variables are used.
This approach uses a stack to simulate the depth of nested parentheses. Each time an open parenthesis '(' is encountered, it is pushed onto the stack, and for each closing parenthesis ')', an item is popped. The maximum size of the stack during this process reflects the maximum nesting depth.
The C code uses an array as a stack to keep track of open parentheses. The depth is reflected by the top index of the stack, which indicates the number of open parentheses nested relatively.
Time Complexity: O(n). Space Complexity: O(n) due to stack usage.
We use a variable d to record the current depth, initially d = 0.
Traverse the string s. When encountering a left parenthesis, increment the depth d by one and update the answer to be the maximum of the current depth d and the answer. When encountering a right parenthesis, decrement the depth d by one.
Finally, return the answer.
The time complexity is O(n), where n is the length of the string s. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
JavaScript
C#
| Approach | Complexity |
|---|---|
| Using a Simple Counter | Time Complexity: O(n), where n is the length of the string. Space Complexity: O(1), as only a few variables are used. |
| Track Depth Using Stack | Time Complexity: O(n). Space Complexity: O(n) due to stack usage. |
| Traversal | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Simple Counter | O(n) | O(1) | Best choice when only the maximum depth is needed. Minimal memory and single pass. |
| Stack Tracking | O(n) | O(n) | Useful when already solving related stack-based parentheses problems or when tracking structure explicitly. |
maximum nesting depth of the parentheses leetcode | leetcode 1614 | string • Naresh Gupta • 14,148 views views
Watch 9 more video solutions →Practice Maximum Nesting Depth of the Parentheses with our built-in code editor and test cases.
Practice on FleetCode