Problem Statement

This problem asks us to count the number of valid parentheses expressions of length n.

A valid parentheses expression must satisfy:

Observation

A valid parentheses expression must contain:

Therefore:

n must be even

If n is odd:

Answer = 0

Example

n = 3

It is impossible to have an equal number of opening and closing brackets.

Therefore, no valid expression can be formed.

Relation to Catalan Numbers

Let:

n = 2k

Then the number of valid parentheses expressions is the k-th Catalan Number.

Example: k = 1

()

Count:

1

Example: k = 2

(())
()()

Count:

2

Example: k = 3

((()))
(()())
(())()
()(())
()()()

Count:

5

These values are exactly:

Catalan(1) = 1
Catalan(2) = 2
Catalan(3) = 5

Catalan Numbers

The nth Catalan Number is given by:

C_n=\frac{(2n)!}{(n+1)!\cdot n!}

For efficient computation, we can use:

C_n=\prod_{i=0}^{n-1}\frac{2(2i+1)}{i+2}

This avoids computing large factorials directly.

Algorithm

  1. If n is odd, return 0.

  2. Compute:

pairs = n / 2

  1. Calculate:

Catalan(pairs)

  1. Return the result.

Example

Input

n = 6

Number of Pairs

pairs = 3

Catalan(3)

5

Valid Expressions

((()))
(()())
(())()
()(())
()()()

Output

5

Java Solution

class Solution {
    int findWays(int n) {
        
        // Odd length can never form valid parentheses
        if (n % 2 != 0) {
            return 0;
        }

        int pairs = n / 2;

        long catalan = 1;

        for (int i = 0; i < pairs; i++) {
            catalan = catalan * (2L * (2 * i + 1)) / (i + 2);
        }

        return (int) catalan;
    }
}

Why This Works

The count of valid parentheses arrangements with k pairs of brackets is a well-known combinatorial result called the Catalan Number.

Since the string length is n:

k = n / 2

Therefore:

Answer = Catalan(n / 2)

when n is even.

If n is odd:

Answer = 0

because a valid parentheses sequence must contain equal numbers of opening and closing brackets.

Complexity Analysis

Time Complexity

O(n)

The Catalan number is computed using a single loop.

Space Complexity

O(1)

Only a few variables are used.

Pattern Recognition

Whenever you encounter problems involving:

think of:

Catalan Numbers

These problems often share the same recursive and combinatorial structure.

Key Takeaway

The most important observation is that a valid parentheses string of length n must contain exactly n/2 pairs of brackets. The number of such balanced arrangements is given directly by the Catalan Number corresponding to n/2. Recognizing this pattern converts an exponential counting problem into a simple mathematical solution.

Summary

To count valid parentheses expressions of length n, first check whether n is even. If it is odd, the answer is 0. Otherwise, let pairs = n/2. The number of valid balanced parentheses sequences is exactly the Catalan Number for pairs, which can be computed efficiently in O(n) time and O(1) space using the multiplicative Catalan formula.