Count Number of Valid Parenthesis

Last Updated: May 22, 2022
Difficulty Level :
MEDIUM

Introduction

A pair of parentheses is considered valid only if there is a right parenthesis for every left one and the left parenthesis occurs before the right one in the sequence. The matched pairs have to be properly nested. The following problem states that for any given integer ‘N', we need to find the number of valid expressions of parenthesis. The length of the expression is equal to N, and the expression consists of only valid parenthesis.

Let’s dive right into the problem.

Problem Statement

Given an integer ‘N’. You need to find the total number of valid parenthesis expressions of length ‘N’.

Example

Suppose N=6.

For N=6, the output will be 5.

Explanation

For N=6, we have the following 6 valid parentheses expressions.

  • ( ( ( ) ) ) 
  • ( ( ) ( ) ) 
  • ( ( ) ) ( )
  • ( ) ( ( ) )
  • ( ) ( ) ( )

 

Before moving on to the solution, do try the Problem by yourself.

Approach 1: Recursion

One of the approaches for this problem is to generate all possible valid expressions of length ‘N’ and count the number of such expressions. We can do so recursively (see recursion). For the parentheses to be balanced, the following conditions need to be satisfied. 

  • If N is odd, then there is no valid parenthesis since, for each left parenthesis, there must be a corresponding right parenthesis. So N must be even.
  • If N is even, then for each left parenthesis, there must be a right parenthesis occurring on the right side of the left parenthesis.

To learn more about the Data Structures, you can visit 'Data Structures'

Algorithm

  1. Divide N into two equal parts of N/2.(For left and right parentheses, respectively).
  2. For Recursion, initialize the base case such that when left==0 and right==0, meaning when there are no more possible scenarios left to obtain a balanced parenthesis pair, we return.
  3. Now select the left parenthesis, reduce its count and make a recursive call.
  4. Similarly, now select the right parenthesis, reduce its count and make a recursive call.
  5. To count only valid parentheses, ensure that the right parentheses count is always less than or equal to the left parentheses count at any given time. If the count of right parenthesis exceeds the count of left parenthesis, it indicates that the expression is unbalanced, and the possibility of the expression being valid is violated.

For example, consider the following expressions:

“( ) ) )” , “( ( ) ) ) )”  , “ ) )” , “( ) )”

In any of the above expressions, right > left and they are always invalid and unbalanced (see check for balanced parenthesis) no matter how many more parentheses we insert.

Code in C++

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

int ans=0;//global ans

int helper(int left, int right) {
    if (left == 0 && right == 0){
        ans++;
    }
    if (left > right){
        return 0; 
    }
    
    if (left > 0){
        helper(left-1, right);
    }
    if (right > 0){
        helper(left, right-1);
    }
    return ans;    
}
 
int Validparentheses(int n){
    if(n % 2 == 1) return 0;
    return helper(n/2,n/2);
}

int main()
{
    int res=Validparentheses(6);
    cout<<res<<endl;
    return 0;
}

Code in Java

class Main{
   private static int ans=0;
   private static int helper(int left, int right) {
       if (left == 0 && right == 0){
     ans++;
  }
  if (left > right){
     return 0;
  }
   
  if (left > 0){
     helper(left-1, right);
  }
  if (right > 0){
     helper(left, right-1);
  }
  return ans;

   }

   // Find possible ways for balanced parenthesis
   private static int countWays(int n){
       // If n is odd no possible valid parentheses
       if ((n & 1) != 0)
           return 0;
       return helper(n / 2, n / 2);
   }

   // Driver code
   public static void main(String[] args){
       int n = 6;
       System.out.println(countWays(6));
   }
}

Code in Python

ans=0
def helper(left, right):
   global ans
   if (left == 0 and right == 0):
       ans+=1
   
   if (left > right):
       return 0 
   
   
   if (left > 0):
       helper(left-1, right)
   
   if (right > 0):
       helper(left, right-1)
       
   return ans  

def Validparentheses(n):
   if(n % 2 == 1):
       return 0
   return helper(n/2,n/2)

res=Validparentheses(6)
print(res)

Output

5

Complexity Analysis

Time Complexity: O(2^N)

There are two options for each index, i.e., we can only consider either ‘(’ or ‘)’ at any given position. As a result, the upper bound of time complexity is O(2^N).

