Maximum Nesting Depth of the Parentheses solution and explanation
TCS
Google
9 more videos on this problem
maximum nesting depth of the parentheses leetcode | leetcode 1614 | stringNaresh Gupta · 4:08 · 14K views
Maximum Nesting Depth of the Parentheses | 2 Approaches | Leetcode 1614 | codestorywithMIKcodestorywithMIK · 16:49 · 12K views
Maximum Nesting Depth of the Parentheses - Leetcode 1614 - PythonNeetCodeIO · 5:39 · 9K views
6. Maximum Nesting Depth of the Parentheses | Strings - Easy | #LearnDSA | Leetcode 1614Ayushi Sharma · 5:35 · 8K views
1614. Maximum Nesting Depth of the Parentheses | Stack | ParenthesisAryan Mittal · 12:26 · 4K views
1614. Maximum Nesting Depth of the Parentheses | leetcode daily challenge | leetcode | DSAShashCode · 12:25 · 3K views
Maximum Nesting Depth of the Parentheses Leetcode 1614 videoEasyLeetcode · 5:10 · 1K views
Leetcode Solution - 1614 Maximum Nesting Depth of the ParenthesesJohn Leonardo · 3:12 · 791 views
1614. Maximum Nesting Depth of the Parentheses (Leetcode Easy)Programming Live with Larry · 2:28 · 786 views
Leetcode | 1614. Maximum Nesting Depth of the Parentheses | Easy | Java SolutionDeveloper Docs · 4:14 · 665 views
The problem
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 <= 100sconsists of digits0-9and characters'+','-','*','/','(', and')'.- It is guaranteed that parentheses expression
sis a VPS.
Approach overview
Problem Overview: Given a valid parentheses expression mixed with characters and numbers, return the maximum nesting depth of the parentheses. Depth increases every time you enter a new ( level and decreases when encountering ). The task is to scan the string and track the deepest level reached.
Approach 1: Using a Simple Counter (Time: O(n), Space: O(1))
The simplest solution tracks the current nesting level with an integer counter. Iterate through the string character by character. When you see (, increment the counter because you are entering a deeper level; update a maxDepth variable if the current level becomes larger. When you see ), decrement the counter since that nesting level closes. All other characters are ignored. This works because valid parentheses guarantee every open parenthesis eventually closes, so the counter always represents the current active depth. The algorithm performs a single pass through the string, resulting in O(n) time complexity with constant O(1) extra space.
Approach 2: Track Depth Using Stack (Time: O(n), Space: O(n))
This method uses a stack to explicitly track open parentheses. Iterate through the string and push onto the stack whenever you encounter (. The stack size represents the current nesting depth, so update the maximum depth after each push. When encountering ), pop from the stack because that level closes. The maximum size the stack reaches during traversal equals the deepest nesting level. This approach mirrors how many parentheses validation problems are solved and can be easier to reason about if you're already thinking in terms of stack-based parsing. The traversal still runs in O(n) time, but the stack can grow to O(n) space in the worst case if the expression contains many nested parentheses.
Both approaches rely on the same insight: nesting depth equals the number of currently open parentheses. The difference is whether you track that state with a simple counter or an explicit stack structure.
Recommended for interviews: The simple counter approach is the optimal solution. It runs in O(n) time and O(1) space while remaining easy to implement and reason about. Interviewers typically expect this because the stack structure is unnecessary when only the depth is required. Showing the stack-based approach first demonstrates understanding of classic parentheses parsing with a stack, then optimizing to a counter shows strong problem-solving instincts.
Approach 1: Using a Simple Counter
This approach utilizes a single counter to track the current depth of nesting while iterating through the string. Whenever an open parenthesis '(' is encountered, the counter is incremented, and whenever a closing parenthesis ')' is encountered, the counter is decremented. The maximum value of the counter at any point during the iteration is recorded as the maximum nesting depth.
def maxDepth(s: str) -> int:
current_depth = 0
max_depth = 0
for c in s:
if c == '(':
current_depth += 1
if current_depth > max_depth:
max_depth = current_depth
elif c == ')':
current_depth -= 1
return max_depth
s = "(1+(2*3)+((8)/4))+1"
print("Max Depth:", maxDepth(s))public class MaxDepth {
public static int maxDepth(String s) {
int current_depth = 0, max_depth = 0;
for (char c : s.toCharArray()) {
if (c == '(') {
current_depth++;
max_depth = Math.max(max_depth, current_depth);
} else if (c == ')') {
current_depth--;
}
}
return max_depth;
}
public static void main(String[] args) {
String s = "(1+(2*3)+((8)/4))+1";
System.out.println("Max Depth: " + maxDepth(s));
}
}#include <iostream>
#include <string>
using namespace std;
int maxDepth(string s) {
int current_depth = 0, max_depth = 0;
for (char c : s) {
if (c == '(') {
current_depth++;
max_depth = max(max_depth, current_depth);
} else if (c == ')') {
current_depth--;
}
}
return max_depth;
}
int main() {
string s = "(1+(2*3)+((8)/4))+1";
cout << "Max Depth: " << maxDepth(s) << endl;
return 0;
}function maxDepth(s) {
let currentDepth = 0, maxDepth = 0;
for (let c of s) {
if (c === '(') {
currentDepth++;
if (currentDepth > maxDepth) {
maxDepth = currentDepth;
}
} else if (c === ')') {
currentDepth--;
}
}
return maxDepth;
}
let s = "(1+(2*3)+((8)/4))+1";
console.log("Max Depth: " + maxDepth(s));#include <stdio.h>
#include <string.h>
int maxDepth(char* s) {
int current_depth = 0, max_depth = 0;
for (int i = 0; s[i] != '\0'; i++) {
if (s[i] == '(') {
current_depth++;
if (current_depth > max_depth) {
max_depth = current_depth;
}
} else if (s[i] == ')') {
current_depth--;
}
}
return max_depth;
}
int main() {
char* s = "(1+(2*3)+((8)/4))+1";
printf("Max Depth: %d\n", maxDepth(s));
return 0;
}using System;
public class Solution {
public int MaxDepth(string s) {
int current_depth = 0, max_depth = 0;
foreach (char c in s) {
if (c == '(') {
current_depth++;
max_depth = Math.Max(max_depth, current_depth);
} else if (c == ')') {
current_depth--;
}
}
return max_depth;
}
public static void Main(string[] args) {
Solution sol = new Solution();
string s = "(1+(2*3)+((8)/4))+1";
Console.WriteLine("Max Depth: " + sol.MaxDepth(s));
}
}This Python function similarly loops over each character in the string, adjusting the depth counter, and records the maximum depth encountered.
Time Complexity: O(n). Space Complexity: O(1).
Approach 2: Track Depth Using Stack
This approach uses a stack to simulate the depth of nested parentheses. Each time an open parenthesis '(' is encountered, it is pushed onto the stack, and for each closing parenthesis ')', an item is popped. The maximum size of the stack during this process reflects the maximum nesting depth.
def maxDepth(s: str) -> int:
stack = []
max_depth = 0
for c in s:
if c == '(':
stack.append(c)
max_depth = max(max_depth, len(stack))
elif c == ')':
if stack:
stack.pop()
return max_depth
s = "(1+(2*3)+((8)/4))+1"
print("Max Depth:", maxDepth(s))import java.util.Stack;
public class MaxDepth {
public static int maxDepth(String s) {
Stack<Character> stack = new Stack<>();
int maxDepth = 0;
for (char c : s.toCharArray()) {
if (c == '(') {
stack.push(c);
maxDepth = Math.max(maxDepth, stack.size());
} else if (c == ')') {
if (!stack.isEmpty()) stack.pop();
}
}
return maxDepth;
}
public static void main(String[] args) {
String s = "(1+(2*3)+((8)/4))+1";
System.out.println("Max Depth: " + maxDepth(s));
}
}#include <iostream>
#include <stack>
#include <string>
using namespace std;
int maxDepth(string s) {
stack<char> stk;
int max_depth = 0;
for (char c : s) {
if (c == '(') {
stk.push(c);
max_depth = max(max_depth, (int)stk.size());
} else if (c == ')') {
if (!stk.empty()) stk.pop();
}
}
return max_depth;
}
int main() {
string s = "(1+(2*3)+((8)/4))+1";
cout << "Max Depth: " << maxDepth(s) << endl;
return 0;
}function maxDepth(s) {
let stack = [];
let maxDepth = 0;
for (let c of s) {
if (c === '(') {
stack.push(c);
maxDepth = Math.max(maxDepth, stack.length);
} else if (c === ')') {
if (stack.length > 0) stack.pop();
}
}
return maxDepth;
}
let s = "(1+(2*3)+((8)/4))+1";
console.log("Max Depth: " + maxDepth(s));#include <stdio.h>
#include <string.h>
#define MAXLEN 100
int maxDepth(char* s) {
char stack[MAXLEN];
int top = -1;
int max_depth = 0;
for (int i = 0; s[i] != '\0'; i++) {
if (s[i] == '(') {
stack[++top] = '(';
if (top + 1 > max_depth) {
max_depth = top + 1;
}
} else if (s[i] == ')') {
if (top >= 0) top--;
}
}
return max_depth;
}
int main() {
char* s = "(1+(2*3)+((8)/4))+1";
printf("Max Depth: %d\n", maxDepth(s));
return 0;
}using System;
using System.Collections.Generic;
public class Solution {
public int MaxDepth(string s) {
Stack<char> stack = new Stack<char>();
int maxDepth = 0;
foreach (char c in s) {
if (c == '(') {
stack.Push(c);
maxDepth = Math.Max(maxDepth, stack.Count);
} else if (c == ')') {
if (stack.Count > 0) stack.Pop();
}
}
return maxDepth;
}
public static void Main(string[] args) {
Solution sol = new Solution();
string s = "(1+(2*3)+((8)/4))+1";
Console.WriteLine("Max Depth: " + sol.MaxDepth(s));
}
}Python's version utilizes a list as a stack to push and pop parentheses, tracking the maximum list (stack) length reached to find the nesting depth.
Time Complexity: O(n). Space Complexity: O(n).
Approach 3: Traversal
We use a variable d to record the current depth, initially d = 0.
Traverse the string s. When encountering a left parenthesis, increment the depth d by one and update the answer to be the maximum of the current depth d and the answer. When encountering a right parenthesis, decrement the depth d by one.
Finally, return the answer.
The time complexity is O(n), where n is the length of the string s. The space complexity is O(1).
function maxDepth(s: string): number {
let ans = 0;
let d = 0;
for (const c of s) {
if (c === '(') {
ans = Math.max(ans, ++d);
} else if (c === ')') {
--d;
}
}
return ans;
}func maxDepth(s string) (ans int) {
d := 0
for _, c := range s {
if c == '(' {
d++
ans = max(ans, d)
} else if c == ')' {
d--
}
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Using a Simple Counter | Time Complexity: O(n). Space Complexity: O(1). |
| Track Depth Using Stack | Time Complexity: O(n). Space Complexity: O(n). |
| Traversal | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Simple Counter | O(n) | O(1) | Best choice when only the maximum depth is needed. Minimal memory and single pass. |
| Stack Tracking | O(n) | O(n) | Useful when already solving related stack-based parentheses problems or when tracking structure explicitly. |
Frequently asked questions
Is Maximum Nesting Depth of the Parentheses easy or hard?
Maximum Nesting Depth of the Parentheses is classified as an Easy problem on LeetCode. It mainly tests basic string traversal and understanding of parentheses depth tracking using a counter or stack.
Maximum Nesting Depth of the Parentheses Python/Java solution
Python and Java solutions typically iterate through the string and update a counter for '(' and ')'. The algorithm maintains a running maximum depth and finishes in O(n) time with O(1) additional space.
How to solve Maximum Nesting Depth of the Parentheses in O(n)?
Traverse the string and maintain a counter representing the current number of open parentheses. Increase it when encountering '(' and decrease it when encountering ')'. Track the maximum value reached during traversal, which represents the deepest nesting level.
What is the best approach for Maximum Nesting Depth of the Parentheses?
The best approach uses a simple counter while scanning the string once. Increment the counter for '(' and decrement for ')', while tracking the maximum value reached. This runs in O(n) time and O(1) space and avoids the overhead of a stack.
Is Maximum Nesting Depth of the Parentheses asked at Google/Amazon/Meta?
Maximum Nesting Depth of the Parentheses appears in interview preparation sets and coding practice lists used by companies like Amazon, Google, and Meta. It tests basic string processing and understanding of stack-based parentheses problems.
What data structure is used in Maximum Nesting Depth of the Parentheses?
A stack can be used to track open parentheses and measure nesting depth. However, the optimal solution replaces the stack with a simple integer counter because only the depth value is needed.
What is the time complexity of Maximum Nesting Depth of the Parentheses?
The optimal solution runs in O(n) time because the string is processed once from left to right. Each character is inspected exactly once, and updates to the depth counter or stack occur in constant time.