Jobs

Interviews

Discussions

Maximum Nesting Depth of the Parentheses

Easy

Intel

2 views

Topics:

StringsStacks

Given a valid parentheses string s, return the nesting depth of s. The nesting depth is the maximum number of nested parentheses.

Example 1:

Input: s = "(1+(2*3)+((8)/4))+1"

Output: 3

Explanation:

Digit 8 is inside of 3 nested parentheses in the string.

Example 2:

Input: s = "(1)+((2))+(((3)))"

Output: 3

Explanation:

Digit 3 is inside of 3 nested parentheses in the string.

Example 3:

Input: s = "()(())((()()))"

Output: 3

Constraints:

1 <= s.length <= 100
s consists of digits 0-9 and characters '+', '-', '*', '/', '(', and ')'.
It is guaranteed that parentheses expression s is a VPS.

Try coding it in LeetCode

Maximum Nesting Depth of the Parentheses

Easy

Intel

2 views

Topics:

StringsStacks

Given a valid parentheses string s, return the nesting depth of s. The nesting depth is the maximum number of nested parentheses.

Example 1:

Input: s = "(1+(2*3)+((8)/4))+1"

Output: 3

Explanation:

Digit 8 is inside of 3 nested parentheses in the string.

Example 2:

Input: s = "(1)+((2))+(((3)))"

Output: 3

Explanation:

Digit 3 is inside of 3 nested parentheses in the string.

Example 3:

Input: s = "()(())((()()))"

Output: 3

Constraints:

1 <= s.length <= 100
s consists of digits 0-9 and characters '+', '-', '*', '/', '(', and ')'.
It is guaranteed that parentheses expression s is a VPS.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input string `s` be empty or null?
Besides '(' and ')', can the input string `s` contain any other characters?
If the parentheses are unbalanced (e.g., '(()' or ')(('), what should the function return?
What is the maximum length of the input string `s`?
Is it safe to assume that memory is not a constraint?

Brute Force Solution

Approach

The brute force approach to finding the maximum nesting depth of parentheses involves checking every possible combination of parentheses and keeping track of the deepest level we encounter. We essentially explore all possible paths to see which one gives us the highest depth. The approach exhaustively simulates all possible arrangements and validates each one.

Here's how the algorithm would work step-by-step:

Go through the entire string of parentheses one character at a time.
Whenever you encounter an opening parenthesis, imagine you're going one level deeper.
Whenever you encounter a closing parenthesis, imagine you're going one level back up.
At each character, check how deep you currently are. Maintain and update the largest depth found so far.
Continue this process for every character in the string, keeping track of the maximum depth seen at any point.

Code Implementation

def maximum_nesting_depth_brute_force(parenthesis_string):
    maximum_depth = 0
    current_depth = 0

    for character in parenthesis_string:
        if character == '(': 
            # Increase depth when an opening parenthesis is encountered
            current_depth += 1

            if current_depth > maximum_depth:
                # Keep track of the largest depth seen so far
                maximum_depth = current_depth

        elif character == ')':
            # Reduce depth when a closing parenthesis is encountered
            current_depth -= 1

    return maximum_depth

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input string of length n once. For each character, it performs a constant amount of work: incrementing or decrementing the current depth and updating the maximum depth found so far. Therefore, the time complexity is directly proportional to the length of the string, resulting in O(n).

Space Complexity

O(1) – The provided algorithm iterates through the input string, maintaining only two integer variables: the current depth and the maximum depth encountered so far. These variables store numerical values independent of the input string's length. Thus, the algorithm uses a constant amount of extra memory regardless of the input size N, where N is the length of the string. Therefore, the space complexity is O(1).

Optimal Solution

Approach

The core idea is to keep track of how deeply nested we are at each point in the string. We increase the nesting level when we see an opening parenthesis and decrease it when we see a closing one. The maximum depth seen at any point is the answer.

Here's how the algorithm would work step-by-step:

Start with the nesting depth at zero.
Also, start with the maximum depth at zero.
Go through the string, character by character.
If you see an opening parenthesis, increase the current nesting depth by one.
After increasing the depth, if the current depth is now bigger than the maximum depth we've seen so far, update the maximum depth.
If you see a closing parenthesis, decrease the current nesting depth by one.
After going through the whole string, the maximum depth will be the answer.

Code Implementation