Space Complexity: O(1)

Space complexity here is O(2^N) as well due to the space occupied by the recursion stack.

As the time complexity for this approach is rather undesirable when larger numbers are taken into consideration, let us try to think of a more optimal approach.

Approach 2: Catalan Numbers (Dynamic Programming)

If we can observe carefully the number of valid sequences we get for each N, a pattern emerges.

We can easily figure out from the observations that the total possible valid expressions for input N are N/2th Catalan number for when N is even and all odd values of N output will be zero since, for each left parentheses, there must be one right parentheses.

The first few numbers Catalan numbers, Cn (where Cn represents the nth catalan numbers (starting from zero):

1,1,2,5,14,42,132,429,1430,…

nth Catalan number is Cn= (2n)! / ((n+1)! n!)

Another Property for Catalan Numbers is nth Catalan number,  C0 =0  and  Cn =  ∑ni=0CiCn-i.

So our problem reduces to calculating the Catalan number for a given index. As previously computed Catalan numbers can be utilized in the computation of the new ones, we approach this problem as a dynamic programming problem wherein we store all the computed values and use them later as opposed to computing them again.

If you want to learn more about dynamic programming, follow this link.

Algorithm

  1. Initialize k=N/2, since for any N our solution is N/2th Catalan Number.
  2. Create an array “catalanNum” of length k+1 and set catalanNum[0]=1 and catalanNum[1]=1.
  3. Initialize a for loop from i = 2 to i < k+1. For each iteration of the outer ‘for loop’ nest another ‘for loop’ from j = 0 to j < i.
  4. For each iteration of the inner for loop, perform catalanNum[i]+= catalanNum[j] * catalanNum[i-j-1].
  5. Return catalanNum[k].

Code in C++

#include <iostream>
#include <bits/stdc++.h>
using namespace std;


int nthCatalan(int k){
    vector<int> catalanNum(k,0);
    catalanNum[0]=catalanNum[1]=1;
    for(int i=2;i<=k;i++){
        for(int j=0;j<i;j++){
            catalanNum[i]+=catalanNum[j]*catalanNum[i-j-1];
        }
    }
    return catalanNum[k];
}

int validParentheses(int N){
    int k=N/2;
    return nthCatalan(k);
}
int main()
{
    int n=6;
    cout<<validParentheses(n);
    return 0;
}

Code in Java

class Main {
   private static int ans = 0;
   private static int catalanDP(int n) {
     int catalanarr[] = new int[n + 2];

    catalanarr[0] = 1;
    catalanarr[1] = 1;

    // Fill entries in catalanarr[]
    for (int i = 2; i <= n; i++) {
        catalanarr[i] = 0;
        for (int j = 0; j < i; j++) {
            catalanarr[i]
                += catalanarr[j] * catalanarr[i - j - 1];
        }
    }

    return catalanarr[n];
   }

   // Find possible ways for balanced parenthesis
   private static int countWays(int n){
       // If n is odd no possible valid parentheses
       if ((n & 1) != 0)
           return 0;
       return catalanDP(n / 2);
   }

   // Driver code
   public static void main(String[] args){
       int n = 6;
       System.out.println(countWays(6));
   }
}

Code in Python

def nthCatalan(k):
   catalanNum = [0]*(k+1)
   catalanNum[0] = catalanNum[1] = 1
   
   for i in range(2,k+1):
       for j in range(0,i):
           catalanNum[i]+=catalanNum[j]*catalanNum[i-j-1]
       
   return catalanNum[k]

def validParentheses(N):
   k=N//2
   return nthCatalan(k)

n=6
res = validParentheses(n)
print(res)

Output

5

Complexity Analysis

Time Complexity: O(N2)

Since for ith iteration of ‘outer for loop’ for we have “ i ” number of iterations of ‘inner for loop‘.

So Total operations are O(1+2+3+4…..+N-1+N) ~ O(N2). Thus the time complexity is equal to O(N2).

Space Complexity: O(N)

As we are using only a single array of length N, therefore the space complexity of the program is O(N).

Let us try to optimize this approach further

Approach 3: Catalan Numbers (Binomial Coefficient)

Since our problem is reduced to calculate the N/2th Catalan Number, we can also optimally calculate the Catalan number. We can also use binomial coefficient formulas to find the nth Catalan number in O(n) time.

You can also give this question a try before proceeding any further for a clearer understanding.

nth Catalan number is Cn= (2n)!/(n+1) n! n!

Code in C++

#include <iostream>
#include <bits/stdc++.h>
using namespace std;


int binomialCoefficient(int n, int k){

//since C(n, k) = C(n, n - k)
if (k > n - k){
    k = n - k;
}

// initialize result
int res = 1;

//Calculate value of 
    //[n * (n-1) *---* (n-k + 1)] / [k * (k-1) *----* 1]
    for(int i=0;i<k;i++){
        res=res*(n-i);
        res=res/(i+1);
    }
return res;
}

int validParentheses(int N){
    if(N%2==1) return 0;
    int k=N/2;
    int c=binomialCoefficient(N,k);
    return c/(k+1);
}
int main()
{
    int n=6;
    cout<<validParentheses(n);
    return 0;
}

Code in Java

class Main {
   // Find the value of Binomial Coefficient
   private static long findBinomialCoeff(int n, int k){
       int res = 1;

       // Because C(n, k) = C(n, n-k)
       if (k > n - k)
           k = n - k;

       for (int i = 0; i < k; ++i) {
           res *= (n - i);
           res /= (i + 1);
       }
       return res;
   }

   // Find nth catalan number at O(n) time
   private static long catalan(int n) {
       long c = findBinomialCoeff(2 * n, n);
       return c / (n + 1);
   }

   // Find possible ways for balanced parenthesis
   private static long countWays(int n){
       // If n is odd no possible valid parentheses
       if ((n & 1) != 0)
           return 0;

       // Else return n/2 th Catalan Number
       return catalan(n / 2);
   }

   // Driver code
   public static void main(String[] args){
       int n = 6;
       System.out.println(countWays(6));
   }
}

Code in Python

# Returns value of Binomial Coefficient C(n, k)
def binomialCoeff(n, k):
    res = 1

    # Since C(n, k) = C(n, n-k)
    if (k > n - k):
        k = n - k

    # Calculate value of [n*(n-1)*---
    # *(n-k+1)] / [k*(k-1)*---*1]
    for i in range(k):
        res *= (n - i)
        res /= (i + 1)

    return int(res)

# A Binomial coefficient based function to find nth catalan number in O(n) time
def catalan(n):

    # Calculate value of 2nCn
    c = binomialCoeff(2 * n, n)

    # return 2nCn/(n+1)
    return int(c / (n + 1))

def findWays(n):

    # Check if n is odd, since it is not possible to create any valid parentheses
    if(n & 1):
        return 0

    # Otherwise return n/2'th Catalan Numer
    return catalan(int(n / 2))


# Driver Code
n = 6
print(findWays(n))

Output

5

Complexity Analysis

Time Complexity: O(N)

Space Complexity: O(1)

Frequently Asked Questions

What is a valid parentheses expression?

A parenthesis is said to be balanced/valid if, for each left parentheses, there must be one right parentheses, and the matched pairs are properly nested.

What is the best time and space complexity that can be achieved for the problem “Find the number of valid parentheses expressions of length N”?

The best achievable Time Complexity is O(N),  and Space Complexity is O(1).

Why is the recursive approach not efficient enough?

Producing all the possible solutions is not necessary as it will include the overhead time for producing the invalid expressions. It will cost us a huge waste of time and could even lead to Time Limit Exceeded( TLE ) error for large values of N.

Conclusion

Catalan Number is a very crucial concept. Catalan numbers are a unique number sequence found helpful in various combinatorial and counting problems.

Properties of Catalan Number

 

A simple recursive solution can exceed the time limit for some problems, which can be solved using a more optimized approach. A recursive solution can be optimized using Dynamic Programming if we can observe some repeated computations.

You can study more about Dynamic Programming by visiting our blog, ‘Dynamic Programming and Algorithms.’ Also, check out some of our top Courses and blogs on Codestudio.

Want to test your understanding of the concept? Why not give these a try?

Check out these to beef up your skills:

Was this article helpful ?
1 upvote

Comments

No comments yet

Be the first to share what you think