## 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.