Maximum Nesting Depth of the Parentheses | Leetcode 1614 | Depth Counting Solution

The Maximum Nesting Depth of the Parentheses problem asks us to determine the deepest level of nested parentheses in a valid parentheses string.

• You are given a string s consisting of digits and parentheses.
• The nesting depth is the maximum number of open parentheses before they get closed.
• Return the maximum depth of valid parentheses.

Here’s the [Problem Link] to begin with.

Examples

Example 1

Input: s = "(1+(2*3)+((8)/4))+1"
Output: 3
Explanation: The deepest valid nesting is "((8)/4)" which has depth 3.

Example 2

Input: s = "(1)+((2))+(((3)))"
Output: 3
Explanation: Maximum nesting occurs with "(((3)))".

Example 3

Input: s = "1+(2*3)/(2-1)"
Output: 1
Explanation: Only single-level parentheses exist.

Example 4

Input: s = "1"
Output: 0
Explanation: No parentheses present, so depth is 0.

Intuition and Approach

The main idea is to track how deeply we are nested inside parentheses while traversing the string.

1. Use two counters:
   • curr_depth: Keeps track of the current level of nesting.
   • max_depth: Keeps track of the maximum nesting depth seen so far.
2. Traverse the string:
   • If you encounter '(', increase curr_depth.
   • Update max_depth as the maximum of max_depth and curr_depth.
   • If you encounter ')', decrease curr_depth.
3. Final answer:
   • After processing the entire string, max_depth will hold the maximum nesting depth.

This is a simple and efficient solution since we only scan the string once.

Code Implementation

class Solution:
    def maxDepth(self, s: str) -> int:
        max_depth = 0
        curr_depth = 0
        for brac in s:
            if brac == "(":
                curr_depth += 1
                max_depth = max(max_depth, curr_depth)
            elif brac == ")":
                curr_depth -= 1
        return max_depth

Code Explanation

• Initialize max_depth = 0 and curr_depth = 0.
• Loop through every character in s.
• When '(' appears, increment curr_depth and update max_depth.
• When ')' appears, decrement curr_depth because one nested level ends.
• Return max_depth at the end.

Dry Run

Input: s = "(1+(2*3)+((8)/4))+1"

• '(' → curr_depth = 1, max_depth = 1
• '(' → curr_depth = 2, max_depth = 2
• '(' → curr_depth = 3, max_depth = 3
• ')' → curr_depth = 2
• ')' → curr_depth = 1
• End of string → return 3.

Output: 3

Time and Space Complexity

• Time Complexity:
  • We scan the string once → O(N), where N is the length of s.
• Space Complexity:
  • Only two counters are used → O(1).

Conclusion

The Maximum Nesting Depth of the Parentheses problem is solved efficiently by using a counter-based approach.

• Increase depth when encountering '('.
• Decrease depth when encountering ')'.
• Keep track of the maximum depth at every step.

This gives us the correct answer in O(N) time and O(1) space, making it an optimal solution for this problem.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.