Maximum Nesting Depth of the Parentheses - Practice Coding Problems

Maximum Nesting Depth of the Parentheses - Problem

String Stack Easy

Given a valid parentheses string s, return the nesting depth of s. The nesting depth is the maximum number of nested parentheses.

A valid parentheses string is a string consisting only of '(' and ')' characters where every opening parenthesis has a corresponding closing parenthesis.

Example: In the string "(1+(2*3)+((8)/4))+1", the maximum nesting depth is 3 because at one point we have three levels of nested parentheses: (((.

Input & Output

Example 1 — Mathematical Expression

$ Input: s = "(1+(2*3)+((8)/4))+1"

› Output: 3

💡 Note: The deepest nesting occurs at "((8)" where we have 3 levels: outer parentheses, plus parentheses, and inner parentheses around 8

Example 2 — Simple Nested

$ Input: s = "(1)+((2))+(((3)))"

› Output: 3

💡 Note: The string (((3))) has maximum nesting depth of 3 levels deep

Example 3 — No Nesting

$ Input: s = "1+(2*3)-(4/5)"

› Output: 1

💡 Note: All parentheses are at the same level with no nesting, so maximum depth is 1

Constraints

1 ≤ s.length ≤ 100
s consists of digits, '+', '-', '*', '/', '(', and ')'
It is guaranteed that parentheses expression is valid

Visualization

Tap to expand

Understanding the Visualization

Input String

Valid parentheses string with other characters

Track Depth

Count opening and closing parentheses

Maximum Depth

Return the highest nesting level found

Key Takeaway

🎯 Key Insight: Use a simple counter to track current nesting depth in O(1) space

Asked in

G Google 15 f Facebook 12 a Amazon 8 M Microsoft 6

The optimal approach uses a simple counter to track current depth while scanning the string once. For each '(' increment depth and update maximum, for each ')' decrement depth. Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Stack-Based Solution	O(n)	O(n)	Use a stack to track opening parentheses and compute depth
Brute Force - Check Each Position	O(n²)	O(1)	For each position, count all unclosed opening parentheses before it
Counter-Based Solution (Optimal)	O(n)	O(1)	Track current depth with a counter, no extra space needed

Stack-Based Solution — Algorithm Steps

Step 1: Initialize empty stack and max depth counter
Step 2: For each '(', push to stack and update max depth
Step 3: For each ')', pop from stack

Visualization

Tap to expand

Step-by-Step Walkthrough

Push Opening

Push '(' to stack, update max depth

Pop Closing

Pop from stack when seeing ')'

Track Maximum

Keep track of maximum stack size

Code -

solution.c — C

#include <stdio.h>
#include <string.h>

int solution(char* s) {
    int stack[1001];
    int top = -1;
    int maxDepth = 0;
    int n = strlen(s);
    
    for (int i = 0; i < n; i++) {
        if (s[i] == '(') {
            stack[++top] = 1;
            if (top + 1 > maxDepth) {
                maxDepth = top + 1;
            }
        } else if (s[i] == ')') {
            if (top >= 0) {
                top--;
            }
        }
    }
    
    return maxDepth;
}

int main() {
    char s[1001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    int result = solution(s);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through the string, each operation is O(1)

✓ Linear Growth

Space Complexity

O(n)

Stack can grow up to n/2 elements in worst case

⚡ Linearithmic Space

30.3K Views

Medium Frequency

~10 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Stack-Based Solution — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler