Maximum Nesting Depth of Parentheses - Visualization

Visualization Player

Problem Statement

Given a valid parentheses string s, your task is to find the maximum nesting depth of parentheses in the string.

  • The nesting depth of a string is the maximum number of parentheses that are open at the same time.
  • Only the characters ( and ) affect the nesting depth. Other characters are ignored.

Return 0 if the string is empty or contains no parentheses.

Examples

Input String Maximum Nesting Depth Description
"(1+(2*3)+((8)/4))+1" 3 Deepest level is ((8)/4) → depth 3
"(1)+((2))+(((3)))" 3 Increasing levels of nested brackets
"1+(2*3)/(2-1)" 1 Only one pair of parentheses at a time
"1+2-3" 0 No parentheses present
"" 0 Empty string returns 0
"(()(()))" 3 Nested parentheses with maximum 3 levels
(a+(b*(c+(d)))) 4 Characters ignored, structure leads to depth 4

Solution

Understanding the Problem

We are given a string that may contain a mix of characters, including parentheses ( and ). Our goal is to determine the maximum nesting depth of parentheses in the string.

But what exactly does "nesting depth" mean? It refers to the number of parentheses that are open at the same time during the reading of the string. Think of it like keeping track of how deep inside layers of parentheses we are.

For example, in the expression ((a + b)), when we reach the innermost a + b, we are two layers deep — that's a nesting depth of 2.

Step-by-Step Solution with Example

Step 1: Initialize two variables

We need to track:

  • currentDepth: How many parentheses are currently open.
  • maxDepth: The maximum value that currentDepth reaches throughout the string.
We start both at 0.

Step 2: Traverse the string character by character

Loop through the string. For each character:

  • If it's an opening bracket (, we increase currentDepth by 1.
  • Update maxDepth if currentDepth exceeds it.
  • If it's a closing bracket ), we decrease currentDepth by 1.
  • Ignore all other characters.

Step 3: Example Walkthrough

Let’s take the example string: (1+(2*3)+((8)/4))+1

We scan from left to right:

Char (   → currentDepth = 1 → maxDepth = 1  
Char 1   → skip  
Char +   → skip  
Char (   → currentDepth = 2 → maxDepth = 2  
Char 2   → skip  
Char *   → skip  
Char 3   → skip  
Char )   → currentDepth = 1  
Char +   → skip  
Char (   → currentDepth = 2  
Char (   → currentDepth = 3 → maxDepth = 3 ✅  
Char 8   → skip  
Char )   → currentDepth = 2  
Char /   → skip  
Char 4   → skip  
Char )   → currentDepth = 1  
Char )   → currentDepth = 0  
Char +   → skip  
Char 1   → skip

Final maxDepth = 3. So, the maximum nesting is 3.

Edge Cases

  • Empty String: No parentheses → nesting depth is 0.
  • No parentheses at all: For example, "abc+123" → depth is 0.
  • Only one pair: "(x)" → depth is 1.
  • Deep nesting: "((((x))))" → depth is 4.
  • Invalid or mismatched parentheses: If we assume valid input only, we don’t handle errors. But ideally, if we encounter a closing ) without a matching open (, we should either ignore or throw an error based on problem constraints.

Finally

The beauty of this problem is its simplicity. You don't need a complex data structure like a stack — just a simple counter to track the current level of nesting. It's a classic example of how a linear pass through a string with just a few variables can solve what seems like a tricky problem.

The overall time complexity is O(n), where n is the length of the string, and the space complexity is O(1).

Algorithm Steps

  1. Initialize two variables: depth = 0 and maxDepth = 0.
  2. Loop through each character ch in the string s.
  3. If ch == '(', increment depth and update maxDepth if depth > maxDepth.
  4. If ch == ')', decrement depth.
  5. Return maxDepth at the end.

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>

int maxDepth(const char* s) {
    int depth = 0, maxDepth = 0;
    for (int i = 0; s[i] != '\0'; i++) {
        if (s[i] == '(') {
            depth++;
            if (depth > maxDepth)
                maxDepth = depth;
        } else if (s[i] == ')') {
            depth--;
        }
    }
    return maxDepth;
}

int main() {
    const char* input = "(1+(2*3)+((8)/4))+1";
    printf("%d\n", maxDepth(input));  // Output: 3
    return 0;
}

Time Complexity

CaseTime ComplexityExplanation
Best CaseO(n)We must scan every character once, even if there are few or no parentheses.
Average CaseO(n)Each character is checked, and counters are updated accordingly.
Worst CaseO(n)Even with maximum depth and complexity, each character is visited once.

Space Complexity

O(1)

Explanation: Only a few counters are used. No extra data structures like stacks are required.


Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.


Loading comments...