Maximum Nesting Depth of the Parentheses - Solution & Explanation

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.