Maximum Nesting Depth of the Parentheses
WHAT IT SAYS
Given a valid parenthesis expression containing digits and operators, return its maximum nesting depth.
WHAT IT'S REALLY ASKING
"You never need to know which '(' matched which ')'. You only need to know how deep you were standing at each instant — and depth is just a running count of what is still open. So the answer is the high-water mark of a single integer."
Match the brackets, then measure
O(n^2) time, O(n) spaceFor each '(', scan forward to find its partner ')'. Then, for each pair, count how many other pairs enclose it. The largest enclosure count is the depth.
WHERE THE WORK IS WASTED — Both halves re-derive a number you could have carried for free. Finding a partner means rescanning the string; counting the enclosing pairs means recounting the brackets in the prefix. But 'how many pairs enclose position i' is exactly the running balance at i — a value that a single left-to-right sweep would have handed you at every index, for the cost of one addition. You are rebuilding a running total from scratch, at every index, by rescanning.
One bracket type means the stack collapses to a counter.
Define the balance at position i as the number of '(' minus the number of ')' in everything up to and including i. Claim: the nesting depth at position i IS the balance. Why? The brackets currently 'open' are precisely those that have been opened and not yet closed — and in a valid expression, a ')' always closes the most recently opened '(', so no bracket is ever skipped or left dangling. That means the SET of open brackets is fully determined by how many of them there are. Their identities carry no extra information, because they are all the same character. So a stack here would push n items you never look at. You would only ever call size() on it. And an object you only ever call size() on is an integer. The nesting depth of the whole expression is therefore the largest balance the string ever reaches — a high-water mark, not a structure. Everything that is not a bracket contributes nothing and can be ignored outright. Notice exactly where this collapse would break. Add a second bracket type, '[', and the count is suddenly worthless: closing a ']' has to check WHAT is open, not just how much. That is the whole difference between this problem and Valid Parentheses, and it is a good test of whether you understand why the counter is legal here.
One counter, one max
O(n) time, O(1) space, one passWalk the string. On '(', increment the depth and update the maximum immediately after (the peak is reached the moment a bracket opens, not later). On ')', decrement. Ignore every other character. The maximum you recorded is the answer.
The Stack Is Just a Counter
YOU'LL SEE IT AGAIN WHEN
- You walk a nested or balanced structure but only ever ask 'how deep' or 'is it balanced' — never 'what is currently on top'.
- There is only one kind of bracket or symbol, so the identity of what is open carries no information beyond how much of it there is.
- The answer is a max or min of a running quantity — a high-water mark — rather than a structure you have to build.