Blog

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.

Bonus Tip

• If you want to upskill your Java, you should definitely check out this bestseller course