Scale Engineer

Maximum Nesting Depth of the Parentheses

Easy
#1483Time: O(N), where N is the length of the string `s`. We iterate through the string once, and stack operations (push, pop, size) take constant time on average.Space: O(D), where D is the maximum nesting depth. In the worst-case scenario, such as a string like `'((...))'`, the stack size can grow up to N/2. Therefore, the space complexity is O(N).1 company
Data structures
StringStack
Companies
Intel

Prompt

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 <= 100
  • s consists of digits 0-9 and characters '+', '-', '*', '/', '(', and ')'.
  • It is guaranteed that parentheses expression s is a VPS.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach uses a stack to explicitly track the nesting of parentheses. The depth at any point is determined by the number of elements currently in the stack. While intuitive, it's less space-efficient than the counter-based method.

Algorithm

  1. Initialize maxDepth = 0.
  2. Initialize an empty stack st.
  3. Iterate through each character c in the string s:
    • If c is '(':
      • Push c onto the stack st.
      • Update maxDepth = Math.max(maxDepth, st.size()).
    • Else if c is ')':
      • Pop an element from the stack st.
  4. Return maxDepth.

Walkthrough

We can determine the nesting depth by iterating through the string and using a stack to keep track of open parentheses.

  • Initialize a variable maxDepth to 0 and an empty stack.
  • Traverse each character of the input string s.
  • If the character is an opening parenthesis '(', push it onto the stack. The current depth is now the size of the stack. We update maxDepth with the maximum value seen so far (max(maxDepth, stack.size())).
  • If the character is a closing parenthesis ')', it signifies the end of a nested level, so we pop from the stack.
  • Other characters (digits, operators) are ignored as they do not affect the nesting structure.
  • After the loop finishes, maxDepth will contain the maximum nesting depth encountered.
import java.util.Stack; class Solution {    public int maxDepth(String s) {        int maxDepth = 0;        Stack<Character> stack = new Stack<>();        for (char c : s.toCharArray()) {            if (c == '(') {                stack.push(c);                maxDepth = Math.max(maxDepth, stack.size());            } else if (c == ')') {                stack.pop();            }        }        return maxDepth;    }}

Complexity

Time

O(N), where N is the length of the string `s`. We iterate through the string once, and stack operations (push, pop, size) take constant time on average.

Space

O(D), where D is the maximum nesting depth. In the worst-case scenario, such as a string like `'((...))'`, the stack size can grow up to N/2. Therefore, the space complexity is O(N).

Trade-offs

Pros

  • The logic is very clear and directly models the concept of nesting.

  • It's a standard way to handle parenthesis-related problems.

Cons

  • Requires extra space for the stack, which is not optimal for this specific problem.

Solutions

public class Solution {    public int MaxDepth(string s) {        int ans = 0, d = 0;        foreach(char c in s) {            if (c == '(') {                ans = Math.Max(ans, ++d);            } else if (c == ')') {                --d;            }        }        return ans;    }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem