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
Difficulty
and has an acceptance rate of about 84% (500k+ submissions).
Typical patterns to solve this problem:
- Stack
- String
AI Disclaimer
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.
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
resultat its initial value of zero, which correctly indicates no nesting. - Strings that contain no parentheses at all also leave
resultunchanged, again yielding a depth of zero. - Inputs where closing parentheses appear before any opening parenthesis cause
depthto dip below zero, butresultstays at zero because no positive depth was ever recorded. - Balanced strings with multiple nested levels are processed correctly, with each opening parenthesis raising
depthand 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 (
+= 1and-= 1) and the built-inmaxfunction are highly optimized in Python, contributing to fast execution. - By updating
resultonly 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.
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.
Code Quality
Complexity Analysis
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
Other Solutions
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 |
Videos
Similar Problems
- problem 1111: Maximum Nesting Depth of Two Valid Parentheses Strings
Solved On The Same Day
- problem 1844: Replace All Digits with Characters
- problem 2315: Count Asterisks
- problem 2656: Maximum Sum With Exactly K Elements
- problem 1155: Number of Dice Rolls With Target Sum
Extra
- 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