Problem 1614

Abstract / Summary

Find the deepest level of nested parentheses in a given string of parentheses.

Note

The full problem description, including helpful examples, can be found on LeetCode.

Python 1614.py

class Solution:
    def maxDepth(self, s: str) -> int:
        result = 0
        depth  = 0
        for c in s:
            if c == "(":
                depth += 1
                result = max(result, depth)
            elif c == ")":
                depth -= 1
        return result
11 lines | 296 bytes | submitted December 26, 2023 | GitHub   tab size 4 | low complexity

Difficulty

This problem is ranked as
easy medium hard

and has an acceptance rate of about 84% (500k+ submissions).

Typical patterns to solve this problem:
  • Stack
  • String
I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.
LeetCode profile | GitHub repo

Code Walkthrough

Overview

The provided implementation computes the maximum nesting depth of parentheses in a given string. It walks through the characters once, maintaining a running count of the current nesting level and recording the highest level encountered. The algorithm is concise, relies on primitive integer operations, and returns the depth as an integer.

Initialization

At the start of the method two integer variables are created. result holds the deepest level seen so far, while depth tracks the current nesting depth while iterating.

result = 0
depth  = 0

Both are initialized to zero, which correctly represents an empty or non-parenthetical input where the maximum depth is zero.

Traversal

The core of the solution is a for loop that examines each character in the input string sequentially.

for c in s:

Processing characters one by one ensures that the algorithm respects the order of parentheses, which is essential for accurate depth calculation.

Depth Update on Opening Parenthesis

When an opening parenthesis '(' is encountered, the current depth is increased. Immediately after the increment, result is updated with the larger of its current value and the new depth. This guarantees that result always reflects the deepest nesting observed up to that point.

if c == "(":
    depth += 1
    result = max(result, depth)

The use of the built-in max function provides a clear and efficient way to keep the maximum without additional conditional branches.

Depth Update on Closing Parenthesis

A closing parenthesis ')' reduces the current nesting level. The decrement is performed unconditionally, which correctly balances a previously seen opening parenthesis.

elif c == ")":
    depth -= 1

If the input contains more closing than opening parentheses, depth may become negative, but result remains unaffected because it only records positive depths. This behavior gracefully handles strings that are not perfectly balanced without raising errors.

Return Value

After the loop finishes, the method returns the recorded maximum depth.

return result

The returned integer represents the deepest level of nested parentheses present in the input string.

Edge Cases Handled

The algorithm naturally accommodates several edge conditions:

  • An empty string results in the loop body never executing, leaving result at its initial value of zero, which correctly indicates no nesting.
  • Strings that contain no parentheses at all also leave result unchanged, again yielding a depth of zero.
  • Inputs where closing parentheses appear before any opening parenthesis cause depth to dip below zero, but result stays at zero because no positive depth was ever recorded.
  • Balanced strings with multiple nested levels are processed correctly, with each opening parenthesis raising depth and each closing parenthesis lowering it, ensuring that the maximum depth reflects the deepest point of nesting.

Performance Optimizations

The implementation exhibits several efficiency choices:

  • A single linear pass over the input string eliminates the need for auxiliary data structures such as stacks, keeping memory usage constant.
  • Integer arithmetic (+= 1 and -= 1) and the built-in max function are highly optimized in Python, contributing to fast execution.
  • By updating result only when an opening parenthesis is seen, the code avoids unnecessary comparisons for characters that do not affect nesting depth.
  • The absence of function calls or complex conditionals inside the loop reduces overhead, allowing the interpreter to execute the loop body with minimal instruction count.

Overall, the solution delivers a straightforward, low-overhead computation of maximum parenthesis depth.

written by openai gpt

ELI5 - Simplified Explanation

Imagine that this code is looking at a long line of tiny toy blocks stacked inside each other like Russian dolls. The code starts with two empty boxes called result and depth that both start at zero. It walks along a line of symbols one by one. When it sees an opening bracket, that is like opening a doll to find another one hiding inside, so it adds one to the depth count. Then it checks if this is the deepest stack seen so far and saves that number in the result box. When it sees a closing bracket, that is like putting a doll back together, so it takes one away from the depth count. It keeps going until all the symbols have been checked to see how many layers deep the nesting goes.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 27 | median = 8 | μ = 8.15 | σ = 1.27

Complexity Analysis

Time: linear
As a rule of thumb, the maximum input size for one second execution time is
  • factorial: up to 10 elements
  • exponential: up to 20 elements
  • polynomial: a few thousand elements
  • loglinear: up to 100,000 elements
  • linear: a few million elements
  • logarithmic: a billion elements
  • constant: practically unlimited
generated automatically

Other Solutions

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)
author
author solutions
www AlgoMonster Python C++ Java TS
WalkCCC Python C++ Java
leetcode.ca Python C++ JS Java Go C# TS
Progiez Python C++ Java
github black-shadows C++
chandansgowda Python
charles-wangkai Java
DimitrisJim C
everthis JS
fartem Ruby
fsq C++
halfrost Go
JoshCrozier JS
keineahnung2345 C++
Krazune C++
lkwq007 Python
muhammadfarhankt Go
pruthvikp Python
suxrobGM C#
trung-hn Python
varunu28 Java
YuriSpiridonov Python
AlgoMonster C++, Python, Java, TypeScript
WalkCCC C++, Python, Java
leetcode.ca C++, C#, Go, Java, JavaScript, Python, TypeScript
Progiez C++, Java, Python
black-shadows C++, C++
chandansgowda Python
charles-wangkai Java
DimitrisJim C
everthis JavaScript
fartem Ruby
fsq C++
halfrost Go
JoshCrozier JavaScript
keineahnung2345 C++
Krazune C++
lkwq007 Python
muhammadfarhankt Go
pruthvikp Python
suxrobGM C#
trung-hn Python
varunu28 Java
YuriSpiridonov Python
35 links | 22 authors | 9 languages

Videos

7 videos   did my crawler come up with invalid videos ? drop me a line.

Similar Problems

1 similar problem

Solved On The Same Day

5 solutions   December 26, 2023

Extra

There are a few extra pages giving you some insights into my setup:
  • Tech Stack - my development environment and tools
  • AI - how AI helped me create this website (NOT solving the problems)
  • Progress - progression over time
  • Quality - code quality