Tuesday, March 3, 2015

Maximum nesting depth of a paranthesis expression

Given a parenthesis expression, We have to find the maximum nesting depth.

For example: the expression ()((()))(()) has a maximum nesting depth of 3.
The expression ((()())) has a maximum nesting depth of 3.
Let us output -1 for an unbalanced expressions such as (())) or ()(

This is a simple problem that can be asked in different forms. One such example can be
Given a sequence of jobs executed by a machine. What is the maximum number of parallel jobs executed at any point of time. 
One more variation of this problem can be
Given a maximum capacity of a computer center, and a sequence of people arrived, how many people have to wait for their turn.
Check this question for details.  
Here is the simple O(n) solution for the original problem. 
  1. Take two variables depth and max_depth initialize them to zero.
  2. Increment depth if we see an open bracket and update the max_depth
  3. Decrement depth if we see a closed bracket and check if it is going negative.If it goes negative, the expression is unbalanced.
  4. Check if depth is zero. If it is not zero, then it is not a balanced expression.
  5. Return max_depth
With minor modifications to this algorithm, we can design an algorithm for the second variation also.

Here is the Python implementation.The time complexity for this O(n) and space complexity is O(1).