def max_depth_parentheses(input_string):
    current_nesting_depth = 0
    maximum_nesting_depth = 0

    for character in input_string:
        if character == '(': 
            # Increase depth for opening parenthesis
            current_nesting_depth += 1

            #Update max depth if necessary
            if current_nesting_depth > maximum_nesting_depth:
                maximum_nesting_depth = current_nesting_depth

        elif character == ')':
            # Decrease depth for closing parenthesis
            current_nesting_depth -= 1

    return maximum_nesting_depth

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input string once. The cost of each iteration is constant, involving simple comparisons and increment/decrement operations. The number of iterations is directly proportional to the length of the string, denoted as n. Therefore, the time complexity is O(n).

Space Complexity

O(1) – The algorithm uses a fixed number of integer variables: one to track the current nesting depth and another to store the maximum depth encountered so far. Regardless of the length of the input string (N), the space used by these variables remains constant. Therefore, the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
Null or empty input string	Return 0 as there are no parentheses to calculate depth for.
Input string with only closing parentheses	Return 0 as there are no opening parentheses to establish nesting.
Input string with only opening parentheses	The algorithm should correctly process all open parentheses adding to depth, without errors.
Input string with no parentheses at all	Return 0 as there are no parentheses.
Input string with unmatched parentheses (e.g., '(()')	The algorithm should calculate the maximum depth reached before the string ends, correctly handling the imbalanced state.
Input string with interleaved balanced and unbalanced parentheses e.g. '(())(')	The algorithm correctly keeps track of the current depth and resets it as necessary when it encounters a closing parenthesis.
Input string containing characters other than '(' and ')'	The algorithm only considers '(' and ')', ignoring other characters, ensuring incorrect characters are not calculated into the maximum depth.
Maximum nesting depth exceeds the maximum integer value	Use appropriate data type to store the depth (e.g. long, or language specific safety features) to prevent potential overflow.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input string `s` be empty or null?
Besides '(' and ')', can the input string `s` contain any other characters?
If the parentheses are unbalanced (e.g., '(()' or ')(('), what should the function return?
What is the maximum length of the input string `s`?
Is it safe to assume that memory is not a constraint?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Go through the entire string of parentheses one character at a time.
Whenever you encounter an opening parenthesis, imagine you're going one level deeper.
Whenever you encounter a closing parenthesis, imagine you're going one level back up.
At each character, check how deep you currently are. Maintain and update the largest depth found so far.
Continue this process for every character in the string, keeping track of the maximum depth seen at any point.

Code Implementation

def maximum_nesting_depth_brute_force(parenthesis_string):
    maximum_depth = 0
    current_depth = 0

    for character in parenthesis_string:
        if character == '(': 
            # Increase depth when an opening parenthesis is encountered
            current_depth += 1

            if current_depth > maximum_depth:
                # Keep track of the largest depth seen so far
                maximum_depth = current_depth

        elif character == ')':
            # Reduce depth when a closing parenthesis is encountered
            current_depth -= 1

    return maximum_depth

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Start with the nesting depth at zero.
Also, start with the maximum depth at zero.
Go through the string, character by character.
If you see an opening parenthesis, increase the current nesting depth by one.
After increasing the depth, if the current depth is now bigger than the maximum depth we've seen so far, update the maximum depth.
If you see a closing parenthesis, decrease the current nesting depth by one.
After going through the whole string, the maximum depth will be the answer.

Code Implementation

def max_depth_parentheses(input_string):
    current_nesting_depth = 0
    maximum_nesting_depth = 0

    for character in input_string:
        if character == '(': 
            # Increase depth for opening parenthesis
            current_nesting_depth += 1

            #Update max depth if necessary
            if current_nesting_depth > maximum_nesting_depth:
                maximum_nesting_depth = current_nesting_depth

        elif character == ')':
            # Decrease depth for closing parenthesis
            current_nesting_depth -= 1

    return maximum_nesting_depth

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input string	Return 0 as there are no parentheses to calculate depth for.
Input string with only closing parentheses	Return 0 as there are no opening parentheses to establish nesting.
Input string with only opening parentheses	The algorithm should correctly process all open parentheses adding to depth, without errors.
Input string with no parentheses at all	Return 0 as there are no parentheses.
Input string with unmatched parentheses (e.g., '(()')	The algorithm should calculate the maximum depth reached before the string ends, correctly handling the imbalanced state.
Input string with interleaved balanced and unbalanced parentheses e.g. '(())(')	The algorithm correctly keeps track of the current depth and resets it as necessary when it encounters a closing parenthesis.
Input string containing characters other than '(' and ')'	The algorithm only considers '(' and ')', ignoring other characters, ensuring incorrect characters are not calculated into the maximum depth.
Maximum nesting depth exceeds the maximum integer value	Use appropriate data type to store the depth (e.g. long, or language specific safety features) to prevent potential overflow.