Maximum Nesting Depth of the Parentheses

How it works

We don't actually need to store the parentheses in a stack. Since we only care about the depth (stack size), we can replace the stack with a simple counter. This reduces space complexity to O(1) while maintaining the same logic.

Steps

1. Initialize res = 0 to track the maximum depth and cur = 0 to track the current depth.
2. Iterate through each character in the string.
3. If the character is (, increment cur. If it's ), decrement cur.
4. After each character, update res with the maximum of res and cur.
5. Return res.

Complexity

• Time complexity: O(n)
• Space complexity: O(1) extra space.

Things to watch for

Counting All Characters

A frequent mistake is incrementing or decrementing the depth counter for every character in the string. The string may contain digits, operators, and other characters that should be ignored. Only parentheses ( and ) affect the nesting depth.

Updating Maximum at the Wrong Time

When using a counter approach, the maximum depth should be updated after incrementing for (, not after decrementing for ). Updating after processing ) will miss the peak depth that occurred when the matching ( was processed.

class Solution:
    def maxDepth(self, s: str) -> int:
        res = 0
        cur = 0

        for c in s:
            if c == "(":
                cur += 1
            elif c == ")":
                cur -= 1
            res = max(res, cur)

        return res

class Solution {
public:
    int maxDepth(string s) {
        int res = 0, cur = 0;

        for (char c : s) {
            if (c == '(') {
                cur++;
            } else if (c == ')') {
                cur--;
            }
            res = max(res, cur);
        }

        return res;
    }
};