Count Number of Valid Parenthesis

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;
}

You can also try this code with Online C++ Compiler

Run Code

You can check out this recursive solution from this video.

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));
   }
}

You can also try this code with Online Java Compiler

Run Code

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)

You can also try this code with Online Python Compiler

Run Code

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.

Also see, Euclid GCD Algorithm

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/2^th 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 C_n= (2n)! / ((n+1)! n!)

Another Property for Catalan Numbers is nth Catalan number,  C₀ =0  and  C_n =  ∑ⁿ_i=0C_iC_n-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/2^th 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;
}

You can also try this code with Online C++ Compiler

Run Code

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));
   }
}

You can also try this code with Online Java Compiler

Run Code

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)

You can also try this code with Online Python Compiler

Run Code

Output

5

Complexity Analysis

Time Complexity: O(N²)

Since for i^th 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(N²). Thus the time complexity is equal to O(N²).

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/2^th 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 C_n= (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;
}

You can also try this code with Online C++ Compiler

Run Code

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));
   }
}

You can also try this code with Online Java Compiler

Run Code

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))

You can also try this code with Online Python Compiler

Run Code

Output

5

Complexity Analysis

Time Complexity: O(N)

Space Complexity: O(1)

Check out this article - Balanced Parentheses

Check out Longest Common Substring

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.

Also read - Strong number in c

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 Coding Ninjas Studio.

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

• Valid Parenthesis
• Balanced Parenthesis
• Longest Valid Parenthesis

Check out these to beef up your skills:

• Available Courses to make you even better
• Top Dynamic Programming Questions
• Test Series
• Interview Experiences
• Contests
• Problem Set