Search⌘ K
AI Features
Home
Courses
Data Structures & Algorithms In Go

Solution Review: Max Depth Parenthesis

Explore how to use stacks to calculate the maximum depth of nested parentheses in an expression. Understand two O(n) time complexity methods that track depth by pushing and popping parentheses or by counting depth without stack checks. Gain practical skills in stack management and algorithm optimization in Go.

We'll cover the following...

First solution

Let’s see how we can solve this problem:

  • Create a stack.

  • When we come across the open parenthesis, we insert it to the stack and increase the depth counter.

  • When we get a closing parenthesis, we pop the opening parenthesis from the stack and decrease the depth counter.

  • We keep track of the depth to find maximum depth.

Solution code

Go (1.6.2)
package main
import "fmt"
func maxDepthParenthesis(expn string, size int) int {
    stk := new(Stack)
    maxDepth := 0
    depth := 0
    var ch byte
    for i := 0; i < size; i++ {
        ch = expn[i]
        if (ch == '(') {
            stk.Push(ch)
            depth += 1
        } else if (ch == ')') {
            stk.Pop()
            depth -= 1
        }
        if (depth > maxDepth) {
            maxDepth = depth
        }
    }
    return maxDepth
}
// Testing code
func main() {
    expn := "((((A)))((((BBB()))))()()()())"
    size := len(expn)
    value :=maxDepthParenthesis(expn, size)
    fmt.Println("Given expn " , expn)
    fmt.Println("Max depth parenthesis is " , value)
}

Time complexity

The time complexity of this solution is ...