Data Structures & Algorithms In Go/

...

/

Solution Review: Max Depth Parenthesis

Solution Review: Max Depth Parenthesis

Let’s take a detailed look at the previous challenge’s solution.

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

Press + to interact
main.go
stack.go
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 ...