Maximum Nesting Depth of the Parentheses — Leetcode 1614

  • Post last modified:November 8, 2022
  • Reading time:3 mins read

Introduction

  • In this article, we will solve Leetcode 1614, which will mainly help us understand how we can use a stack data structure.
  • We will also see how we can solve it without a stack data structure.

Problem Statement

  • We have been given a Valid Parentheses String(VPS) and need to return nesting depth.
  • VPS is defined as 
    >> “” -> empty string 
    >> it is written as AB, where A and B both are valid VPS
    >> (A) -> where A is VPS

Examples

  • In the below example, the depth of parentheses is 3 since the digit 8 is nested inside of 3 parentheses.
  • Similarly in the second example, nested depth is 3, where 3 is nested parentheses.

Solutions

Intuition
Intuition is that we iterate through each character of the string and if the character happens to be open parentheses then we add it to our stack.
– When we add open parentheses to the stack, we also check if current stack size is greater than the max or not. Stack size basically depicts the depth.
– If the character happens to be closing parentheses then we can pop the last open parentheses that we added since it completes our parentheses.

Code

  • Here is the entire logic.
class Solution {
    public int maxDepth(String s) {
        Stack<Character> stack = new Stack<>();
        int max = 0;
        for(int i=0;i<s.length();i++){
            if(s.charAt(i)=='('){
                stack.push('(');
                max = Math.max(stack.size(),max);
            }else if(s.charAt(i)==')'){
                stack.pop();
            }
        }
        
        return max;
    }
}
  • We can avoid using stack since the only character we are dealing with is open and closing parentheses.
  • Instead, we can maintain open parentheses and increment whenever open parentheses encounter and decrease when closing parentheses are encountered.
class Solution {
    public int maxDepth(String s) {
        
        int depth = 0;
        int maxDepth = 0;
       
        for(int i=0;i<s.length();i++){
            if(s.charAt(i)=='('){
                depth+=1;
                maxDepth = Math.max(maxDepth, depth);
            }else if(s.charAt(i)==')'){
                depth-=1;
            }
        }
        
        return maxDepth;
    }
}

Result

  • Our solution is accepted by leetcode

Complexity

With Stack
-> Time Complexity: O(N)
-> Space Complexity: O(N)

Without Stack
-> Time Complexity: O(N)
-> Space Complexity: O(1) 

Conclusion

  • In this article, we used the stack to solve the parentheses problem. This problem is good to start problem to play with the stack data structure.
  • We also see how we can make the stack redundant if the data that is stored in the stack are not changing.

Leave a Reply